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

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

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