Solving the Weighted Region Least Cost Path Problem Using Transputers

Abstract

The weighted region least cost path problem involves finding the minimal cost path between a source point and a goal point through a plane that has been subdivided into weighted regions. In this thesis, we investigate a new parallel approach which seeks to take advantage of the distributed, asynchronous computing environment provided by the INMOS Transputer. The algorithm consists of a family of local, asynchronous, iterative and parallel procedures. The program is implemented on a network of transputers using a parallel version of the C programming language and tested on various maps of triangulated weighted regions. Results were favorable in terms of producing a near optimum path and reduced processing time.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1989
Accession Number
ADA225399

Entities

People

  • Iván Garcia

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • C Programming Language
  • Communication Channels
  • Computer Architecture
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Computers
  • Computing System Architectures
  • Environment
  • Experimental Design
  • Language
  • Marine Corps
  • Programming Languages
  • Refraction
  • Schools
  • United States

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Approximation Theory.
  • Software Verification and Validation.