Design and Implementation for Searching Feasible Solutions of Traveling Salesman Problem
Peijun Chen · Journal of Taiyuan University of Science and Technology · 2009
Using the characters of traveling Salesman problem(TSP),the conclusions connected with TSP,the nearest neighbor(NN)method and depth first search(DFS) algorithm,a method of generating better feasible solutions for TSP are designed.First,we sort the cities according the distances for every city,and delete the longer edges between cities.Secondly,we choose one city as the first city and search Hamilton cycles in finite step with NN and DFS.If many Hamilton cycles can be found,the best one is chosen as the feasible solution.Otherwise we choose another city as the first city and begin new search.We choose every city as the first city and generate the solutions for st70、a280 with this method.The results show that the solutions are much better than the solutions generated randomly,but the efficient and precision of this method are still not better than NN.