货郎担问数 高金玲
货郎担问题 高金玲
货郎担问题也叫推销商问题( 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