动态规划解TSP问题

用动态规划方法编程求解下面的问题：某推销员要从城市出发，访问其它城市23, 各一次且仅一次，最后返回为各城市间的距离矩阵。问：该推销员应如何选择路线，才能使总的行程最短？v101020304050v212018302521v3D=2319051015v4343240816v545271110018v6_562216201201、变量设定TOC\o"1-5"\h\z阶段：已遍历过个结点， ，表示刚从出发， 表示已回到起点状态变量 ,：已遍历个结点，当前位于结点，还未遍历的结点集合为。则， ， ，①) =①决策变量 ,i已遍历个结点，当前位于结点，下一个结点选择。状态转移方程： T ,第阶段的指标函数 。最优指标函数 ， ：已遍历个结点，当前从结点出发，访问中的结点一次且仅一次，最后返回起点的最短距离。则, ^ WW=①、分析：()时，，①=①==①,①,①21①——6,①,1①6,①,1①6,①51①6,①,1①6即时，对于每一种状态，都有唯一的决策()时， ( [①①①,①5①

,①，①6①，①，①2①，①5①，①2①6①，①，①2①，①,①3①2①即时，对于每一种状态5都有唯一决策()时，

(3,5)⑸{4})104454=F4(3,{4,5})(3,{4,6})(3,4)(4,{6})57277(3,6)(6,{4})155469=F4(3,{4,6})(3,{5,6})(3,5)(5,{6})107484(3,6)(6,{5})155772=F4(3,{5,6})(4,{2,3})(4,2)(2,{3})324173(4,3)(3,⑵)43134=F4(4,{2,3})(4,{2,5})(4,2)(2,{5})3270102(4,5)(5,{2})83947二F4(4,{2,5})(4,{2,6})(4,2)(2,{6})3277109(4,6)(6,{2})163450=F4(4,{2,6})(4,{3,5})(4,3)(3,{5})45559(4,5)(5,{3})83442=F4(4,{3,5})(4,{3,6})(4,3)(3,{6})47175(4,6)(6,{3})163955=F4(4,{3,6})(4,{5,6})(4,5)(5,{6})87482(4,6)(6,{5})165773=F4(4,{5,6})(5,{2,3})(5,2)(2,{3})274168(5,3)(3,⑵)113142=F4(5,{2,3})(5,{2,4})(5,2)⑵{4})276491(5,4)(4,{2})104454=F4(5,{2,4})(5,{2,6})(5,2)(2,{6})2777104(5,6)(6,{2})183452=F4(5,{2,6})(5,{3,4})(5,3)⑶{4})113950(5,4)(4,{3})102737=F4(5,{3,4})(5,{3,6})(5,3)(3,{6})117182(5,6)(6,{3})183957=F4(5,{3,6})(5,{4,6})(5,4)(4,{6})107282(5,6)(6,{4})185472=F4(5,{4,6})(6,{2,3})(6,2)(2,{3})224163(6,3)(3,⑵)163147二F4(6,{2,3})(6,{2,4})(6,2)⑵{4})226486(6,4)(4,{2})204464=F4(6,{2,4})(6,{2,5})(6,2)(2,{5})227092(6,5)(5,⑵)123951=F4(6,{2,5})(6,{3,4})(6,3)⑶{4})163955(6,4)(4,{3})202747=F4(6,{3,4})(6,{3,5})(6,3)(3,{5})165571(6,5)(5,{3})123446=F4(6,{3,5})(6,{4,5})(6,4)(4,{5})205373(6,5)⑸{4})124456=F4(6,{4,5})时3，()时，时1，3、伪代码和时间复杂度为方便计算，结点编号改为0到5.用一张二维表格表示，行数是，列数是。行号表示当前所在的结点i列号对应的五位二进制表示表示 的一个子集，表示在集合中，0表示不在集合中。例如： 表示的集合为 ， 表示空集再用一张的表格存储对应每个状态， 所做的最优决策，以便回溯找最短路线。伪代码：TSP(in，tiDn[t][n])输入个顶点的有向图，矩阵 是有向图的邻接矩阵是原图的邻接矩阵中存储阶段最短路径， 中存储阶段最优策略行数是，列数是找到从出发，遍历所有城市一次且仅一次再回到 的最短路径长度//并输出最短路径初始化第歹； ，①列行不在的二进制表示对应的集合中对于对应集合中的每一个点{计算 并选择使之取得最