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

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

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