Research On Optimal Algorithm For Touring Intersecting Circle Sequences In The Plane

This paper,we proposed an optimal algorithm for the shortest path problem of touring a sequence of circles in the plane.Our work is to propose an intelligent algorithm,which can find the shortest path access from the given point to the end point,visiting every circle by order.This problem is a variant of the classic traveling salesman problem.Therefore,it has a high theoretical value.At the same time,this problem is also an abstract model of many practical problems,such as route planning,layered manufacturing,wireless sensor network transmission,etc.So we can see that the study on this problem also has high practical application value.In the algorithm design section,we discusses some basic points and common algorithms in geometric object traversal.On this basis,we analyze the research results of existing related traversal problems,such as the latest results of traversal problems with line segments or convex polygon sequences,which can be intersecting or not.The local geometrical properties of the circle sequence propose the necessary region division by tangents between adjacent circles.Using this method of region division,the local circle sequence is divided into different regions,and the local shortest path point solution scheme is determined.After determining the solution scheme of the local shortest path,the iterative calculation is performed using the local optimum,and a globally optimal traversal path is constructed.Finally,the method of the traversal path is given for different local optimal access types.This paper proves the existence and uniqueness of the shortest traversal path of the circle sequence,and draws on the algorithm idea of line segment traversal,such as dynamic programming,to design an algorithm with time complexity not exceeding O(n2).In the experimental part,this paper implements the algorithm through programming,and uses the experimental results of a large number of test data to verify the effectiveness of the algorithm.Through a large number of practical arguments,the intersecting circle sequence traversal algorithm proposed in this paper is an effective algorithm for solving the traversal problem of circle sequences on a plane.