本文關(guān)鍵詞：平面內(nèi)可相交直線序列的遍歷算法研究

  更多相關(guān)文章： ESP問(wèn)題 Rubber-band算法 直線序列 凸多邊形

【摘要】：ESP問(wèn)題是計(jì)算幾何中的經(jīng)典問(wèn)題。本文針對(duì)遍歷平面內(nèi)可相交直線序列的ESP問(wèn)題進(jìn)行研究,研究目標(biāo)是要尋找一條從起點(diǎn)出發(fā)到達(dá)終點(diǎn),且遍歷給定直線序列中每條直線至少一次的最短路徑。該問(wèn)題是很多實(shí)際應(yīng)用問(wèn)題的抽象模型,針對(duì)該問(wèn)題的研究,不僅具有重要的理論意義,而且也具有很高的實(shí)際應(yīng)用價(jià)值。本文首先闡述了與求解問(wèn)題相關(guān)的基礎(chǔ)知識(shí)與求解方法,如點(diǎn)與直線的位置關(guān)系、直線與直線的位置關(guān)系、對(duì)稱點(diǎn)、凸包、貪婪算法、Rubber-band算法等。在此基礎(chǔ)上,通過(guò)構(gòu)造給定直線序列的凸多邊形,將平面內(nèi)直線序列的遍歷問(wèn)題轉(zhuǎn)化為平面內(nèi)可相交線段序列的遍歷問(wèn)題。為此,本文詳細(xì)論述了凸包構(gòu)造方法以及依據(jù)凸包構(gòu)造凸多邊形的詳細(xì)過(guò)程,給出了遍歷給定可相交直線序列的最優(yōu)遍歷路徑一定包含在所構(gòu)造的凸多邊形內(nèi)部的研究結(jié)論及其嚴(yán)格的理論證明。接著,通過(guò)對(duì)比分析兩種求解可相交線段序列的改進(jìn)Rubber-band算法,選擇交換訪問(wèn)順序的處理方式,提出了一個(gè)時(shí)間復(fù)雜度為O(n2)的求解平面內(nèi)可相交直線序列的最短遍歷路徑的算法。針對(duì)提出的算法,設(shè)計(jì)了相應(yīng)的數(shù)據(jù)結(jié)構(gòu),并用C++程序設(shè)計(jì)語(yǔ)言實(shí)現(xiàn)了該算法。隨機(jī)構(gòu)造了大量測(cè)試數(shù)據(jù),對(duì)所提出的算法進(jìn)行了測(cè)試,并可視化算法運(yùn)行結(jié)果,驗(yàn)證了算法的正確性和有效性。
【學(xué)位授予單位】：大連海事大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：O18

【參考文獻(xiàn)】

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前1條

1 譚錦彪;遍歷平面內(nèi)Partial-Order線段集的ESP求解算法研究[D];大連海事大學(xué);2013年

，

本文編號(hào)：1261005