使用动态规划的方式求解TSP旅行推销员问题

一、问题描述：

给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

二、例题

             图 1

             图 2

有向图图1可以用图2的矩阵进行表示。

现在要求从城市 0 出发，访问城市 1，城市 2，城市 3 （需要访遍每一座城市），

最后回到城市 0 的最短路径

三、基础知识讲解

1、首先定义一项规则

i -> V’ -> 0 = num ①

可以记为 d(i,V’) = num ②

其中 V’ = {i1, i2, …, ik} k = 1,2,3,…,n 表示需要经过的点集

① 表示，从点 i 出发，经果点集 V’，最后到达起始点 0 的最短路径为 num

②是简洁的表示形式

如 3 -> {2, 3} -> 0 10

所代表的意思是，从点 3 出发，经过点 2，点3 最后到达起始点 0 的最短路径为 10

也可以表示为 d(3,{2,3}) = 10

四、例题分析

1、该题需要进行逆过程思考, 接下来将会对下列的过程进行讨论：

**1、不经过任何点集**

    1 -> {} -> 0    记为 d(1,{})    (4.1.1)
    2 -> {} -> 0    记为 d(2,{})    (4.1.2)
    3 -> {} -> 0    记为 d(3,{})    (4.1.3)

**2、经过 1 条点集**

    2 -> {1} -> 0    记为 d(2,{1})    (4.1.4)
    3 -> {1} -> 0    记为 d(3,{1})    (4.1.5)

    1 -> {2} -> 0    记为 d(1,{2})    (4.1.6)
    3 -> {2} -> 0    记为 d(3,{2})    (4.1.7)

    1 -> {3} -> 0    记为 d(1,{3})    (4.1.8)
    2 -> {3} -> 0    记为 d(2,{3})    (4.1.9)

**3、经过 2 条点集**

    1 -> {2, 3} -> 0    记为 d(1,{2, 3})    (4.1.10)
    2 -> {1, 3} -> 0    记为 d(2,{1, 3})    (4.1.11)
    3 -> {1, 2} -> 0    记为 d(3,{1, 2})    (4.1.12)

**4、经过 3 条点集**

    0 -> {1, 2, 3} -> 0    (4.1.13) d(0,{1, 2, 3}) (4.1.13)

2、对 1 内容进行解释

由于最终要回到起点 0 点，在我们不经过任何点集时，有 1 点，2 点，3 点，可以回到 0 点，

所以有如下解释

(4.1.1) 表示，从 1 点不经过任何点集，到达起始点 0 点；
(4.1.2) 表示，从 2 点不经过任何点集，到达起始点 0 点；
(4.1.3) 表示，从 3 点不经过任何点集，到达起始点 0 点；

(4.1.4) 表示，从 2 点经过点集 1，到达起始点 0 点；
(4.1.5) 表示，从 3 点经过点集 1，到达起始点 0 点；

(4.1.6) 表示，从 1 点经过点集 2，到达起始点 0 点；
(4.1.7) 表示，从 3 点经过点集 2，到达起始点 0 点；

(4.1.8) 表示，从 1 点经过点集 3，到达起始点 0 点；
(4.1.9) 表示，从 2 点经过点集 3，到达起始点 0 点；

(4.1.10) 表示，从 1 点经过点集 2，3，到达起始点 0 点；
(4.1.11) 表示，从 2 点经过点集 1，3，到达起始点 0 点；
(4.1.12) 表示，从 3 点经过点集 1，2，到达起始点 0 点；

(4.1.13) 表示，从起始 0 点经过点集1， 2，3，到达起始点 0 点；

显然 (4.1.13) 是我们需要求解的结果,

现在还不适合求解最短路径，因此没有给出任何 ① 中提到的 num 的信息

3、对(4.1.x)的数据进行分解

**1、不经过任何点集**

    1 -> {} -> 0    (4.1.1)
    2 -> {} -> 0    (4.1.2)
    3 -> {} -> 0    (4.1.3)

**2、经过 1 条点集**

    2 -> {1} -> 0    (4.1.4)
        2 -> 1 -> {} -> 0    (4.1.4.1)
    3 -> {1} -> 0    (4.1.5)
        3 -> 1 -> {} -> 0    (4.1.5.1)

    1 -> {2} -> 0    (4.1.6)
        1 -> 2 -> {} -> 0    (4.1.6.1)
    3 -> {2} -> 0    (4.1.7)
        3 -> 2 -> {} -> 0    (4.1.7.1)

    1 -> {3} -> 0    (4.1.8)
        1 -> 3 -> {} -> 0    (4.1.8.1)
    2 -> {3} -> 0    (4.1.9)
        2 -> 3 -> {} -> 0    (4.1.9.1)

**3、经过 2 条点集**

    1 -> {2, 3} -> 0    (4.1.10)
        1 -> 2 -> {3} -> 0    (4.1.10.1)
        1 -> 3 -> {2} -> 0     (4.1.10.2)

    2 -> {1, 3} -> 0    (4.1.11)
        2 -> 1 -> {3} -> 0    (4.1.11.1)
        2 -> 3 -> {1} -> 0    (4.1.11.2)

    3 -> {1, 2} -> 0    (4.1.12)
        3 -> 1 -> {2} -> 0    (4.1.12.1)
        3 -> 2 -> {1} -> 0    (4.1.12.2)

**4、经过 3 条点集**

    0 -> {1, 2, 3} -> 0    (4.1.13)
        0 -> 1 -> {2,3} -> 0    (4.1.13.1)
        0 -> 2 -> {1,3} -> 0    (4.1.13.2)
        0 -> 3 -> {1,2} -> 0    (4.1.13.3)

4、数据分解带来的好处

为什么要对上述数据进行分解呢，因为分解之后我们就可以利用上面已经产生的数据，简化计算。

有了 3 的分解过程，我们就可以求最短路径了，

由图 2 可知，C 表示各个点的路径长度，即 C[i][j] 表示从 i 点到达 j 点的路径长度。

由 ② 可知，d(i,V’) 表示，从点 i 出发，经过点集 V’ 到达零的最短路径

现在对上述的分解过程进行第一部分讲解,
第一部
1、不经过任何点集

    1 -> {} -> 0    (4.1.1)
    2 -> {} -> 0    (4.1.2)
    3 -> {} -> 0    (4.1.3)

对于这三项不用计算，直接求最短路径

(4.1.1) 表示，从 1 点不经过任何点集，到达起始点 0 点，即 1 到 0 点的距离，可以用矩阵
C[1][0] = 5
(4.1.2) 表示，从 2 点不经过任何点集，到达起始点 0 点,即 2 到 0 点的距离，可以用矩阵
C[2][0] = 6
(4.1.3) 表示，从 3 点不经过任何点集，到达起始点 0 点，即 3 到 0 点的距离，可以用矩阵
C[2][0] = 3

整理得，

**1、不经过任何点集**

1 -> {} -> 0    记为 d(1,{}) = 5        (4.4.1)
2 -> {} -> 0    记为 d(2,{}) = 6        (4.4.2)
3 -> {} -> 0    记为 d(3,{}) = 3        (4.4.3)

进行第二部分的讲解

第二部分
    **2、经过 1 条点集**

        2 -> {1} -> 0    (4.1.4)
            2 -> 1 -> {} -> 0    (4.1.4.1)
        3 -> {1} -> 0    (4.1.5)
            3 -> 1 -> {} -> 0    (4.1.5.1)

        1 -> {2} -> 0    (4.1.6)
            1 -> 2 -> {} -> 0    (4.1.6.1)
        3 -> {2} -> 0    (4.1.7)
            3 -> 2 -> {} -> 0    (4.1.7.1)

        1 -> {3} -> 0    (4.1.8)
            1 -> 3 -> {} -> 0    (4.1.8.1)
        2 -> {3} -> 0    (4.1.9)
            2 -> 3 -> {} -> 0    (4.1.9.1)

对于 (4.1.4.1) 可以看成两部分，第一部分时 2 -> 1，第二部分是 1 -> {} -> 0，

即先从点 2 出发然后经过点 1，然后经过空点集，到达 0 点

第一部分为矩阵 C[2][1] = 4 的值

而第二部分也已经求解，即 (4.4.1) 的结果 d(1,{}) = 5

所以 2 -> {1} -> 0 => 2 -> 1 -> {} -> 0 => C[2][1] + d(1,{}) = 4 + 5 = 9

对于 (4.1.5.1) 可以看成两部分，第一部分时 3 -> 1，第二部分是 1 -> {} -> 0，

即先从点 3 出发然后经过点 1，然后经过空点集，到达 0 点

第一部分为矩阵 C[3][1] = 7 的值

可以发现第二部分已经求解，即 (4.4.1) 的结果 d(1,{}) = 5

所以 3 -> {1} -> 0 => 3 -> 1 -> {} -> 0 => C[3][1] + d(1,{}) = 7 + 5 = 12

同理，可得其他;

整理得，

(4.1.4.1) : C[2][1] + d(1,{}) = 4 + 5 = 9    记为 d(2,{1}) = 9    (4.4.4)
(4.1.5.1) : C[3][1] + d(1,{}) = 7 + 5 = 12    记为 d(3,{1}) = 12    (4.4.5)
(4.1.6.1) : C[1][2] + d(2,{}) = 2 + 6 = 8    记为 d(1,{2}) = 8    (4.4.6)
(4.1.7.1) : C[3][2] + d(2,{}) = 5 + 6 = 11    记为 d(3,{2}) = 11    (4.4.7)
(4.1.8.1) : C[1][3] + d(3,{}) = 3 + 3 = 6    记为 d(1,{3}) = 6    (4.4.8)
(4.1.9.1) : C[2][3] + d(3,{}) = 2 + 3 = 5    记为 d(2,{3}) = 5    (4.4.9)

进行第三部分得讲解

第三部分
    **3、经过 2 条点集**

        1 -> {2, 3} -> 0    (4.1.10)
            1 -> 2 -> {3} -> 0    (4.1.10.1)
            1 -> 3 -> {2} -> 0     (4.1.10.2)

        2 -> {1, 3} -> 0    (4.1.11)
            2 -> 1 -> {3} -> 0    (4.1.11.1)
            2 -> 3 -> {1} -> 0    (4.1.11.2)

        3 -> {1, 2} -> 0    (4.1.12)
            3 -> 1 -> {2} -> 0    (4.1.12.1)
            3 -> 2 -> {1} -> 0    (4.1.12.2)

1 -> {2, 3} -> 0 ，表示从 点 1 出发，经过点集 2 3，然后达到 0，得最短路径

此时我们有两种方式可以实现该过程，即上式得 (4.1.10.1) 和 (4.1.10.2)

(4.1.10.1) 表示先从点 1 出发，到达点 2，然后经过点集 3，最后到达起始点 0

(4.1.10.2) 表示先从点 1 出发，到达点 3，然后经过点集 2，最后到达起始点 0

因为要实现 1 -> {2, 3} -> 0 这个过程，有两种方式，而我们要求的是最短路径，

所以要求得 1 -> {2, 3} -> 0 最短路径为 1 -> 2 -> {3} -> 0 和 1 -> 3 -> {2} -> 0 得最小值

对于 (4.1.10.1) 可以分解为两个过程，第一个过程为 1 -> 2，第二个过程为 2 -> {3} -> 0

即先从点 1 出发，经过点 2，在经过点集 3，最后到达起始点 0

第一部分为矩阵 C[1][2] = 2 的值

而第二部分也已经求解，即 (4.4.9) 的结果 d(2,{3}) = 5

所以 1 -> 2 -> {3} -> 0 = C[1][2] + d(2,{3}) = 2 + 5 = 7

对于 (4.1.10.1) 可以分解为两个过程，第一个过程为 1 -> 3，第二个过程为 3 -> {2} -> 0

即先从点 1 出发，经过点 2，在经过点集 3，最后到达起始点 0

第一部分为矩阵 C[1][3] = 3 的值

而第二部分也已经求解，即 (4.4.7) 的结果 d(3,{2}) = 11

所以 1 -> 3 -> {2} -> 0 = C[1][3] + d(3,{2}) = 3 + 11 = 14

所以 1 -> {2, 3} -> 0 需要取两者得最小值为 min(7, 14) = 7

同理，可得其他;

整理得，

(4.1.10.1) : C[1][2] + d(2,{3}) = 2 + 5 = 7    
(4.1.10.2) : C[1][3] + d(3,{2}) = 3 + 11 = 14
(4.1.11.1) : C[2][1] + d(1,{3}) = 4 + 6 = 10
(4.1.11.2) : C[2][3] + d(3,{1}) = 2 + 12 = 14
(4.1.12.1) : C[3][1] + d(1,{2}) = 7 + 8 = 15
(4.1.12.2) : C[3][2] + d(2,{1}) = 5 + 9 = 14
取最小值得
(4.1.10) : min((4.1.10.1),(4.1.10.2)) = 7         记为 d(1,{2,3}) = 7        (4.4.10)
(4.1.11) : min((4.1.11.1),(4.1.11.2)) = 10        记为 d(2,{1,3}) = 10        (4.4.11)
(4.1.12) : min((4.1.12.1),(4.1.12.2)) = 14        记为 d(3,{1,2}) = 14        (4.4.12)

进行第四部分的讲解

第四部
    **4、经过 3 条点集**
        0 -> {1, 2, 3} -> 0    (4.1.13)
            0 -> 1 -> {2,3} -> 0    (4.1.13.1)
            0 -> 2 -> {1,3} -> 0    (4.1.13.2)
            0 -> 3 -> {1,2} -> 0    (4.1.13.3)

0 -> {1, 2, 3} -> 0，表示从点 0 出发，经过点集 1，2，3 最终回到出发点 0，

这就是我们要求的最短路径(因为 TSP 算法要求我们必须从 0 出发，经过多有得点，最后再回到 0 点)

此时我们有三种方式可以实现该过程，即上式得 (4.1.13.1),(4.1.13.2) 和 (4.1.13.3)

(4.1.13.1) 表示先从点 0 出发，到达点 1，然后经过点集 2 3，最后到达起始点 0；

(4.1.13.2) 表示先从点 0 出发，到达点 2，然后经过点集 1 3，最后到达起始点 0；

(4.1.13.2) 表示先从点 0 出发，到达点 3，然后经过点集 1 2，最后到达起始点 0；

因为要实现 0 -> {1, 2, 3} -> 0 这个过程，有三种方式，而我们要求的是最短路径，

所以要求得 0 -> {1, 2, 3} -> 0 最短路径为

0 -> 1 -> {2,3} -> 0，0 -> 2 -> {1,3} -> 0 和 0 -> 3 -> {1,2} -> 0 得最小值

对于 (4.1.13.1) 可以分解为两个过程，第一个过程为 0 -> 1，第二个过程为 1 -> {2，3} -> 0

即先从点 0 出发，经过点 1，在经过点集 2 3，最后到达起始点 0

第一部分为矩阵 C[0][1] = 3 的值

而第二部分也已经求解，即 (4.4.10) 的结果 d(1,{2,3}) = 7

所以 1 -> 2 -> {3} -> 0 = C[0][1] + d(1,{2,3}) = 3 + 7 = 10

对于 (4.1.13.2) 可以分解为两个过程，第一个过程为 0 -> 2，第二个过程为 2 -> {1，3} -> 0

即先从点 0 出发，经过点 2，在经过点集 1 3，最后到达起始点 0

第一部分为矩阵 C[0][2] = 6 的值

而第二部分也已经求解，即 (4.4.11) 的结果 d(2,{1,3}) = 10

所以 1 -> 2 -> {3} -> 0 = C[0][2] + d(2,{1,3}) = 6 + 10 = 16

对于 (4.1.13.3) 可以分解为两个过程，第一个过程为 0 -> 3，第二个过程为 3 -> {1，2} -> 0

即先从点 0 出发，经过点 3，在经过点集 1 2，最后到达起始点 0

第一部分为矩阵 C[0][3] = 7 的值

而第二部分也已经求解，即 (4.4.12) 的结果 d(3,{1,2}) = 14

所以 1 -> 2 -> {3} -> 0 = C[0][3] + d(3,{1,2}) = 7 + 14 = 21

整理得，

(4.1.13.1) : C[0][1] + d(1,{2,3}) = 3 + 7 = 10 
(4.1.13.2) : C[0][2] + d(2,{1,3}) = 6 + 10 = 16
(4.1.13.3) : C[0][3] + d(3,{1,2}) = 7 + 14 = 21
取最小值得
(4.1.13) ： min((4.1.13.1),(4.1.13.2),(4.1.13.3)) = 10 记为 d(0,{1,2,3}) = 10(4.4.13)

5、整理数据

整理上方数据我们可以得到图 3 所示得表格，使用 dp 来表示这个二维数组

             
    图 3

其中 d[i][j] 表示点 i 通过 j 所表示得点集，然后回到 0 所得到的最短路径

dp[1][6](两个下标都是从 0 开始) 其中 1 表示节点 1 ，6 表示点集{2，3}

dp[1][6] 表示从点 1 出发，经过点集 {2,3} 最后到达 0 求得的最短路径为 7

五、分析过程存在的难点

1、如何表示 j 所代表的数据

j 所代表的数据即,{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}

要想表示上边的点集，我们需要使用二进制形式表示，由于点集最多有三个点，

可以使用三位二进制来表示，具体表示方法为二进制从低位到高位依次表示 1 2 3，

            图 4

第 1 行第 2 列表示每位所代表的数字(行列下标都是从 1 开始)，

如第 5 行(下标从 1 开始) 0 1 1，从右到左以此表示 1 存在，2 存在，3不存在，

所以 011 表示点集{1,2}

这样我们就能用数字表示点集了

由于点集出现的顺序和图 3 的 j 所代表的顺序是不一致的，

所以需要重新绘制图 3 得到图 5，如下

                              图 5

该图也将那些需要赋值为空的数据，赋值为 ∞，表示该点不可达,

我们将在下面介绍如何找到这些点

六、对图中数据生成的过程进行说明

1、必备基础知识 (以下所有的讨论都是基于图 5 红框中的数据，行列下标都从 0 开始)##

1、可以通过整数来表示一个点集

在图 4 中，可以通过一个整数找到对应的点集，对应关系如下

0 = 000 -> {}        1 = 001 -> {1}
2 = 010 -> {2}        3 = 011 -> {1,2}
4 = 100 -> {3}        5 = 101 -> {1,3}
6 = 110 - > {2,3}    7 = 111 -> {1,2,3}

这说明我可以通过一个整数，找到对应的点集
例如 整数 6 就可以找到点集 {2,3}

同样，给定一个点集，也可以找到他在数组中对应的横坐标
如点集 {1,3} 二进制表示形式为 101 = 5,所以他在二维数组的横坐标为 5

2、dp[i][j] = num 表示的是什么

dp[i][j] = num 表示的是从点 i 出发，经过 j 所表示的点集 V’，

到达 0 的最短距离为 num，即 d(i,V’) 的最短距离为 num

如 d[3][3] = 14 表示从 3 出发，经过 3 所表示的点集{1,2}，

到达 0 的最短距离为 14，即 d(3,{1,2}) = 14

3、如何判断整数 num 的二进制表示形式的第 j 位上为 1（以8位二进制数为例）

通过 num & 0000 0001 
    结果为 0000 0001(2的0次方) num 的第 1 位上存在 1，为 0 不存在
通过 num & 0000 0010 
    结果为 0000 0010(2的1次方) num 的第 2 位上存在 1，为 0 不存在
通过 num & 0000 0100 
    结果为 0000 0100(2的2次方) num 的第 3 位上存在 1，为 0 不存在
通过 num & 0000 1000 
    结果为 0000 1000(2的3次方) num 的第 4 位上存在 1，为 0 不存在
通过 num & 0001 0000 
    结果为 0001 0000(2的4次方) num 的第 5 位上存在 1，为 0 不存在
通过 num & 0010 0000 
    结果为 0010 0000(2的5次方) num 的第 6 位上存在 1，为 0 不存在
通过 num & 0100 0000 
    结果为 0100 0000(2的6次方) num 的第 7 位上存在 1，为 0 不存在
通过 num & 1000 0000 
    结果为 1000 0000(2的7次方) num 的第 8 位上存在 1，为 0 不存在

例如对于 252 二进制为 1010 1010

第 1 位    1010 1010 & 0000 0001 = 0000 0000
第 2 位    1010 1010 & 0000 0010 = 0000 0010
第 3 位    1010 1010 & 0000 0100 = 0000 0000
第 4 位    1010 1010 & 0000 1000 = 0000 1000
第 5 位    1010 1010 & 0001 0000 = 0000 0000
第 6 位    1010 1010 & 0010 0000 = 0010 0000
第 7 位    1010 1010 & 0100 0000 = 0000 0000
第 8 位    1010 1010 & 1000 0000 = 1000 0000
可以得出 252 这个整数的第 2，4，6，8 位上面各存在一个 1
                     而 1，3，5，7 位上面没有 1，与 252 的二进制表示形式相符

4、第 j 位上的 1 代表的是哪个点

直接说结论，第 j 位上的 1 代表的是 j 这个点
因为从左到右以此表示的点为 1 2 3 4 ……

例如对于 252 二进制为 1010 1010

1010 1010 第 2 位存在 1 ，代表点 2
1010 1010 第 4 位存在 1 ，代表点 4
1010 1010 第 6 位存在 1 ，代表点 6
1010 1010 第 8 位存在 1 ，代表点 8

5、如何判断点 k 是否存在于点集之中

还是直接说结论，若点集的整数表示形式为 pointNum,则点 k 存在于点集中，

必有如下规则 pointNum & 2^(k - 1) = 2^(k - 1)

例如对于 252 二进制为1010 1010

1010 1010 & 0000 0010 = 0000 0010 表示点 2 在点集中(0000 0010 = 2^(2 - 1))
1010 1010 & 0000 1000 = 0000 1000 表示点 4 在点集中(0000 1000 = 2^(4 - 1))
1010 1010 & 0010 0000 = 0010 0000 表示点 6 在点集中(0010 0000 = 2^(6 - 1))
1010 1010 & 1000 0000 = 1000 0000 表示点 8 在点集中(1000 0000 = 2^(8 - 1))

6、从点集中取出一个点后形成一个新的点集

可以先通过 5 判断在点集中是否存在一个点，若存在，则移除该点，

可以通过如下的方法从点集中移除该点

选择点集 V’ 用整数 pointNum 表示，判断一个点是否在点集里面，若存在，取出该点，

获得新的点集 V’’ 用整数 newPointNum 表示，获取一个新的点集的过程如下

1、
    判断点集中是否存在 1 点
    pointNum & 0000 0001(2的 0 次方) = 0000 0001
    获取新的点集(若点 1 存在点集中，则执行下列步骤，否则判断点 2)
    pointNum - 0000 0001 = newPointNum
    newPointNum 就是新的点集的整数表示形式
2、
    判断点集中是否存在 2 点
    pointNum & 0000 0010(2的 1 次方) = 0000 0010
    获取新的点集(若第 2 位上存在 1，则执行下列步骤，否则判断点 3)
    pointNum - 0000 0010 = newPointNum
    newPointNum 就是新的点集的整数表示形式

                    ………………

i、
    判断点集中是否存在 i 点
    pointNum & 1(i 个 0)(2的 i - 1 次方) = 1(i 个 0)
    获取新的点集(若第 i 位上存在 1，则执行下列步骤，否则判断点 i + 1)
    pointNum - 1(i 个 0) = newPointNum
    newPointNum 就是新的点集的整数表示形式

例如对于 252 二进制为 1010 1010

1010 1010 & 0000 0001 = 0000 0000 第 1 位没有 1
1010 1010 & 0000 0010 = 0000 0010 第 2 位存在 1
    1010 1010 - 0000 0010 = 1010 1000 新点集 1010 1000

1010 1010 & 0000 0100 = 0000 0000 第 3 位没有 1
1010 1010 & 0000 1000 = 0000 1000 第 4 位存在 1
    1010 1010 - 0000 1000 = 1010 0010 新点集 1010 0010

1010 1010 & 0001 0000 = 0000 0000 第 5 位没有 1
1010 1010 & 0010 0000 = 0010 0000 第 6 位存在 1
    1010 1010 - 0010 0000 = 1000 1010 新点集 1000 1010

1010 1010 & 0100 0000 = 0000 0000 第 7 位没有 1
1010 1010 & 1000 0000 = 1000 0000 第 8 位存在 1
    1010 1010 - 1000 0000 = 0010 1010 新点集 0010 1010

7、d(i,V’)的另外一种表示

d(i,V’) 表示从点 i 出发,经过点集 V’ （使用整数 pointNum 表示）,

到达点 0 的最短距离（假设在 pointNum 的二进制表示形式中第 j 位上存在 1）

由 2 知，

dp[i][pointNum] 表示的是从点 i 出发，经过 pointNum 所表示的点集 V’，

到达点 0 的最短距离。

因此可以看出 d(i,V’) = dp[i][pointNum] (在 pointNum 能够表示 V’ 的情况下)

8、拆分之后如何求最短路径

最短路径 d(i,V’) 表示从点 i 出发,经过点集 V’ （使用整数 pointNum 表示）,

最后到达 0 的最短距离（假设在 pointNum 的二进制表示形式中第 j 位上存在 1）

我们可以通过 3 判断出在 pointNum 的第 j 位上存在 1,

然后我们通过 6 可以取出点 j

那么取出的点为 k （2 的 j - 1 次方），构成的新点集为 V’’ 用整数 newPointNum 表示

那么我们就获得了一条新的路径，新路径为 i -> j -> V’’ -> 0

表示为 从点 i 出发，然后到达点 j，然后从点 j(2 的 j - 1 次方) 出发，

绕后经过点集 V’’,最后到达 0 点的最短路径，拆分为两部分

第一部分 i -> j 表示从 i 到 j 的距离，可以通过 C[i][j] 表示
第二部分 j -> V'' -> 0 j 经过点集 V'' 最后到达 0 的距离
可以通过 dp[j][newPointNum] 表示

由 2 可知，
dp[i][j] 表示的是从点 i 出发，经过 j 所表示的点集 V'，然后到达 0 的最短距离，
那么 dp[j][newPointNum] 表示的是从点 j 出发，
经过 newPointNum 所表示的点集 V''，然后到达 0 的最短距离,
所以 j -> V'' -> 0 可以使用 dp[j][newPointNum] 来表示

因此,

d(i,V’) = dp[i][pointNum] = i -> V’ -> 0 = i -> j -> V’’ -> 0 = C[i][j] + dp[j][newPointNum]

其中 i 是已知的不用求，k = 2^(j -1)，newPointNum = pointNum - k

pointNum 也是已知的，它是 V’ 的整数表示形式，

那么我们只需要找出 j 和 newPointNum 就行了

当我们知道了 j 时，k 就已知， newPointNum 也就已知，所以主要求 j

例如，由 6 可知，对于图 5 的 dp[3][3] = d(3,{1,2}) = 14

其中 i = 3，pointNum = 011 = 3
    第 1 位 第 2 位 第 3 位
    011        011        011
   &001       &010       &100
    001        010        000

得到 
    j1 = 1                               j2 = 2(表示第 1 2 位上存在 1)
    k1 = 2^(1-1) = 1                    k2 = 2^(2 - 1) = 2(表示点 1 2 在点集中)
    newPointNum1 = pointNum - k1 = 2    newPointNum2 = pointNum - k2 = 1
    C[3][1] + dp[1][2] = 7 + 8 = 15        C[3][2] + dp[2][1] = 5 + 9 = 14

两者取最小值为14，即为数组 dp[3][3] 所求
dp[1][2],dp[2][1]我们会在下面介绍如何得到的

9、如何找出无效的点

无效的点分为两种情况，

• 没有经过完整的点集
• 经过了重复的点

将 dp 中的无效点进行分类，可以得到下列数据

对于第一种在 dp 数组中有点
    dp[0][0],dp[0][1],dp[0][2]dp[0][3],dp[0][4],dp[0][5],dp[0][6]
    有这 7 个点
对于第 2 种情况在 dp 数组中有点
    dp[1][1],dp[1][3],dp[1][5],dp[1][7]
    dp[2][2],dp[2][3],dp[2][6],dp[2][7]
    dp[3][4],dp[3][5],dp[3][6],dp[3][7]
    有这 12 个点

第一种情况可以通过 if 判断，当在 0 行时，是否为最后一列，若不是最后一列，
就赋值为无效值
对于第二种情况,由于是经过了重复的点，通过 5 我们可以判断在点集中是否存在一个点，
这时候我们只需要知道判断的是哪个点在不在点击就可以了
对于dp[i][j] 来说，只需要判断 i 是不是在点集中就好了，

dp[1][1] k = 2^(1 - 1) = 1        j & k = 001 & 001 = 001
表示在点集中存在 1
dp[1][3] k = 2^(1 - 1) = 1        j & k = 011 & 001 = 001
表示在点击中存在 1
dp[1][5] k = 2^(1 - 1) = 1        j & k = 101 & 001 = 001
表示在点集中存在 1
dp[1][7] k = 2^(1 - 1) = 1        j & k = 111 & 001 = 001
表示在点集中存在 1

dp[2][2] k = 2^(2 - 1) = 2        j & k = 010 & 010 = 010
表示在点集中存在 2
dp[2][3] k = 2^(2 - 1) = 2        j & k = 011 & 010 = 010
表示在点击中存在 2
dp[2][6] k = 2^(2 - 1) = 2        j & k = 110 & 010 = 010
表示在点集中存在 2
dp[2][7] k = 2^(2 - 1) = 2        j & k = 111 & 010 = 010
表示在点集中存在 2

dp[3][4] k = 2^(3 - 1) = 4        j & k = 100 & 100 = 100
表示在点集中存在 3
dp[3][5] k = 2^(3 - 1) = 4        j & k = 101 & 100 = 100
表示在点击中存在 3
dp[3][6] k = 2^(3 - 1) = 4        j & k = 110 & 100 = 100
表示在点集中存在 3
dp[3][7] k = 2^(3 - 1) = 4        j & k = 111 & 100 = 100
表示在点集中存在 3

2、表格数据进行说明(只要我们能够找到 k 就可以解决问题了)##

我们在 9、如何找出无效的点章节已经找出了无效的点，下面的讨论将会一笔带过，

它们分别是

dp[0][0],dp[0][1],dp[0][2],dp[0][3],
dp[0][4],dp[0][5],dp[0][6]
dp[1][1],dp[1][3],dp[1][5],dp[1][7]
dp[2][2],dp[2][3],dp[2][6],dp[2][7]
dp[3][4],dp[3][5],dp[3][6],dp[3][7]

对红框框起来的数据进行讨论

第 0 列数据

dp[0][0] = ∞ 已经证明
dp[1][0] = d(1,{}) = C[1][0] = 5
dp[2][0] = d(2,{}) = C[2][0] = 6
dp[3][0] = d(3,{}) = C[3][0] = 3

这一行的数据可以在初始化的时候给表格赋值初始值

第 1 列数据

dp[0][1] = ∞ 已经证明
dp[1][1] = ∞ 已经证明
dp[2][1] = d(2,{1})
    其中 i = 2，pointNum = 001 = 1
    第 1 位 第 2 位 第 3 位
    001        001        001
   &001       &010       &100
    001        000        000 
得到 
    j = 1                               
    k = 2^(1 - 1) = 1                    
    newPointNum = pointNum - k = 0    
    C[2][1] + dp[1][0] = 4 + 5 = 9

dp[3][1] = d(3,{1})
    其中 i = 3，pointNum = 001 = 1
    第 1 位 第 2 位 第 3 位
    001        001        001
   &001       &010       &100
    001        000        000 
得到 
    j = 1                               
    k = 2^(1 - 1) = 1                    
    newPointNum = pointNum - k = 0    
    C[3][1] + dp[1][0] = 7 + 5 = 12    

第 2 列数据

dp[0][2] = ∞ 已经证明
dp[1][2] = d(1,{2})
其中 i = 1，pointNum = 010 = 2
    第 1 位 第 2 位 第 3 位
    010        010        010
   &001       &010       &100
    000        010        000 
得到 
    j = 2                               
    k = 2^(2 - 1) = 2                    
    newPointNum = pointNum - k = 0    
    C[1][2] + dp[2][0] = 2 + 6 = 8    
dp[2][2] = ∞ 已经证明
dp[3][2] = d(3,{2})
    其中 i = 3，pointNum = 010 = 2
    第 1 位 第 2 位 第 3 位
    010        010        010
   &001       &010       &100
    000        010        000 
得到 
    j = 2                               
    k = 2^(2 - 1) = 2                    
    newPointNum = pointNum - k = 0    
    C[3][2] + dp[2][0] = 5 + 6 = 11    

第 4 列（注意这里是第 4 列，不是第 3 列，先把单个点集的列计算完）

dp[0][4] = ∞ 已经证明
dp[1][4] = d(1,{3})
    其中 i = 1，pointNum = 100 = 4
    第 1 位 第 2 位 第 3 位
    100        100        100
   &001       &010       &100
    000        000        100 
得到 
    j = 3                               
    k = 2^(3 - 1) = 4                    
    newPointNum = pointNum - k = 0    
    C[1][3] + dp[3][0] = 3 + 3 = 6    
dp[2][4] = d(2,{3})
    其中 i = 2，pointNum = 100 = 4
    第 1 位 第 2 位 第 3 位
    100        100        100
   &001       &010       &100
    000        000        100 
得到 
    j = 3                               
    k = 2^(3 - 1) = 4                    
    newPointNum = pointNum - k = 0    
    C[2][3] + dp[3][0] = 2 + 3 = 5    
dp[3][4] = ∞ 已经证明

第 3 列数据

dp[0][3] = ∞ 已经证明
dp[1][3] = ∞ 已经证明
dp[2][3] = ∞ 已经证明
dp[3][3] = d(2,{1,2}) (上面也已经证明,摘录一下)
其中 i = 3，pointNum = 011 = 3
    第 1 位 第 2 位 第 3 位
    011        011        011
   &001       &010       &100
    001        010        000

得到 
    j1 = 1                               j2 = 2(表示第 1 2 位上存在 1)
    k1 = 2^(1-1) = 1                    k2 = 2^(2 - 1) = 2(表示点 1 2 在点集中)
    newPointNum1 = pointNum - k1 = 2    newPointNum2 = pointNum - k2 = 1
    C[3][1] + dp[1][2] = 7 + 8 = 15        C[3][2] + dp[2][1] = 5 + 9 = 14

两者取最小值为14，即为数组 dp[3][3] 所求

第 5 列数据

dp[0][5] = ∞ 已经证明
dp[1][5] = ∞ 已经证明
dp[2][5] = d(2,{1,3})
其中 i = 2，pointNum = 101 = 5
    第 1 位 第 2 位 第 3 位
    101        101        101
   &001       &010       &100
    001        000        100

得到 
    j1 = 1                               j2 = 3(表示第 1 2 位上存在 1)
    k1 = 2^(1 - 1) = 1                    k2 = 2^(3 - 1) = 4(表示点 1 2 在点集中)
    newPointNum1 = pointNum - k1 = 4    newPointNum2 = pointNum - k2 = 1
    C[2][1] + dp[1][4] = 4 + 6 = 10        C[2][3] + dp[3][1] = 2 + 12 = 14
    两者取最小值为10，即为数组 dp[2][5] 所求
dp[3][5] = ∞ 已经证明

第 6 列数据

dp[0][6] = ∞ 已经证明
dp[1][6] = d(1,{2,3})
其中 i = 1，pointNum = 110 = 6
    第 1 位 第 2 位 第 3 位
    110        110        110
   &001       &010       &100
    000        010        100

得到 
    j1 = 2                               j2 = 3(表示第 1 2 位上存在 1)
    k1 = 2^(2 - 1) = 2                    k2 = 2^(3 - 1) = 4(表示点 1 2 在点集中)
    newPointNum1 = pointNum - k1 = 4    newPointNum2 = pointNum - k2 = 2
    C[1][2] + dp[2][4] = 2 + 5 = 7        C[1][3] + dp[3][2] = 3 + 11 = 14    
    两者取最小值为7，即为数组 dp[1][5] 所求
dp[2][6] = ∞ 已经证明
dp[3][6] = ∞ 已经证明

第 7 列数据

dp[0][7] = d(0,{1,2,3}) 这个是有数据的，因为经过了所有的点集
    其中 i = 0，pointNum = 111 = 7
    第 1 位 第 2 位 第 3 位
    111        111        111
   &001       &010       &100
    001        010        100

得到 
    j1 = 1                   j2 = 2                                                j3 = 3
    k1 = 1                    k2 = 2                                                k3 = 4
    newPointNum1  = 6        newPointNum2 = 5                                    newPointNum2 = 3
    C[0][1] + dp[1][6] = 3 + 7 = 10        C[0][2] + dp[2][5] = 6 + 10 = 16  C[0][3] + dp[3][3] = 7 + 14 = 21
    三者取最小值为10，即为数组 dp[0][7] 所求

整个数组就这样讲解完了

七、代码讲解

通过上面的讲解，我们知道要先求点的数量为 0 1 2 3 的点集，但是点集在横坐标上并不是按照数量进行排序的，而是按照点集的整数表现形式，从小到大进行排序的。如图 5 的第 3 列和第 4 列(下标从 0 开始)。

因此我们需要找到点的数量为 0 1 2 3 的点集，可以通过下面的代码进行求解，第一张图片显示了如何求解一个整数中 1 的数量，第 2 张图片显示，构造一个列表，该列表存储了有 0 个 1，1 个 1，2 个 1，3 个 1 的都有哪些列表，最终构造的列表如下
0 [0]
1 [1,2,4]
2 [3,5,6]
3 [7]

所代表的含义是，

0 个 1 的整数有 0
1 个 1 的整数有 1,2,4
2 个 1 的整数有 3,5,6
3 个 1 的整数有 7

如何从一个整数中获取 1 的个数，可以查看这篇博客，此处的代码片段也是从该博客中截取的

地址：https://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html

在开始有个初始化的操作，因为在初始的时候我们就已经知道了，点集中点的个数有多少，

对于图 1，有 4 个点，去掉起始点 0(因为起始点不能加入到点集中)，剩余的 3 个点，

共有 4 种情况，0 个 1，1 个 1，2 个 1，3 个 1。

1 处就是把无效数据给赋值成 ∞，这里用 Integer.MAX_VALUE 代替
2 处判断一个点是都存在点集中，并且拆出来的这个点能够由 i 点可达
3 处进行点的拆分
4 处当拆分出多个点的时候，取其最小值

八、代码

代码地址:https://github.com/clay-nuyoah/TSP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

package tsp;

import java.util.ArrayList;
import java.util.List;

/**
 * TSP 算法旅行推销员问题
 * 给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。
 */
public class TspDp {
	    public static void main(String[] args) {
	        int[][] nums = {{Integer.MAX_VALUE, 3, 6, 7},
	                {5, Integer.MAX_VALUE, 2, 3},
	                {6, 4, Integer.MAX_VALUE, 2},
	                {3, 7, 5, Integer.MAX_VALUE}
	        };
	        TspDp tspDp = new TspDp();
	        int minCost = tspDp.getMinCost(nums, nums.length);
	        System.out.println(minCost);
	    }

    /**
     * 获取最小花费
     *
     * @param nums 节点之间的花费
     * @param n    节点个数
     * @return
     */
    public int getMinCost(int[][] nums, int n) {
        int row = n;
        int col = (int) Math.pow(2, n - 1);
        int[][] dp = new int[row][col];
        List<List<Integer>> countLists = getCountLists(row, col);

        init(dp, nums, row);

			//遍历数组中的每一个数
        for (int j = 1; j < row; j++) { //循环遍历 数量 数组
            List<Integer> countList = countLists.get(j);
				//用来确定横坐标
            for (int k = 0; k < countList.size(); k++) {
				//纵坐标       
                for (int i = 0; i < row; i++) {           
                    Integer num = countList.get(k);
                    int currentMinCost = getCurrentMinCost(i, num, row, col, nums, dp);
                    dp[i][num] = currentMinCost;

                }
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println();
        }
        return dp[0][col - 1];
    }

    /**
     * 获取一个 list
     * list[0] 表示 从 0 ~ col 中二进制 拥有 0 个 1 的数字组成的集合
     * list[1] 表示 从 0 ~ col 中二进制 拥有 1 个 1 的数字组成的集合
     *
     * @param row
     * @param col
     * @return
     */
    private List<List<Integer>> getCountLists(int row, int col) {
        List<List<Integer>> countLists = new ArrayList<>();
        for (int i = 0; i < row; i++) {
            countLists.add(new ArrayList<>());
        }

        for (int i = 0; i < col; i++) {
            int count = bitCount(i);
            countLists.get(count).add(i);
        }

        return countLists;
    }

    /**
     * 获取一个整数 二进制 1 的个数
     *
     * @param n
     * @return
     */
    private int bitCount(int n) {
        int c;
        for (c = 0; n != 0; ++c) {
            n &= (n - 1); // 清除最低位的1
        }
        return c;
    }

    /**
     * 获取当前条件下的最小花费
     *
     * @param i
     * @param num
     * @param row
     */
    private int getCurrentMinCost(int i, int num, int row, 
			int col, int[][] nums, int[][] dp) {
        int pow = (int) Math.pow(2, i - 1);

        if (num != col - 1 && (i == 0 || (pow & num) == pow)) {
            return Integer.MAX_VALUE;
        }

        int min = Integer.MAX_VALUE;
        for (int j = 1; j < row; j++) {
            int pow1 = (int) Math.pow(2, j - 1);
            if ((pow1 & num) == pow1 && nums[i][j] != Integer.MAX_VALUE) {
                int y = num - pow1;
                int cost = nums[i][j] + dp[j][y];
                if (cost < min) {
                    min = cost;
                }
            }
        }
        return min;
    }

    /**
     * 初始化 dp
     *
     * @param dp
     * @param nums
     * @param row
     */
    private void init(int[][] dp, int[][] nums, int row) {
        for (int i = 0; i < row; i++) {
            dp[i][0] = nums[i][0];
        }
    }
}