f2(2,[3,4])min f1(3,4)d32, f1(4,3)d42
min 148,15520 p2(2,3,4)4 f2(3,2,4)min 149,13518 p2(3,2,4)4 f2(4,2,3)min 157,15822 p2(4,2,3)2
.
6
当k=3时，即从v1城开始，中间经过三个城市(顺序随便)回 到v1城的最短距离是：
.
7
旅行商问题应用
• 物资运输路线问题 • 自动焊机割咀路线问题 • 管道铺设路线问题
.
8
课堂练习
• 求解四个城市的旅行商问题。问应如何选择行进路线，使 从v1的出发到其他城市一次且仅一次，再回到v1的总路 程最短？
vi vj
1
2
3
4
1
0
3
6
7
2
5
0
2
Байду номын сангаас
3
3
6
4
0
2
4
3
7
5
0
.
9
作业
• 求解5个城市的旅行商问题。
第四讲 旅行商问题
讲授：白丹宇
.
1
问题描述
货郎担问题在运筹学里是一个著名的命题。有一个串村 走户卖货郎，他从某个村庄出发，通过若干个村庄一次且 仅一次，最后仍回到原出发的村庄。问应如何选择行走路 线，能使总的行程最短。类似的问题有旅行路线问题，应 如何选择行走路线，使总路程最短或费用最少等。
现在把问题一般化。设有n个城市，以v1，v2，…，vn表 示之。dij表示从vi城到vj城的距离。一个推销员从城市v1 出发到其他每个城市去一次且仅仅是一次，然后回到城
当k=1时，即从v1城开始，中间经过一个城市到达vi城的最 短距离是：
f1(2,3) f0(3,)d32 7815 f1(2,4) f0(4,)d42 9514 f1(3,2)6915 f1(3,4)9514 f1(4,2)6713 f1(4,3)7815
.
5
当k=2时，即从v1城开始，中间经过二个城市(它们的顺序随 便)到达vi城的最短距离是：
3
例： 求解四个城市旅行推销员问题，其距离矩阵 如表所示。当推销员从v1城出发，经过每个城市一 次且仅一次，最后回到v1城，问按怎样的路线走， 使总的行程距离最短。
vj
vi
1
2
1
0
6
2
8
0
3
5
8
4
6
5
.
3
7 9 0 5
4
解: 由边界条件可知：
f 0 ( 2 ,) d 1 2 6 , f 0 ( 3 ,) d 1 3 7 , f 0 ( 4 ,) d 1 4 9
• 最有指标函数fk(i, S)为从V1出发经由k个城镇的S到Vi的最短距 离
• 决策变量Pk(i, S)表示：从V1经由k个中间城镇的S到Vi城镇的最 短路线上邻接Vi的前一个城镇，则动态规划的顺序递推关系为
fk(i,S)mjisnfk1(j,S\j)dj i
f0(i,)d1i 为空集
(k1,2,L,n1， . i2,3,L,n)
市v1。问他如何选择行走的路线，使总的路程最短。这 个问题属于组合最优化问题，当n不太大时，利用动态规
划方法求解是很方便的。
.
2
动态规划模型
• 设S表示从V1到Vi中间所有可能经过的城市集合，S实际上是包 含除V1与Vi两个点之外其余点的集合，但S中的点的个数要随阶 段数改变。
• 状态变量（i，S）表示：从V1点出发，经过S集合中所有点一次 最后到达到Vi
f3 ( 1 , 2 ， 3 ， 4 ) m in f2 ( 2 , 3 ,4 ) d 2 1 ,f2 ( 3 , 2 ,4 ) d 3 1 ,f2 ( 4 , 2 ,3 ) d 4 1
m in 2 0 8 ,1 8 5 ,2 2 6 2 3
p3(1,2,3,4)2
由此可知，推销员的最短旅行路线是1→2→4→3→1，最短 总距离为23。
12345
101234 0000
210132
2
805
329051
3
0
4 3 3 4 0. 8
10