基于凸鏈存儲的不相交線段序列的最優(yōu)遍歷算法.pdf

1、本文針對平面上不相交線段序列的最優(yōu)遍歷問題進行研究，目標是要尋找一條從給定起點出發(fā)，依次遍歷每一條線段，最終到達給定終點的最優(yōu)遍歷路徑。該問題也是一個歐幾里德最短路徑(ESP)問題，是計算幾何領域的一個理論問題，也是很多實際應用問題的抽象模型。研究高效的求解該問題的方法，不僅具有重要的理論意義，而且也具有很高的實際應用價值。
　　本文在綜述本領域相關研究成果的基礎上，指出了運用Rubber-band算法求解該問題時可能產生振蕩現象

2、，導致算法時間復雜度較高等問題。為解決這些問題，本文首先研究了與線段遍歷問題相關的一些經典問題，以及問題求解過程中需要用到的基礎知識與基本算法，如確定點與線段的位置關系、直線與直線的位置關系、反射點與完美反射等。在此基礎上，提出了采用凸鏈存儲技術，結合Rubber-band算法，給出不相交線段序列最優(yōu)遍歷問題的求解思路，即利用凸鏈存儲局部最優(yōu)路徑，并利用二分檢索樹實現路徑點的更新，防止振蕩現象的產生，減少迭代次數，提升算法效率的整體解決