基于计算几何与图论的动态目标协作搜索机制及其算法研究

项目名称： 基于计算几何与图论的动态目标协作搜索机制及其算法研究

项目编号： No.61173034

项目类型： 面上项目

立项/批准年度： 2012

项目学科： 计算机科学学科

项目作者： 蒋波

作者单位： 大连海事大学

项目金额： 55万元

中文摘要： 多搜索员协作搜索机制及其搜索算法是动态目标搜索研究的核心问题。本项目基于计算几何与图论的技术方法，针对2维或3维空间里的移动目标，研究搜索这些目标的各种搜索算法。将搜索区域设定为多边形或多面体的表面，并将搜索目标设定为多边形内快速移动的点，设计性能较优的算法搜索该动态目标并计算发现目标所需的最少搜索员数。采用循序渐进方法,先研究1个搜索员在多边形内进行搜索时的充要条件，并在可搜索时给出线性时间算法。然后针对多个搜索员，设计一个递减过程将它逐步归纳为2个搜索员的问题，运用计算几何与图论的相关技术为搜索员建立可视图与动态变迁图，并对已搜索区做合并操作，在此基础上设计相应的求解算法。当多边形内部含有洞(属NP难题)时,采用平面图分割定理进行递归剖分,消去洞的影响并获得较好的近似算法。拓展到3D空间，当多面体表面的垂直投影为平面图时，将它归纳为图的搜索问题后再求解。本项研究成果具有很好的应用前景。

中文关键词： 计算几何；动态目标搜索；多搜索员协作搜索；可视性；竞争比

英文摘要：

英文关键词： Computational geometry；Searching mobile targets；Collaboration search with multi-searchers；Visibility；Competitive ratio