Researches On Online Exploration Algorithms For Solving Single Source Evacuation Problem

The online exploration problem of rapid evacuation from the dangerous area is to study the deformation problem of polygonal exploration.It requires exploring a path that can quickly evacuate from a dangerous area with unknown boundary information.The study of this problem not only involves related basic knowledge such as computational geometry,but also can provide technical support for solving some practical problems,so it has both great theoretical significance and practical application value.This article mainly studies the evacuation problem.In the study,the boundary information of the agreed evacuation area is unknown,and in the case of a single source point,the evacuation people can be divided into n groups,and it is required to explore an optimal evacuation strategy.To this end,this article analyzes the relevant basic knowledge and concepts that may be involved in the study of the problem firstly,such as whether the point is on a straight line,the position relationship between the point and the polygon,the spatial position relationship between the point and the line segment,and the calculation of the competition ratio,etc.Then the existing research results such as straight line search algorithm,double strategy,semicircle evacuation strategy of single source with 1 group and semicirle evacuation strategy of single source with 2 groups are analyzed in detail.Aiming at the problem of single-group single-source evacuation,a new evacuation strategy suitable for exploring convex polygon area,namely the triangle evacuation strategy,is proposed.Its competition ratio is 19.48,which is lower than the existing algorithms.At the same time,it focuses on the multiple-group(n?2)single source evacuation problem,applies the triangle evacuation strategy to the multiple-group single-source evacuation problem,and calculates the competition ratio of the corresponding exploration strategy,the result is better than the existing exploration strategy.Programming implements the proposed algorithm,and constructs test data to verify the correctness and effectiveness of the algorithm.Theoretical analysis and experimental results show that the triangle evacuation strategies proposed in this paper are effective algorithms to solve the problem of polygon evacuation.