A Study Of The Online Searching Algorithms Based On Watchman Route Problem

The problem of visiting an unknown polygon not only involves algorithm design and analysis,computational geometry,path planning,but also is the basis for solving practical problems in game industry and emergency evacuation.Therefore,the research of this subject has both theoretical significance and practical value.The main work of this paper is to solve the online watchman route problem and grid evacuation problem.First of all,the related basic knowledge of computational geometry involved in this paper are discussed,such as determining the relationship between a point and a polygon,determining the arc defined by two points and analyzing the competition ratio.Then,we analyze existing algorithms related to the subject,for example,"doubling strategy" of liner search problem,-times watchman route approximation algorithm,26.5-competitive algorithm for visiting an unknown polygon and 21-competitive evacuation strategy for the evacuation problem in a grid by single group.We also point out the shortcomings of them as well.On this basis,we study and encode the 6.7-competitive algorithm for visiting an unknown polygon,and verify the effectiveness and feasibility of this algorithm by comparing experimental result with theoretical result.At the same time,we propose two evacuation algorithms to solve thesingle-source point evacuation problem and the multi-source evacuation problem,in addition,we also prove that the single-source point two-group evacuation strategy and multi-source evacuation strategy are applicable to situations in which the dangerous area is a convex polygon or a non-convex polygon.Finally,we calculate the competition ratio of each algorithm respectively.