簡單多邊形中兩個守衛(wèi)的min-sum算法研究.pdf

1、兩個守衛(wèi)(two-guard)問題是計(jì)算幾何中的經(jīng)典問題之一,它的主要研究議題是:對于一個給定的簡單多邊形P,在它的邊沿上有一個入口s和一個出口t,該多邊形P被稱作走廊。two-guard問題要求守衛(wèi)從入口s出發(fā),把目標(biāo)(指非法入侵者)從出口t驅(qū)逐出去。這類守衛(wèi)問題是由著名的畫廊問題和巡視員路徑問題激發(fā)而來,該類問題致力于在一個n邊形P中用一組移動的守衛(wèi)檢測一個不可預(yù)測的、移動的目標(biāo)。
　　 本文對two-guard問題中的子問

2、題min-sum問題即簡單多邊形中兩個守衛(wèi)走過的距離的總和達(dá)到最小的問題進(jìn)行了深入研究。由于一臺機(jī)器人(或守衛(wèi))需要的能量和成本是它所移動距離的遞增函數(shù),所以研究min-sum問題具有十分重要的價值。
　　 首先,研究計(jì)算幾何領(lǐng)域中的相關(guān)基礎(chǔ)知識；其次,論述計(jì)算幾何中的經(jīng)典守衛(wèi)問題,如畫廊問題、最短巡視員路徑問題以及two-guard問題:再次,研究two-guard問題中的兩種基本掃描方式,即直掃描和反掃描,論述相關(guān)掃描機(jī)理,