结点可同名图的旅行商问题

Traveling salesman problem of the graph of which the vertices may have the same names

随着经济的快速发展,旅游业也大量兴起。但是一般游客的时间和金钱有限,怎么才能花最少的时间和金钱游玩所有想去的城市成了旅行商为大的难题。基于此问题,提出了基于结点可同名求解TSP的算法,首先将旅行商要走的所有城市分成几类,然后在每类城市中选取一个城市来走,并计算出总的距离,最后选取出一条最优的路径。算法实现容易,运行速度快,解决了一类新的TSP问题。在很大程度上给旅行商节约了时间和金钱。

With the rapid development of economy, tourism is getting popular. The general visitors＇ the time and money is limited and how to spend the least amount of time and money to play all the citys that the visitors want to go is traveling salesmen＇ the most difficult problem. For this problem, this paper puts forward an algorithm for solving the TSP that based on the graph of which the vertices may have the same names. Firstly, allocate all the cities into several specific classifications for this TSP. Then, choose one city from every classification and calculate its total distance. At last, choose the optimal road. This algorithm is easy to implement and fast to operate. Thus time and money is saved.