不相交多邊形序列遍歷問題的近似求解算法研究.pdf

1、本文針對(duì)不相交多邊形序列遍歷問題的近似求解算法進(jìn)行研究。不相交的任意多邊形遍歷問題是NP難題，因此本文研究目標(biāo)是設(shè)計(jì)一個(gè)近似求解算法，對(duì)于不相交多邊形遍歷問題，找到一條從給定起點(diǎn)出發(fā)，依次遍歷給定的不相交多邊形，最后到達(dá)給定終點(diǎn)的近似路徑。多邊形遍歷問題是部件切割等實(shí)際應(yīng)用問題的理論模型，研究高效的近似求解算法不僅具有重要的理論意義，同時(shí)也具有很高的實(shí)際應(yīng)用價(jià)值。
　　目前，不相交多邊形序列遍歷問題的研究成果較少。本文首先對(duì)問題涉

2、及到的相關(guān)基礎(chǔ)與概念進(jìn)行了分析，如多邊形、點(diǎn)與線段關(guān)系、競(jìng)爭(zhēng)比等。其次，詳細(xì)分析了遍歷多邊形序列最短路徑問題與遍歷凸多邊形序列最短路徑問題之間的聯(lián)系與區(qū)別，提出了求解不相交多邊形序列遍歷問題的求解思路，詳細(xì)論述了多邊形遍歷過程中局部路徑出現(xiàn)的每種情形，以及凸包序列遍歷過程中凸多邊形終段最短路徑圖的區(qū)域劃分，根據(jù)先求解凸包序列，再求解凸包序列最短路徑，最后分別對(duì)多邊形奇、偶序列做處理的方式，更新遍歷路徑，并設(shè)計(jì)出相應(yīng)的不相交多邊形序列遍歷