碩士 / 國立海洋大學 / 電機工程學系 / 90 / Abstract
A path with minimum turns is important for transportation planning, as turns usually incur extra cost, be it time or fuel. In this thesis, we first propose a minimum-turn path-finding algorithm capable of finding a path with minimum turns in rectangular grids.
However, a path with minimum turns may not always be desirable, since decreasing the number of turns usually means increasing the path length. Also, an algorithm for finding a minimum-cost path considering simultaneously two or more factors is, by nature, an NP-complete problem. We solve the minimum-cost path-finding problem with a two-stage approach. First, we use Kirby’s pseudo-network to reconstruct a mesh. This transforms the mesh into a directed graph. Then, we adopt a modified, thus, more efficient, Dijkstra’s algorithm to find the minimum-cost path.
Both path-finding algorithms developed in this thesis achieve O(N) time complexity and are optimal as well.
Keywords: Shortest path, mesh, Lee’s shortest path connection algorithm,
Dijkstra’s algorithm, minimum-cost path algorithm, minimum-turn
path algorithm.
| Identifer | oai:union.ndltd.org:TW/090NTOU0442004 |
| Date | January 2002 |
| Creators | Hsieh Hsiao Chi, 謝效輯 |
| Contributors | Shao-Wei Jan, Gene Eu Jan, 呂紹偉, 詹景裕 |
| Source Sets | National Digital Library of Theses and Dissertations in Taiwan |
| Language | zh-TW |
| Detected Language | English |
| Type | 學位論文 ; thesis |
| Format | 32 |
Page generated in 0.0017 seconds