旅行商问题的较优可行解的搜索算法的设计

利用问题本身的特点和相关的已有结论，结合最近邻法和深度优先搜索算法设计了产生旅行商问题较优可行解的方法。首先，将与每个城市关联的城市由近到远排序，并将城市之间距离较远的边删除。然后选择一个城市作为出发地，按排序利用深度优先搜索算法在有限步内搜索可行解。若搜索到多个可行解，从中选择较优的作为以该城市为出发地的可行解；否则，重新选择出发地开始新的搜索。对经典的st70、a280问题依次将每个城市作为出发地进行实验，该方法产生的可行解的性能明显优于随机搜索算法。但仍不及最近邻法。

Design and Implementation for Searching Feasible Solutions of Traveling Salesman Problem

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.