遍歷平面內(nèi)Partial-Order線段集的ESP求解算法研究.pdf

1、Euclidean最短路徑(ESP)問題是計(jì)算幾何中的經(jīng)典問題，很多實(shí)際應(yīng)用問題都可以抽象成ESP問題進(jìn)行求解。平面內(nèi)Partial-Order線段集ESP問題是從最短巡視員路徑問題抽象出來的一個(gè)模型，研究目標(biāo)是尋找一條從起點(diǎn)出發(fā)到達(dá)終點(diǎn)，且遍歷給定線段集中每條線段至少一次的最短路徑。該路徑是解決最短巡視員路徑問題的關(guān)鍵步驟，因此，針對(duì)該問題的研究，不僅具有理論意義，而且還有重要實(shí)際應(yīng)用價(jià)值。
　　 本文首先針對(duì)計(jì)算幾何的相關(guān)基

2、礎(chǔ)知識(shí)和算法進(jìn)行研究，著重研究簡單多邊形以及線段相交性判斷等問題，同時(shí)，對(duì)貪心算法及其特點(diǎn)也做了較為深入的分析。在此基礎(chǔ)上，針對(duì)Rubber-band算法用于遍歷平面內(nèi)有序不相交線段的ESP問題求解過程中存在的不足，通過深入分析相鄰線段相交的各種可能的情形，以及改變?cè)L問順序?qū)η蠼庾疃搪窂降挠绊?，提出了改進(jìn)Rubber-band算法的技術(shù)方法，使其能夠用于求解本文所研究的Partial-Order線段集的ESP問題。針對(duì)改進(jìn)算法，設(shè)計(jì)了相