Java 语言 TSP 递归程序的优化
程序设计中,有一种特殊的程序——递归程序,递归程序是直接调用自己或通过一系列的过
程间接调用自己的程序。递归程序在程序设计中经常出现,因此应该学会使用递归程序求解
问题,但递归程序运行的效率一般都比较低,因此应对递归程序进行优化。
下面结合旅行家问题谈谈递归的优化。
一.递归程序的实现
旅行家问题如下:旅行家要旅行 N 个城市,要求各个城市经历且仅经历一次,并要求
所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题,是有名的 N—P 难题
之一。在 N 很大时,并不采用本文所用的递归遍历方法,而是采用其他方法,如神经网络、
遗传算法等,得到问题的解。
要得到 N 个城市依次经历的最短路径,应把各个对 N 个城市的经历所经过的路程相比
较,选出其中的最小值作为返回结果。
用递归程序解决旅行家问题时,思路与循环方法一样:找出各种可能的经历顺序,比较在各
个顺序下所走的路程,从中找出最短路程所对应的经历顺序。该问题中如何通过递归得到对
所有可能路径的经历应作为重点,而对路程的计算、比较、更新与循环方法类似。在该问题
的递归调用中,第 n 对第 n-1 层传递过来的已经经历的城市进行判断,以决定是否已经遍历,