Java学习：TSP递归程序的优化

在编程中，有一种特殊的程序——递归程序，它通过一系列进程直接或间接地调用自己。程序设计中经常会出现递归程序，所以要学会用递归程序来解决问题，但是递归程序的效率普遍较低，所以要对递归程序进行优化。

下面结合旅行者问题来谈谈递归的优化。

1.递归程序的实现

旅行者的问题如下:旅行者需要去N个城市旅行，每个城市只需要体验一次，要求距离最短。这个问题又称为推销员问题、邮差问题和推销员问题，是著名的N-P问题之一。当n较大时，不采用本文所用的递归遍历法，而是采用其他方法，如神经网络、遗传算法等来得到问题的解。

要得到N个城市依次经历的最短路径，要比较每对N个城市经历的距离，取最小值作为返回结果。

用递归程序解决旅行商问题时，思路和循环法一样:找出所有可能的经验序列，比较每个序列中取的距离，找出最短距离对应的经验序列。在这个问题中，如何通过递归得到所有可能路径的经验应该是重点，而距离的计算、比较和更新类似于循环法。在这个问题的递归调用中，第n个判断经过第n-1层的城市，决定是否穿越。如果N个城市都遍历过了，计算、比较、更新距离，然后返回下一层；如果没有穿越，选择一个未探索的城市加入经验城市，一起传到n+1层。这里，N层调用传入的参数可以看作是已经体验过的城市和已经确定的最短距离，返回的结果可以看作是更新后的最短距离和体验序列。