TSP问题的动态规划解法.doc

《TSP问题的动态规划解法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、TSP问题的动态规划解法第十七组：郑少斌王瑞锋江飞鸿韩鑫唐万强1．TSP问题简介旅行商问题（TravelingSalesmanProblem,简称TSP,亦称为货单郎问题）可以描述为：对于N个城市，它们之间的距离已知，有一旅行商要从某一城市走遍所有的城市，且每一城市只能经过一次，最后回到出发的城市，问如何选择路线可使他走过的路径最短。这是一个典型的组合优化问题。它有很强的现实意义，可以应用于交通运输，物资调配，旅游线路设置。对于了解某个国家地理分布也有一定的现实意义。这个问题的解法有很多种，在这里我们尝试使用最优控制中的动态规划的相关知识来进行求解。2．TSP问题分析对于

2、这个问题，我们首先想到的是应用穷举法进行解答，但是这个方法时间和空间的复杂度很高。从表面上看，TSP问题很简单，其实则不然。对于N个城市的TSP,存在的可能路径为（N-1）!/2条，当N较大时，其数量是惊人的。计算每条路经都需求出N个距离之和，这样各种路径及其距离之和的计算量正比与N!/2.用搜索法要求就规模大的TSP是不现实的。例如使用1GFLOPs次的计算机搜索TSP所需的时间如下表所示城市数7152050100200加法量搜索时间1.8h350y由上可知，对于这个问题采用穷举法进行解答是不现实的，这就要求我们采用其他的方法进行解答。1．其他求解TSP问题的方法*贪心

3、法a.所谓贪心法，就是在组合算法中，将每一步都取局部最优的求解方法。b.下表表示用贪心法求解TSP的过程。先将各城市间的距离用行列式形式表示，主对角线上用∞表示。我们可以从城市C1出发，依次在每一行或列中选取元素最小的路径，且每个城市只能访问一次。a.按贪心法从C1出发所挑选的路径为L＝2＋7＋3＋4＋4＋3＋10＝33不难看出，这种从局部最优原则出发的方法所得的结果的好坏，与城市间的距离的具体情况和从那个城市开始有关。例如，从C7出发时，用贪心法所得的结果为其路线长度减为L＝2＋5＋3＋7＋4＋3＋7＝31*Hopfield神经元网络法a.全互连型神经网络求解TSP问题

4、：设有N个城市：C={}C中任意两个城市的距离D()=现在要找到一个城市的排列使得闭合路径为最小我们用换位矩阵来表征一条路径。对于N个城市来说，换位矩阵有N*N个元素，需要用N*N个神经元来表征。ABCDEA00001B10000C00100D01000E00010根据下面四方面的要求，即：1.换位矩阵每行只能有一个一；2.换位矩阵每列只能有一个一；3.换位矩阵中元素一之和应为N；4.所构造的函数的极小值对应于最短路径。我们构造出与TSP相对应的计算能量函数为式中前三项与条件的1，2，3的要求对应，上式的第四项为目标项，它的最小值就对应于最短路径长度。上式中v的数值为0或

5、者1，是由表正换位矩阵中神经元的输出来表示的。1．TSP问题的动态规划解法主要特点：将一个问题分为若干个相互联系的阶段，每个阶段进行决策优化。在这种多阶段决策优化过程中，无论其初始状态和初始决策如何，以后的最优策略只取决于由最初策略所形成的当前策略。1．问题分析我们应用动态规划的解法来求解五个城市的TSP问题。我们采用一个矩阵A表示城市之间的距离。其中，，表示第个城市和第个城市之间的距离。这是个对称阵，而且对角线的元素均为0。假定我们已经找到一个最短的路径，设它是先从到，则从出发沿着这条路径回到的路，必定是经过中每个城市一次，最后回到的路径中的最短的一条，也就是符合最优原

6、理。设表示从城市出发，通过s集合中所有城市一次且仅一次，最后回到出发城市的最短路径的长度。由f的定义知，所求最短路径长度可表示为。根据最优原理，应有一般的有：。根据以上分析，应用Matlab编程如下：clearclcD=[0146.13356.43286.99349.83;140.950228.38456.76201.68;364.21233.230431.53198.65;287.89471.96418.440222.73;340.68191.78213.68232.220];n=4;c1=1;c2=n*nchoosek(n-1,n-1);c3=n*nchoosek(n

7、-1,n-2);c4=n*nchoosek(n-1,n-3);c5=n*nchoosek(n-1,n-4);layer1=zeros(1,c1);layer2=zeros(1,c2);layer3=zeros(1,c3);layer4=zeros(1,c4);layer5=zeros(1,c5);path1=0;path2=zeros(1,c2);path3=zeros(1,c3);path4=zeros(1,c4);path5=zeros(1,c5);%###############################第五层fo