有限空間內最短路徑之研究

近年來，圖論的應用層面延伸至各個研究領域，而圖論問題中最短問題為其核心問題，而本研究主要是探討有限空間內之最短問題，有限空間內之最短路徑問題在應用上甚廣，如警衛放置問題、無人搬運車、等等有關在有限空間內移動之相關問題。然而，以往的文獻上總把空間內的物體當成是障礙物(obstacle)，而去尋找一條不去碰觸此些障礙物的最短路徑，在此，將此些障礙物當成是目標(target)來處理，此問題就像是動物園管理員問題(zookeeper’s problem)，。而本論文是研究在一有限空間P內含有多個目標多邊形(target)，如何從一起始點出發，巡視完各個目標多邊形，並至終點之最短路徑問題，而本論文針對此問題提出了一個新的演算法，因本問題為一起點與終點已知且各個目標多邊形必須經過至少一次之Hamiltonian path，故為一NP-complete問題。

關鍵字

最短路徑；幾何學；多邊形

並列摘要

The problems of finding the shortest path without touching any obstacle have been studied intensive The different point of this study is that some objects inside the space and treated as targets The essence of this research is to find the shortest path conneting all the targets without touching the obstacles .It is to find the shortest Hamiltonian path problem,which is known as a NP-complete problem An approximate algorithm is developed A simulation is given to show that computational complexity of this algorithm is linear

並列關鍵字

shortest-path problem ； geometry ； polygon

參考文獻

【13】Vasko Francis J,Barbieri Robert S, Rieksts Brian Q,Reitmeyer Kenneth L,

【5】Lalgudi Kumar N,Papaefthymiou Marios C,Computing strictly-second shortest- paths Information Processing Letters Volume: 63, Issue: 4, pp. 177-181, August 28, 1997

【6】Lin, Yi-Kuei,Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network ,Computers and Operations Research Volume: 30, Issue: 4, pp. 567-575 , April, 2003

【7】Khosravi, Ramtin,Ghodsi, Mohammad,Shortest paths in simple polygons with

【9】Rios Miguel,Marianov Vladimir Avagliano,Andres,Multiple path routing algorithm for IP networks ,Computer Communications Volume: 28, Issue: 7, pp. 829-836，May 2, 2005

國際替代計量

有限空間內最短路徑之研究

未授權

主題瀏覽