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

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

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