DP求解TSP问题

定义

TSP问题（旅行商问题）是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。
假设现在有四个城市，0,1,2,3，他们之间的代价如图一，可以存成二维表的形式，如图所示：
Alt text
现在要从城市0出发，最后又回到0，期间1，2，3都必须并且只能经过一次，使代价最小。

分析

该方法运用到 TSP 问题的求解过程如下:
Alt text

实例分析

现在对问题定义中的例子来说明TSP的求解过程。(假设出发城市是 0城市):
Alt text 我们要求的最终结果是d(0,{1,2,3}),它表示，从城市0开始，经过{1,2,3}之中的城市并且只有一次，求出最短路径.
d(0,{1,2,3})是不能一下子求出来的，那么他的值是怎么得出的呢？
看上图的第二层，第二层表明了d(0,{1,2,3})所需依赖的值。那么得出:

   d(0,{1,2,3})=min  {
                                C01+d(1,{2,3})
                                C02+d{2,{1,3}}
                                C03+d{3,{1,2}}
                              }

d(1,{2,3})，d(2,{1,3})，d(3,{1,2})同样也不是一步就能求出来的，它们的解一样需要有依赖，就比如说d(1,{2,3})

 d(1,{2,3})=min{
                          C12+d(2,{3})                             
                          C13+d(3,{2})
                          }

d(2,{1,3})，d(3,{1,2})同样需要这么求。
按照上面的思路，只有最后一层的，当当V’为空集时，Cis的值才可以求，它的值是直接从
Alt text 这张表里求得的。

编程思路

将d(i, V’)转换成二维表，d[i][j] Alt text

源代码

ptr_test/stp2

reference:

JoeKwok的专栏