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

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

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