環(huán)形走廊中1-searcher搜索問(wèn)題的算法研究.pdf

1、本文針對(duì)環(huán)形走廊中的1-searcher搜索問(wèn)題進(jìn)行研究。環(huán)形走廊是指在一個(gè)簡(jiǎn)單多邊形的內(nèi)部包含另一個(gè)與之不相交的簡(jiǎn)單多邊形，本文限定給定的環(huán)形走廊具有內(nèi)、外邊界相互弱可視的幾何特性。所謂1-searcher，是指持有一條搜索光束的機(jī)器人或人，且只有光束所發(fā)出的射線段對(duì)其是可視的。約定1-searcher的光束始終照射在內(nèi)邊界上。環(huán)形走廊中1-searcher搜索問(wèn)題是機(jī)器人搜索等實(shí)際應(yīng)用問(wèn)題的理論模型，因此研究該問(wèn)題，不僅具有理論意義

2、，而且具有很大的實(shí)際應(yīng)用價(jià)值。
　　本文在分析環(huán)形走廊的幾何特性、Two-guard問(wèn)題的相關(guān)求解技術(shù)與方法、1-searcher的搜索能力等問(wèn)題的基礎(chǔ)上，針對(duì)內(nèi)、外邊界具有相互弱可視特性的環(huán)形走廊，提出了“開(kāi)始階段”“結(jié)束階段”和“不可分割死鎖”等關(guān)鍵概念，對(duì)兩個(gè)1-searcher可掃描環(huán)形走廊的判定條件及其判別方法進(jìn)行了較為詳細(xì)的研究，設(shè)計(jì)出了O(nlogn)時(shí)間的判定算法，并在可掃描情形下，設(shè)計(jì)出了相應(yīng)的掃描方案。同時(shí)，指