未知多边形遍历问题不仅涉及算法设计与分析、计算几何、路径规划等基础理论问题,也是解决游戏产业、未知区域搜救等领域实际问题的基础。因此,本课题的研究,兼具理论意义和实用价值。本文针对未知多边形遍历问题以及网格撤离问题进行了研究,首先研究了与求解问题相关的基础知识,如点与多边形位置关系的判定、求解给定两点界定的圆弧、竞争比的分析方法等,然后分析了与课题相关的已有算法,如直线搜索问题的双倍策略、√2倍巡逻员路径近似算法、竞争比为26.5的未知多边形遍历算法,以及竞争比为21的网格单组撤离策略等,并指出部分算法的不足之处。在此基础上,详细研究了竞争比为6.7的未知多边形遍历算法并对其进行了编程实现,通过比较实验结果和理论结果,验证了算法的有效性。同时,提出了解决单源点两组撤离问题与多源点撤离问题的撤离算法,证明了单源点两组撤离策略以及多源点撤离策略不仅适用于危险区域是凸多边形的情形,而且也适用于受灾区域是非凸多边形的情形,并分别计算出了每个算法的竞争比。