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

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

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