Efficient grid based techniques for solving the weighted region least cost path problem on multicomputers
MetadataShow full item record
This thesis explores the possibilities of developing fast grid parallel algorithms to solve the Weighted Region Least Cost Path problem. Two complimentary steps have been undertaken. First, an efficient sequential algorithm to solve the above problem was developed. the algorithm is a modification of a Gauss-Seidel-like algorithm for obtaining the minimum costs. The most salient feature of the algorithm is the reduction of the number of nodes and edges in cheaper regions of the grid. the reported experimental results ascertain the superiority of this algorithm with regard to computer running time at a modest reduction in the accuracy of the obtained solution. Parallel implementations of grid-based algorithms were studies. A simple grid-based variant was implemented on a network of Transputers. The overall approach is employed could be used to develop a parallel version of the above sequential algorithm on a Transputer network, combining both advantages of efficiency and parallelization.
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Rhoden, Christopher A. (Monterey, California. Naval Postgraduate School, 1994-06);The Simplex algorithm, developed by George B. Dantzig in 1947 represents a quantum leap in the ability of applied scientists to solve complicated linear optimization problems. Subsequently, its utility in solving finite ...
Huang, Jo-Wen (Monterey, California: Naval Postgraduate School, 2017-06);With the development and advancement in the technology of control and multi-robot systems, robot agents are likely to take over mine countermeasure (MCM) missions one day. The path planning coverage algorithm is an essential ...
Zyda, Michael J. (Monterey, California. Naval Postgraduate School, 1984-09); NPS-52-84-013We present in this study the architectural specification and feasibility determination for a real-time contour display generator. We begin by examining a recently reported, highly decomposable algorithm for contour surface ...