平面上成组疏散的Online搜索算法研究

发布时间：2018-04-05 21:36

  本文选题：计算几何　切入点：Online搜索问题　出处：《大连海事大学》2017年硕士论文

【摘要】：平面上成组疏散的Online搜索问题的求解研究,不仅涉及计算几何、图论、组合优化等技术方法,而且是解决很多实际应用问题的基础,所以针对该问题的研究,不仅具有理论意义,而且具有较高的实际应用价值。本文针对边界信息未知的单源点疏散问题中分组数为n(n≥2)的快速疏散策略进行研究,首先分析了用于问题求解的相关基础知识及概念,如判断点在直线上、判断点是否在多边形内、竞争比的计算等,然后对直线上探索问题的双倍策略、单源点与多源点的成组等角疏散策略、单源点半圆疏散策略等已有研究结果进行了较为详细的分析,指出了其中存在的不足。在此基础上,针对分组数为2的单源点疏散问题,应用半圆疏散策略,设计出了相应的求解算法,并拓展应用到分组数为n(n≥3)的情形,设计出了相应的成组扇形疏散策略,分析了每个疏散策略的竞争比。同时指出分组数≥2的半圆疏散策略同样适用于求解疏散区域为非凸多边形的疏散问题,并对非凸情形下的竞争比做了详细分析。最后,编码实现了n=2的半圆疏散策略以及分组数≥2的成组扇形疏散策略。运行结果表明,本文所设计的算法是可行且高效的。
[Abstract]:The research of solving the Online search problem of group evacuation on the plane is not only related to computational geometry, graph theory, combinatorial optimization and other technical methods, but also the basis of solving many practical application problems.Not only has the theory significance, but also has the higher practical application value.In this paper, the fast evacuation strategy for single source point evacuation problem with unknown boundary information is studied. Firstly, the basic knowledge and concepts for solving the problem are analyzed, such as the judgment point is on a straight line.To determine whether the point is in the polygon, to calculate the competition ratio, and then to explore the double strategy of the problem on the straight line, the group equiangular evacuation strategy of the single source point and the multiple source point, etc.The research results of single source point semi-circular evacuation strategy are analyzed in detail, and the shortcomings are pointed out.On this basis, for the evacuation problem of single source point with number of groups 2, a corresponding algorithm is designed by using semi-circular evacuation strategy, and extended to the case where the number of groups is n / n 鈮，

本文编号：1716588