A New Tour Construction Algorism and its Application in Laser Carving Path Control[J]. Journal of Image and Graphics, 2007, 12(6): 1114. DOI: 10.11834/jig.20070625.
By Bring in integral principle and the idea of Kruskal/2-opt algorism
a new tour construction algorism with time complicity O(N2) is presented in this paper. In fact
carving path of laser carving machine could be transferred to the traveling salesman problem(TSP) and optimized for laser carving process(LCP). In this algorism
some reasonable small loops are constructed in the first step
then larger loops are progressively synthesized with the small ones from bottom to top and in the end
a near-optimal resolution can be captured in this way. Moving distance resulted from this calculation is about 1.1 times of lower bound due to Held and Karp. Experimental results show that in the case of laser engraving machine