Monterey, CA; Naval Postgraduate School
Efficient grid based techniques for solving the weighted region least cost path problem on multicomputers
Abstract
dc:description.abstractThis 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.
Degree
thesis:*- Name thesis:degree_name
- M.S. in Engineering Science
- Level thesis:degree_level
- Masters
- Discipline thesis:degree_discipline
- Engineering Science
- Department dc:contributor.department
- Department of Computer Science
- Grantor dc:publisher
- Monterey, CA; Naval Postgraduate School
- Year dc:date.issued
- 1992
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Ekin, Cengiz
- Advisor dc:contributor.advisor
-
- Zaky, Amr
- Committee member dc:contributor.committeemember
-
- Kwak, Sehung
Rights
dc:rights- Statement dc:rights
-
- Copyright is reserved by the copyright owner.
- Approved for public release; distribution is unlimited.
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/10945/23654