有限空間中最短路徑規劃

The Planning of a 3D Shortest Path in a Volume

詹景裕(Gene Eu Jan) ； 張啓隱(Ki-Ying Chang) ； 吳建興(Jhiann-Shing Wu)

《中國航空太空學會學刊》 35卷2期 (2003/06) Pp. 197-202

https://doi.org/10.6124/TAASRC.200306_35(2).11

摘要

1961年Lee提出路徑連接演算法，一直被廣泛應用在路徑與印刷電路板佈線規劃上：最近Jan所提出的網格圖最短路徑演算法，改善了Lee演算法只針對4個方向搜尋路徑的缺點，同時搜尋8個方向並以輻射擴散的方式，使所求之路徑更趨近實際空間之最短路徑，此演算法的時間複雜度爲O(N^2)，其中N爲網格數。本文之有限空間最短路經規劃演算法，藉由Jan演算法擴展至有限空間，且以核子分裂連鎖反應的特性使演算法的時間複雜度降低至O(N)而空間複雜度維持在O(N)，並減少Jan演算法所需之計算量及輔助計算用的連結串列。

關鍵字

最短路徑 ； 網格圖 ； 有限空間

並列摘要

The Lee path connection algorithm, which proposed in 1961, is the most widely used method for finding wire paths on PCB and VLSI design. Recently, Jan proposed an algorithm on the raster plane with O(N^2) time. It improved Lee's algorithm from searching four connected neighbors to eight connected neighbors. We extended Jan's algorithm to the 3D shortest path algorithm with the properties of nuclear fission chain reaction on the volume. This algorithm, which also has less auxiliary linked lists and the time and memory space complexities of O(N), has been coded in C(superscript ++) language on a PC and some illustrations are presented.

並列關鍵字

Rater map ； Shortest path ； Volume