回溯法解决旅行售货员(TSP)问题

问题描述：

某个售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地城市出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或总旅费）最小。

如：正确答案应该是 1->3->2->4->1，最少路费为 25.

算法描述及思考过程：

用回溯法解决，解空间是排列树。

而剪枝的条件是，如果不存在这条路径（从 x[n-1]到 x[n]或是从 x[1:n]），或者当前 x[1:n]的费用大于了当前最优值，则剪枝。

所以当路径存在，且费用小于最优值时，选取这条路径。

例 1：

剪枝后的解空间树为：

例 2：

剪枝后的解空间树为：

运行结果及实验结果说明：

例子 1.

四个城市间都可以相互到达，如图。

正确答案应该是 1->3->2->4->1，最少路费为 25.

运行结果：

例子 2

若城市 2,4 不通，如图。

正确结果应为 1->2->3->4->1,最少费用为 59.

运行结果如图：