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

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

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