货郎担问数 高金玲
货郎担问题 高金玲
货郎担问题也叫推销商问题( traveling salesman problem), 其一般提法为:有n个城市,用1 n表示,城,之间 的距离为dn,有一个货郎从城1出发到其他城市一次且仅 次,最后回到城市1,怎样选择行走路线使总路程最短?
货郎担问题也叫推销商问题（traveling salesman problem）, 其一般提法为：有n个城市，用1，2，…，n表示，城i, j之间 的距离为 ，有一个货郎从城1出发到其他城市一次且仅一 次，最后回到城市1，怎样选择行走路线使总路程最短？ dij
动态规划解 阶段变量k:按所经过的城市个数划分阶段k,k=1,2,n-1 状态变量Sk:设第k阶段到达城市i时途中所经过的k个城市 集合为S,则Sk=(S,1)其中 S∈{2,3,…,-1,i+1…,n}|SF=k
动态规划解 阶段变量k：按所经过的城市个数划分阶段k, k=1,2,…,n-1. 状态变量 sk ：设第k 阶段到达城市i 时途中所经过的k个城市 集合为S，则 s (S,i) k = 其中 S {2,3, ,i −1,i +1, ,n} | S |= k
决策变量xk:第k阶段到达城市i的最短路线上邻接i的 前一个城市j。 例如x3({2,3,4,5)=3, 表示推销商从城1出发途径城市{2,3,4】到达城市5时, 须先途经城市{2,4}到达城市3,再去城市5
例如： ， 表示推销商从城1出发途径城市{2,3,4}到达城市5时， 须先途经城市{2,4}到达城市3，再去城市5。 决策变量 ：第k 阶段到达城市i 的最短路线上邻接i 的 前一个城市 。 k x j j = 2,3, ,n. x3 ({2,3,4},5) = 3
阶段指标函数a设从城市1出发,第k-1阶段到达到城市j 则城市与下一阶段(第k阶段)的目的地城市之间的距离为d 最优指标函数f(S,i):从城市1出发,经过S中k个城市,到 达城市的最短距离
阶段指标函数 : 设从城市1出发，第k-1阶段到达到城市j, 则城市j与下一阶段（第k阶段）的目的地城市i之间的距离为 d ji 最优指标函数 f k (S,i) ：从城市1出发，经过S中k个城市,到 达城市i的最短距离. d ji
则动态规划的顺序递推关系为 min&(s\j,j)+d f60(,)=d1,i=2,3,…,n,k=1,2,…,n-1 最后算出fn=1(N,1)2N={2,3,…,m},即为全程的最短距离同时 可得最优策略,即最优行走路线. 例1已知4个城市间距离如表1,求从城市1出发,经其与城 市一次且仅一次最优回到城市1的最短路与距离
则动态规划的顺序递推关系为: = = = − = − + ( , ) , 2,3, , , 1,2, , 1. ( , ) min{ ( \ , ) } 0 1 1 f i d i n k n f S i f S j j d i k j i j S k 最后算出 ,即为全程的最短距离,同时 可得最优策略,即最优行走路线. ( ,1), f n−1 N N = {2,3, ,n} 例1 已知 4个城市间距离如表1，求从城市1出发，经其与城 市一次且仅一次最优回到城市1的最短路与距离。 ( ,1), f n−1 N N ={2,3, ,n}
856 6085 7905 9780 解:由边界条件知 f6(01)=d1=0f6(,2)=ad12=66(,3)=d13=7 f6(,4)=d14=9
城 城 市 市 1 2 3 4 1234 0856 6085 7905 9780 解：由边界条件知： ( , 1 ) 0 f0 = d11 = f0 (, 2 ) = d12 = 6 f0 (, 3 ) = d13 = 7 f0 (, 4 ) = d14 = 9
856 6085 7905 9780 当k=1时,从城市1出发,经过1个城市到达城市的最短距离 为 f(S,2)=min{f0(,3)+a32,f0(4)+d4 min{7+8,9+5}=14, x2({4,2)=4 即从城市1出发,途经1个城市去城2,应先到4,再到2
城 城 市 市 1 2 3 4 1 2 3 4 0 8 5 6 6 0 8 5 7 9 0 5 9 7 8 0 当k=1时，从城市1出发，经过1个城市到达城市i的最短距离 为： ( ,2) min{ ( ,3) , ( ,4) } 1 0 32 0 d42 f S = f + d f + = min{ 7 +8,9 +5} =14, ({4},2) 4 * x2 = 即从城市1出发，途经1个城市去城2，应先到4，再到2
1234 0856 085 7905 9780 f(S,3)=mn{f0(0,2)+d23,f0(,4)+d43 mn{6+9,9+5}=14, ({4},3)=4 即从城市1出发,途经1个城市去城3,应先到4,再到3
城 城 市 市 1 2 3 4 1 2 3 4 0 8 5 6 6 0 8 5 7 9 0 5 9 7 8 0 ( ,3) min{ ( ,2) , ( ,4) } 1 0 23 0 d43 f S = f + d f + = min{ 6 +9,9 +5} =14, ({4},3) 4 * x2 = 即从城市1出发，途经1个城市去城3，应先到4，再到3
856 6085 7905 9780 f(S,4)=mn{f0(,2)+d24,J(,3)+d4 mn{6+7,7+8}=13, x2({2},4)=2 即从城市1出发,途经1个城市去城4,应先到2,再到4
城 城 市 市 1 2 3 4 1 2 3 4 0 8 5 6 6 0 8 5 7 9 0 5 9 7 8 0 ( ,4) min{ ( ,2) , ( ,3) } 1 0 24 0 d34 f S = f + d f + = min{ 6 + 7,7 +8} =13, ({2},4) 2 * x2 = 即从城市1出发，途经1个城市去城4，应先到2，再到4