平面內(nèi)不相交圓序列遍歷問題的求解算法研究.pdf

1、本文針對(duì)平面上不相交圓序列的最優(yōu)遍歷問題進(jìn)行研究，其目標(biāo)是尋找一條從給定起始點(diǎn)出發(fā)，依次遍歷每個(gè)給定的圓，最終到達(dá)目標(biāo)點(diǎn)的最短遍歷路徑。該問題不僅是計(jì)算幾何領(lǐng)域的一個(gè)理論問題，而且也是很多實(shí)際問題的抽象模型，因此研究該問題，不僅具有重要的理論意義，而且具有很高的實(shí)際應(yīng)用價(jià)值。
　　本文在分析有關(guān)研究成果的基礎(chǔ)上，依據(jù)平面上不相交線段序列、不相交多邊形序列等遍歷問題的現(xiàn)有求解方案，結(jié)合不相交圓序列的幾何特征分析，提出了通過構(gòu)造相鄰圓

2、之間的切線，以便快速確定圓上路徑點(diǎn)的局部最優(yōu)路徑，并通過組合優(yōu)化構(gòu)造全局最優(yōu)遍歷路徑的求解方法。為此，本文首先分析了與不相交圓序列遍歷問題有關(guān)的一些基本知識(shí)，如點(diǎn)與圓的位置關(guān)系、兩個(gè)相鄰圓的公切線、反射點(diǎn)以及完美反射等，然后針對(duì)遍歷圓時(shí)可能出現(xiàn)的穿越、反射等訪問類型進(jìn)行了分析，分別給出了局部最優(yōu)遍歷路徑的計(jì)算方法。在此基礎(chǔ)上，利用不相交圓序列最短遍歷路徑的存在性和唯一性，通過局部優(yōu)化并加以組合的技術(shù)方法，設(shè)計(jì)出了時(shí)間復(fù)雜度為O(n2)的