单源点疏散问题的Online探索算法研究

Research on Online Exploration Algorithm for Single Source Evacuation Problem

课题所研究的问题是受困人员如何从未知情形的受灾区域中尽快地完成撤离.单源点疏散问题是指受灾人员位于危险区域P中的某个位置,需要找到一条能够快速地到达安全位置(P的边界)的疏散路线.由于受灾人员不知道P边界的任何信息,所以采用online探索算法,针对单组单源点疏散问题,提出了三角形疏散策略探索凸多边形区域,计算出所提算法的竞争比为19.48,低于已有算法的竞争比,即优于现有求解该问题的其它算法.同时提出了分组数为2的半圆疏散策略用于探索P为任意多边形区域的情形,得到了一个较小的竞争比,结果表明,单源点半圆疏散策略可以较好地解决疏散区域为非凸多边形的疏散问题.

The problem studied in this topic is to solve the problem of how the trapped person can complete the evacuation as soon as possible from the disaster area of the unknown situation.The single-source point evacuation problem means that the affected person is located at a certain position in the dangerous area P,and needs to find an evacuation route that can quickly reach the safe position(the boundary of P).Since the disaster persons do not know any information about the P boundary,they can only do online exploration to find a safe boundary,for the single-source single-point evacuation problem,a triangular evacuation strategy is proposed to explore the convex polygon region,the calculated competition ratio is 19.48,which is lower than the competition ratio of the existing algorithms,indicating that the algorithm is superior to other existing algorithms for solving this problem.At the same time,a semicircular evacuation strategy with a group number of 2 is proposed to explore the case where P is an arbitrary polygonal area,and a smaller competition ratio is obtained.The result shows that the single-source point semicircle evacuation strategy can better solve the problem of evacuation what the evacuation area is a non-convex polygon.