文章目录
**TSP问题：**旅行家要旅行n个城市,每个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。
(
∞
3
6
7
5
∞
2
3
6
4
∞
2
3
7
5
∞
)
\begin{pmatrix}\infty\ \ 3\ \ 6\ \ 7\\5\ \ \infty\ \ 2\ \ 3\\6\ \ 4\ \ \infty\ \ 2\\3\ \ 7\ \ 5\ \ \infty \end{pmatrix}
⎝⎜⎜⎛∞ 3 6 75 ∞ 2 36 4 ∞ 23 7 5 ∞⎠⎟⎟⎞
1.动态规划法
对于图 G = ( V , E ) G=(V, E) G=(V,E)，假设从顶点 i i i出发，令 V ′ = V − i V^{'}=V-i V′=V−i，则 d ( i , V ′ ) d(i, V') d(i,V′)表示从顶点 i i i出发经过 V ′ V' V′中各个顶点一次且仅一次，最后回到出发点 i i i的最短路径长度， 显然，初始子问题是 d ( k , { } ) d(k, \{ \}) d(k,{})，即从顶点 i i i出发只经过顶点 k k k回到顶点 i i i。现在考虑原问题的一部分， d ( k , V ′ − { k } ) d(k, V'-\{k\}) d(k,V′−{k})表示从顶点k出发经过 V ′ − { k } V'-\{k\} V′−{k}中各个顶点一次且仅一次，最后回到出发点 i i i的最短路径长度，则：
KaTeX parse error: Unknown column alignment: d at position 24: … \begin{array} d̲d(k, \{ \ \}) =…
i i i为子问题起点， V ′ V^{'} V′里就是子问题经过的点， V ′ V^{'} V′里有几个点， m i n { } min\{\} min{}里就有几种情况
还不理解，就结合解题过程
解题过程：（括号内内容从下往上看，便于理解，即自底向上思考）
-
首先计算初始子问题，可以直接获得：
d ( 1 , { } ) = c 10 = 5 ( 1 → 0 ) d(1, \{ \ \})= c_{10} =5(1→0) d(1,{ })=c10=5(1→0)
d ( 2 , { } ) = c 20 = 6 ( 2 → 0 ) d(2, \{\ \})= c_{20} =6(2→0) d(2,{ })=c20=6(2→0)
d ( 3 , { } ) = c 30 = 3 ( 3 → 0 ) d(3, \{\ \})= c_{30} =3(3→0) d(3,{ })=c30=3(3→0)
-
再求解下一个阶段的子问题，有：
d ( 1 , { 2 } ) = c 12 + d ( 2 , { } ) = 2 + 6 = 8 ( 1 → 2 ) d(1, \{2\})= c_{12}+d(2, \{\ \})=2+6=8(1→2) d(1,{2})=c12+d(2,{ })=2+6=8(1→2)d ( 1 , { 3 } ) = c 13 + d ( 3 , { } ) = 3 + 3 = 6 ( 1 → 3 ) d(1, \{3\})= c_{13}+d(3, \{\ \})=3+3=6(1→3) d(1,{3})=c13+d(3,{ })=3+3=6(1→3)
d ( 2 , { 1 } ) = c 21 + d ( 1 , { } ) = 4 + 5 = 9 ( 2 → 1 ) d(2, \{1\})= c_{21}+d(1, \{\ \})=4+5=9(2→1) d(2,{1})=c21+d(1,{ })=4+5=9(2→1)
d ( 2 , { 3 } ) = c 23 + d ( 3 , { } ) = 2 + 3 = 5 ( 2 → 3 ) d(2, \{3\})= c_{23}+d(3, \{\ \})=2+3=5(2→3) d(2,{3})=c23+d(3,{ })=2+3=5(2→3)
d ( 3 , { 1 } ) = c 31 + d ( 1 , { } ) = 7 + 5 = 12 ( 3 → 1 ) d(3, \{1\})= c_{31}+d(1, \{\ \})=7+5=12(3→1) d(3,{1})=c31+d(1,{ })=7+5=12(3→1)
d ( 3 , { 2 } ) = c 32 + d ( 2 , { } ) = 5 + 6 = 11 ( 3 → 2 ) d(3, \{2\})= c_{32}+d(2, \{\ \})=5+6=11(3→2) d(3,{2})=c32+d(2,{ })=5+6=11(3→2)
(反过来思考，求从1出发，经过2、3，考虑到所有情况就是先要知道
从2出发，经过3；或从3出发，经过2。同理，另外两种情况一样考虑)
-
再求解下一个阶段的子问题，有：
d ( 1 , { 2 , 3 } ) = m i n { c 12 + d ( 2 , { 3 } ) , c 13 + d ( 3 , { 2 } ) } = m i n { 2 + 5 , 3 + 11 } = 7 ( 1 → 2 ) d(1, \{2, 3\})=min\{c_{12}+d(2,\{3\}), \ c_{13}+ d(3,\{2\})\}=min\{2+5, 3+11\}=7(1→2) d(1,{2,3})=min{c12+d(2,{3}), c13+d(3,{2})}=min{2+5,3+11}=7(1→2)
d ( 2 , { 1 , 3 } ) = m i n { c 21 + d ( 1 , { 3 } ) , c 23 + d ( 3 , { 1 } ) } = m i n { 4 + 6 , 2 + 12 } = 10 ( 2 → 1 ) d(2, \{1, 3\})=min\{c_{21}+d(1, \{3\}), \ c_{23}+d(3, \{1\})\}=min\{4+6, 2+12\}=10(2→1) d(2,{1,3})=min{c21+d(1,{3}), c23+d(3,{1})}=min{4+6,2+12}=10(2→1)
d ( 3 , { 1 , 2 } ) = m i n { c 31 + d ( 1 , { 2 } ) , c 32 + d ( 2 , { 1 } ) } = m i n { 7 + 8 , 5 + 9 } = 14 ( 3 → 2 ) d(3, \{1, 2\})=min\{c_{31}+d(1, \{2\}),\ c_{32}+ d(2, \{1\})\}=min\{7+8, 5+9\}=14(3→2) d(3,{1,2})=min{c31+d(1,{2}), c32+d(2,{1})}=min{7+8,5+9}=14(3→2)(反过来思考，求0经过1、2、3，考虑到所有情况就是先要知道
从1出发，经过2、3；或从2出发，经过1、3；或从3出发，经过1、2)
-
直到最后一个阶段，有：
d ( 0 , { 1 , 2 , 3 } ) = m i n { c 01 + d ( 1 , { 2 , 3 } ) , c 02 + d ( 2 , { 1 , 3 } ) , c 03 + d ( 3 , { 1 , 2 } ) } = m i n { 3 + 7 , 6 + 10 , 7 + 14 } = 10 ( 0 → 1 ) d(0, \{1, 2, 3\})=min\{c_{01}+ d(1, \{ 2, 3\}), \ c_{02}+ d(2, \{1, 3\}), c_{03}+ d(3, \{1, 2\})\}\\ =min\{3+7, 6+10, 7+14\}=10(0→1) d(0,{1,2,3})=min{c01+d(1,{2,3}), c02+d(2,{1,3}),c03+d(3,{1,2})}=min{3+7,6+10,7+14}=10(0→1)(反过来思考，这题就是求从0出发，经过中间点1、2、3)
所以，从顶点0出发的TSP问题的最短路径长度为10，再将状态进行回溯，得到最短路径是0→1→2→3→0。图示如下：
2.分支限界法
题目重抄一下： ( ∞ 3 6 7 5 ∞ 2 3 6 4 ∞ 2 3 7 5 ∞ ) \begin{pmatrix}\infty\ \ 3\ \ 6\ \ 7\\5\ \ \infty\ \ 2\ \ 3\\6\ \ 4\ \ \infty\ \ 2\\3\ \ 7\ \ 5\ \ \infty \end{pmatrix} ⎝⎜⎜⎛∞ 3 6 75 ∞ 2 36 4 ∞ 23 7 5 ∞⎠⎟⎟⎞
一般情况下，假设当前已确定的路径为U=(r1, r2, …, rk)，即路径上已确定了k个顶点，此时，该部分解的目标函数值的计算方法如下：
l b = ( 2 ∑ i = 1 k − 1 c [ r i ] [ r i + 1 ] + ∑ r i ∈ U r i 行 不 在 路 径 的 最 小 元 素 + ∑ r j ∉ U r j 行 最 小 的 两 个 元 素 ) / 2 lb=(2\sum_{i=1}^{k-1}{c[r_i][r_{i+1}]+\sum_{r_i\in U}{r_i行不在路径的最小元素}}+\sum_{r_j\notin U}{r_j行最小的两个元素})/2 lb=(2∑i=1k−1c[ri][ri+1]+∑ri∈Uri行不在路径的最小元素+∑rj∈/Urj行最小的两个元素)/2
（这个公式理解为：每个城市一进一出都取最小的路，每个城市都选，重复了一遍，所以除以二）
从根结点开始依次计算目标函数值加入待处理结点表中直至叶子结点
题解二叉树：
算法步骤：
-
根据限界函数计算目标函数的下界10；采用贪心法得到上界10；
（下界：由lb的求解公式，每个节点一进一出都取最小的，相加除以二，所以[(3+3)+(2+3)+(2+2)+(2+3)]/2=10；上界：由贪心法，每次都取最近的路径到下一节点，除了已经经过的节点，初1->2(3最小)，再2->3(2最小)，再3->4(2最小，且只能到4)，最后4->1(3)回起点，3+2+2+3=10）
-
计算根结点的目标函数值并加入待处理结点表PT；
-
循环直到某个叶子结点的目标函数值在表PT中取得极小值
3.1 i = 表PT中具有最小值的结点；
3.2 对结点i的每个孩子结点x执行下列操作：
3.2.1 估算结点x的目标函数值lb;
3.2.2 若(lb<=up)，则将结点x加入表PT中；
否则丢弃该结点； -
将叶子结点对应的最优值输出，回溯求得最优解的各个分量；
注意：无向图的TSP就直接对于每一个节点，取两个最小的无向路劲
例：下界用限界求得14，上界用贪心求得是16，其他步骤同上
3.回溯法
对于TSP问题，回溯法最后构造的是横向的排列树，如下，解的个数是n!
题目重抄一下： ( ∞ 3 6 7 5 ∞ 2 3 6 4 ∞ 2 3 7 5 ∞ ) \begin{pmatrix}\infty\ \ 3\ \ 6\ \ 7\\5\ \ \infty\ \ 2\ \ 3\\6\ \ 4\ \ \infty\ \ 2\\3\ \ 7\ \ 5\ \ \infty \end{pmatrix} ⎝⎜⎜⎛∞ 3 6 75 ∞ 2 36 4 ∞ 23 7 5 ∞⎠⎟⎟⎞
实际画出的解空间树就是上上图n=4的解空间树，边代表问题中的节点，每种情况都走一遍，但一种情况走不通时或不满足条件时，就换兄弟节点走。较为繁琐，略。