Introduction       Since the appearance of path planning conception, it has been widely used to solve reality problems, take the Semiconductor industry as an example, when using a drill to bore holes on a printed circuit board (PCB), the total time spent can be divided into two parts: the time of boring the hole and the time of moving from one hole to another. The drill starts from the assigned position, after boring all holes on the PCB, it moves back to its previous location. This essay will focus on the boring process and seek the fastest way to finish a job. Firstly, the working process of the drill is illustrated. Following this, a theory to solve this problem is proposed and it will be explained in detail. Finally, a suggestion to this problem is given, it may not be the best one, but still a useful method.       Drilling Process       High productivity and low cost are the fundamental elements that industry manufacture especially volume manufacturing is seeking. Just as shown in figure 1, there are holes in different dimension in the PCB, when a drill works, it will cover all points on the tour that the red line shows below and then move back to its original location to change the drill for the next process.       Time spent on boring the hole which is called pad in IC industry can be calculated with the formula:       ttotal : time spent totally during the process   ti-process: time spent boring the hole   ti-move : time spent moving from one hole to another           Figure 1   TSP Algorithm       The problem can be divided into the Traveling salesman Problem (TSP) whose goal is to find the shortest tour that visits each of a collection of n subsets in the underlying metric space (T-H.H Chan & K.Elbassioni, 2010). Although to the limited subsets, there must be a shortest tour, and the tour can be found out by enumeration. However, when the subset amount is large, it becomes complex to solve this problem. Karp (1972) proved the TSP to be non-deterministic polynomial, but effective heuristic approximation methods were developed to solve this.       The traveling salesperson problem can be solved with the minimum spanning tree (MST) heuristic. The MST cost of a set of subsets is the smallest sum of the link that connects all the subsets. Prim's algorithm can be used to solve the MST problem for a connected weighted undirected graph (Thomas H. Cormen, 2009).   (a)    Input: A non-empty connected weighted graph with vertices V and edges E   (b)   Initialize: Vnew = {x}, where x is an arbitrary node (starting point) from V, Enew = {}   (c)    Repeat until Vnew = V:   1)        Choose an edge {u, v} with minimal weight such that u is in Vnew and v is not (if there are multiple edges with the same weight, any of them may be picked)   2)        Add v to Vnew, and {u, v} to Enew   (d)   Output: Vnew and Enew describe a minimal spanning tree   Application       For the planning movements of automatic circuit-board drills, suppose there are eight pads on the PCB shown as below (http://www.personal.kent.edu):   1)      Construct MST from root a using MST-PRIM (G, c, r). Define V={a, b, c, h, d, e, f, g }, Vnew={a}, repeat the MST process listed in TSP algorithm, after this, the link is shown as picture a of figure 2.   2)      List vertices visited in preorder walk. L = {a, b, c, h, d, e, f, g}. As shown in picture b of figure 2.   3)      Return Hamiltonian cycle. As shown in picture c of figure 2.       (a) MST              (b) preorder walk      (c) Hamiltonian cycle   Figure 2   The Final Optimal TSP tour for a given problem (graph) would be as figure 3.       Figure 3 Final Optimal TSP tour           Conclusion   In conclusion, TSP is a difficulty to the scientist and people have been trying to find a good method to solve this. This essay uses the MST heuristic algorithm to learn the smallest distance of edges linking vertices, and then an improved method is used to meet the TSP requirement. Besides this, the TSP plays a big role in planning trips for traveling salespersons and stocking machines on shop floors. Mathematics model helps a lot to the society development.       Reference:       R. E. Miller. J. W. &Thatcher. D. (1972) Reducibility among combinatorial problems. New York: Complexity of Computer Computations.       Stuart Russell,A. & Peter Norvig, D. (2009) Artificial Intelligence: A Modern Approach. NewJersey: Pearson Education.       Thomas, H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. J. (2009) Introduction to Algorithms. Massachusetts: MITPress.       T-H.H Chan & K.Elbassioni. D. (2010) A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics. Springer.   ......