动态规划解TSP问题.docx

用动态规划方法编程求解下面的问题：
某推销员要从城市v1 出发，访问其它城市v2，v3，…，v6 各一次且仅一次，最后返回v1。D为各城市间的距离矩阵。问：该推销员应如何选择路线，才能使总的行程最短？

1、变量设定
阶段k：已遍历过k个结点，k=1,2…6,7。
K=1表示刚从V1出发，k=7表示已回到起点V1
状态变量Xk=(i，Sk)：已遍历k个结点，当前位于i结点，还未遍历的结点集合为Sk。则X1=(1，{2,3,4,5,6})，X6=(i，Φ)，X7=(1，Φ)
决策变量Uk=(i，j)：已遍历k个结点，当前位于i结点，下一个结点选择j。
状态转移方程：Xk+1 = T(Xk，Uk) = (j，Sk-{j})
第k阶段的指标函数Vk = D[i,j]。
最优指标函数Fk(Xk) = Fk(i，Sk)：已遍历k个结点，当前从i结点出发，访问Sk中的结点一次且仅一次，最后返回起点V1的最短距离。
则Fk(i，Sk) = min{ D[i,j] + Fk+1(j，Sk-{j}) } 1≤k≤6
F7(X7) = F7(1，Φ) = 0

2、分析：

（1）k=6时，F6(i，Φ) = min{D[i,1] + F7(X7)} = D[i,1] i=2,3,4,5,6

X6=(i，Φ)
U6=(i，j)
X7=(1，Φ)
V6=D[i,j]
F7(1，Φ)
V6 + F7(X7)
(2，Φ)
(2，1)
(1，Φ)
12
0
12=F6(2,Φ)
(3，Φ)
(3，1)
(1，Φ)
23
0
23=F6(3,Φ)
(4，Φ)
(4，1)
(1，Φ)
34
0
34=F6(4,Φ)
(5，Φ)
(5，1)
(1，Φ)
45
0
45=F6(5,Φ)
(6，Φ)
(6，1)
(1，Φ)
56
0
56=F6(6,Φ)
即k=6时，对于每一种状态X6，都有唯一的决策U6。

（2）k=5时，F5(i，S5) = min{D[i,j] + F6(j，Φ)} i=2,3,4,5,6
X5=(i,S5)
U5=(i,j)
X6=(j, Φ)
V5=D[i,j]
F6(j,Φ)
V5 + F6(X6)
(2,{6}}
(2,6)
(6，Φ)
21
56
77=F5(2,{6})
(2,{5}}
(2,5)
(5，Φ)
25
45
70=F5(2,{5})
(2,{4}}
(2,4)
(4，Φ)
30
34
64=F5(2,{4})
(2,{3}}
(2,3)
(3，Φ)
18
23
41=F5(2,{3})
(3,{6})
(3,6)
(6，Φ)
15
56
71=F5(3,{6})
(3,{5})
(3,5)
(5，Φ)
10
45
55=F5(3,{5})
(3,{4})
(3,4)
(4，Φ)
5
34
39=F5(3,{4})
(3,{2})
(3,2)
(2，Φ)
19
12
31=F5(3,{2})
(4,{6})
(4,6)
(6，Φ)
16
56
72=F5(4,{6})
(4,{5})
(4,5)
(5，Φ)
8
45
53=F5(4,{5})
(4,{3})
(4,3)
(3，Φ)
4
23
27=F5(4,{3})
(4,{2})
(4,2)
(2，Φ)
32
12
44=F5(4,{2})
(5,{6})
(5,6)
(6，Φ)
18
56
74=F5(5,{6})
(5,{4})
(5,4)
(4，Φ)
10
34
44=F5(5,{4})
(5,{3})
(5,3)
(3，Φ)
11
23
34=F5(5,{3})
(5,{2})
(5,2)
(2，Φ)
27
12
39=F5(5,{2})
(6,{5})
(6,5)
(5，Φ)
12
45
57=F5(6,{5})
(6,{4})
(6,4)
(4，Φ)
20
34
54=F5(6,{4})
(6,{3})
(6,3)
(3，Φ)
16
23
39=F5(6,{3})
(6,{2})
(6,2)
(2，Φ)
22
12
34=F5(6,{2})
即k=时，对于每一种状态X5，都有唯一决策U5。

（3）k=4时，F4(i,S4) = min(D[i,j] + F5(j,S5) ) i=2,3,4,5,6
X4=(i,S4)
U4=(i,j)
X5=(j,S5)
V4=D[i,j]
F5(j,S5)
V4 + F5(j,S5)
(2,{3,4})
(2,3)
(3,{4})
18
39
57=F4(2,{3,4})
(2,4)
(4,{3})
30
27
57=F4(2,{3,4})
(2,{4,5})
(2,4)
(4,{5})
30
53
83
(2,5)
(5,{4})
25
44
69=F4(2,{4,5})
(2,{5,6})
(2,5)
(5,{6})
25
74
99
(2,6)
(6,{5})
21
57
78=F4(2,{5,6})
(2,{3,5})
(2,3)
(3,{5})
18
55
73
(2,5)
(5,{3})
25
34
59=F4(2,{3,5})
(2,{3,6})
(23)
(3,{6})
18
71
89
(2,6)
(6,{3})
21
39
60=F4(2,{3,6})
(2,{4,6})
(2,4)
(4,{6})
30
72
102
(2,6)
(6,{4})
21
54
75=F4(2,{4,6})
(3,{2,4})
(3,2)
(2,{4})
19
64
83
(3,4)
(4,{2})
5
44
49=F4(3,{2,4})
(3,{2,5})
(3,2)
(2,{5})
19
70
89
(3,5)
(5,{2})
10
39
49=F4(3,{2,5})
(3,{2,6})
(3,2)
(2,{6})
19
77
96
(3,6)
(6,{2})
15
34
49=F4(3,{2,6})
(3,{4,5})
(3,4)
(4,{5})
5
53
58
(3,5)
(5,{4})
10
44
54=F4(3,{4,5})
(3,{4,6})
(3,4)
(4,{6})
5
72
77
(3,6)
(6,{4})
15
54
69=F4(3,{4,6})
(3,{5,6})
(3,5)
(5,{6})
10
74
84
(3,6)
(6,{5})
15
57

72=F4(3,{5,6})
(4,{2,3})
(4,2)
(2,{3})
32
41
73
(4,3)
(3,{2})
4
31
34=F4(4,{2,3})
(4,{2,5})
(4,2)
(2,{5})
32
70
102
(4,5)
(5,{2})
8
39
47=F4(4,{2,5})
(4,{2,6})
(4,2)
(2,{6})
32
77
109
(4,6)
(6,{2})
16
34
50=F4(4,{2,6})
(4,{3,5})
(4,3)
(3,{5})
4
55
59
(4,5)
(5,{3})
8
34
42=F4(4,{3,5})
(4,{3,6})
(4,3)
(3,{6})
4
71
75
(4,6)
(6,{3})
16
39
55=F4(4,{3,6})
(4,{5,6})
(4,5)
(5,{6})
8
74
82
(4,6)
(6,{5})
16
57
73=F4(4,{5,6})
(5,{2,3})
(5,2)
(2,{3})
27
41
68
(5,3)
(3,{2})
11
31
42=F4(5,{2,3})
(5,{2,4})
(5,2)
(2,{4})
27
64

91
(5,4)
(4,{2})
10
44
54=F4(5,{2,4})
(5,{2,6})
(5,2)
(2,{6})
27
77
104
(5,6)
(6,{2})
18
34
52=F4(5,{2,6})
(5,{3,4})
(5,3)
(3,{4})
11
39
50
(5,4)
(4,{3})
10
27
37=F4(5,{3,4})
(5,{3,6})
(5,3)
(3,{6})
11
71
82
(5,6)
(6,{3})
18
39
57=F4(5,{3,6})
(5,{4,6})
(5,4)

(4,{6})
10
72
82
(5,6)
(6,{4})
18
54
72=F4(5,{4,6})
(6,{2,3})
(6,2)
(2,{3})
22
41
63
(6,3)
(3,{2})
16
31
47=F4(6,{2,3})
(6,{2,4})
(6,2)
(2,{4})
22
64
86
(6,4)
(4,{2})
20
44
64=F4(6,{2,4})
(6,{2,5})
(6,2)
(2,{5})
22
70
92
(6,5)
(5,{2})
12
39
51=F4(6,{2,5})
(6,{3,4})
(6,3)
(3,{4})
16
39
55
(6,4)
(4,{3})
20
27
47=F4(6,{3,4})
(6,{3,5})
(6,3)
(3,{5})
16
55
71
(6,5)
(5,{3})
12
34
46=F4(6,{3,5})
(6,{4,5})
(6,4)
(4,{5})
20
53
73
(6,5)
(5,{4})
12
44
56=F4(6,{4,5})

（4）k=3时，F3(i,S3) = min{D[i,j] + F4(j,S4)} i=2,3,4,5,6
X3i,S3)
U3=(i,j)
X4=(j,S4)
V3=D[i,j]
F4(j,S4)
V3 + F4(j,S4)
(2,{3,4,5})
(2,3)
(3,{4,5})
18
54
72
(2,4)
(4,{3,5})
30
42
72
(2,5)
(5,{3,4})
25
37
62=F3(2,{3,4,5})
(2,{3,4,6})
(2,3)
(3,{4,6})
18
69
87
(2,4)
(4,{3,6})
30
55
85
(2,6)
(6,{3,4})
21
47
68=F3(2,{3,4,6})
2,{3,5,6})
(2,3)
(3,{5,6})
18
72
90
(2,5)
(5,{3,6})
25
57
82
(2,6)
(6,{3,5})
21
46
67=F3(2,{3,5,6})
(2,{4,5,6})
(2,4)
(4,{5,6})
30
73
103
(2,5)
(5,{4,6})
25
72
97
(2,6)
(6,{4,5})
21
56
77=F3(2,{4,5,6})
(3,{2,4,5})
(3,2)
(2,{4,5})
19
69
88
(3,4)
(4,{2,5})
5
47
52=F3(3,{2,4,5})
(3,5)
(5,{2,4})
10
54
64
(3,{2,4,6})
(3,2)
(2,{4,6})
19
75
94
(3,4)
(4,{2,6})
5
50
55=F3(3,{2,4,6})
(3,6)
(6,{2,4})
15
64
79
(3,{2,5,6})
(3,2)
(2,{5,6})
19
78
97
(3,5)
(5,{2,6})
10
52
62=F3(3,{2,5,6})
(3,6)
(6,{2,5})
15
51
66
(3,{4,5,6})
(3,4)
(4,{5,6})
5
73
78
(3,5)
(5,{4,6})
10
72
82
(3,6)
(6,{4,5})
15
56
71=F3(3,{4,5,6})
(4,{2,3,5})
(4,2)
(2,{3,5})
32
59
91
(4,3)
(3,{2,5})
4
49
53
(4,5)
(5,{2,3})
8
42
50=F3(4,{2,3,5})
(4,{2,3,6})
(4,2)
(2,{3,6})
32
60
92
(4,3)
(3,{2,6})
4
49
53=F3(4,{2,3,6})

(4,6)
(6,{2,3})
16
47
63
(4,{2,5,6})
(4,2)
(2,{5,6})
32
78
110
(4,5)
(5,{2,6})
8
52
60=F3(4,{2,5,6})
(4,6)
(6,{2,5})
16
51
67
(4,{3,5,6})
(4,3)
(3,{5,6})
4
72
76
(4,5)
(5,{3,6})
8
57
65
(4,6)
(6,{3,5})
16
46
62=F3(4,{3,5,6})
(5,{2,3,4})
(5,2)
(2,{3,4})
27
57
84
(5,3)
(3,{2,4})
11
49
60
(5,4)
(4,{2,3})
10
34
44=F3(5,{2,3,4})
(5,{2,3,6})
(5,2)
(2,{3,6})
27
60
87
(5,3)
(3,{2,6})
11
49
60=F3(5,{2,3,6})
(5,6)
(6,{2,3})
18
47
65
(5,{2,4,6})
(5,2)
(2,{4,6})
27
75
102
(5,4)
(4,{2,6})
10
50
60=F3(5,{2,4,6})
(5,6)
(6,{2,4})
18
64
82
(5,{3,4,6})
(5,3)
(3,{4,6})
11
69
80
(5,4)
(4,{3,6})
10
55
65=F3(5,{3,4,6})
(5,6)
(6,{3,4})
18
47
65=F3(5,{3,4,6})
(6,{2,3,4})
(6,2)
(2,{3,4})
22
57
79
(6,3)
(3,{2,4})
16
49
65
(6,4)
(4,{2,3})
20
34
54=F3(6,{2,3,4})
(6,{2,3,5})
(6,2)
(2,{3,5})
22
59
81
(6,3)
(3,{2,5})
16
49
65
(6,5)
(5,{2,3})
12
42
54=F3(6,{2,3,5})
(6,{2,4,5})
(6,2)
(2,{4,5})
22
69
91
(6,4)
(4,{2,5})
20
47
67
(6,5)
(5,{2,4})
12
54
66=F3(6,{2,4,5})
(6,{3,4,5})
(6,3)
(3,{4,5})
16
54
70
(6,4)
(4,{3,5})
20
42
62
(6,5)
(5,{3,4})
12
37
49=F3(6,{3,4,5})

（5）k=2时，F2(i,S2) = min{D[i,j] + F3(j,S3)} i=2,3,4,5,6
X2=(i,S2)
U2=(i,j)
X3=(j,S3)
V2=D[i,j]
F3(j,S3)
V2 + F3(j,S3)
(2,{3,4,5,6})
(2,3)
(3,{4,5,6})
18
71
89
(2,4)
(4,{3,5,6})
30
62
92
(2,5)
(5,{3,4,6})
25
65
90
(2,6)
(6,{3,4,5})
21
49
70=F2(2,{3,4,56})
(3,{2,4,5,6})
(3,2)
(2,{4,5,6})
19
77
96
(3,4)
(4,{2,5,6})
5
60
65=F2(3,{2,4,5,6})
(3,5)
(5,{2,4,6})
10
60
70
(3,6)
(6,{2,4,5})
15
66
81
(4,{2,3,5,6})
(4,2)
(2,{3,5,6})
32
67
99
(4,3)
(3,{2,5,6})
4
62
66=F2(4,{2,3,5,6})
(4,5)
(5,{2,3,6})
8
60
68
(4,6)
(6,{2,3,5})
16
54
70
(5,{2,3,4,6})
(5,2)
(2,{3,4,6})
27
68
95
(5,3)
(3,{2,4,6})
11
55
66
(5,4)
(4,{2,3,6})
10
53
63=F2(5,{2,3,4,6})
(5,6)
(6,{2,3,4})
18
54
72
(6,{2,3,4,5})
(6,2)
(2,{3,4,5})
22
62
84
(6,3)
(3,{2,4,5})
16
52
68
(6,4)
(4,{2,3,5})
20
50
70
(6,5)
(5{2,3,4})
12
44
56=F2(6,{2,3,4,5})

（6）k=1时，F1(1,S1) = min{D[1,j] + F2(j,S2)}
X1=(1,S1)
U1=(1,j)
X2=(j,S2)
V1=D[1,j]
F2(j,S2)
V1 + F2(j,S2)
(1,{2,3,4,5,6})
(1,2)
(2,{3,4,5,6})
10
70
80=F1(1,{2,3,4,5,6})
(1,3)
(3,{2,4,5,6})
20
65
85
(1,4)
(4,{2,3,5,6})
30
66
96
(1,5)
(5,{2,3,4,6})
40
63
103
(1,6)
(6,{2,3,4,5})
50
56
106

3、伪代码和时间复杂度
为方便计算，结点编号改为0到5.
(1)用一张二维表格F[][]表示F(i,Sk)，行数是n，列数是2n-1。
(2)行号表示当前所在的结点i。
列号对应的五位二进制表示表示{V5,V4,V3,V2,V1}的一个子集，1表示在集合中，0表示不在集合中。
例如：00110表示的集合为{V3,V2}，00000表示空集
(3)再用一张n*2n-1的表格M[][]存储对应每个状态(i，Sk)所做的最优决策，以便回溯找最短路线。

伪代码
TSP(int D[][]，int n)
//输入n个顶点的有向图，矩阵D[][]是有向图的邻接矩阵
//D[][]是原图的邻接矩阵
//F[][]中存储阶段最短路径，M[][]中存储阶段最优策略, 行数是n，列数是2n-1
//找到从V0出发，遍历所有城市一次且仅一次再回到V0的最短路径长度
//并输出最短路径
{
for(i=0; iif(j不在i的二进制表示对应的集合中)
对于i对应集合中的每一个点k
{
计算D[j][k]+F[k][i-2k-1]并选择使之取得最小值min的k*;
F[k][i] = min ; //填表，记录阶段最优值
M[k][i] = k* ; //记录每个状态的最优决策k*
}

//i==2n-1-1 时
对于i中的每个节点k
计算D[0][k] + F[k][ [i-2k-1]并选择使之取得最小值min的k*
F[0][ 2n-1-1] = min; //总最短路径
M[0][ 2n-1-1] = k*;

//回溯查表M输出最短路径
输出V0
for(2n-1-1,j=0; i>0; )
{
j = M[j][i];//下一步去往哪个结点
i = i –2j-1;//从i表示的集合中删除j
输出Vj
}
}

考虑算法中所做的加法和比较次数:
k=2n-1kk-1n-1k + (n-1) = (n-1)(n-2)2n-3 + (n-1) = O(n22n)