数学和计算机科学板块_辛酸网
数据结构与算法22
BY TSherry
多段图是图，一段一段的，每一个结点都属于其中的一个段，每一个结点的入边来自上一个段，出边走向下一个段。 现在给定一个多段图，以首段的结点为起点，末段的结点为终点，求自起点而终点的最短路径，这就是多段图最短路径问题。
、
多段图就是上边这样，由于图片显示限制这里略去箭头，其中S为首段，T为末段。
首先看终点前的那段结点。我们设第i段第j个结点叫做Ni,j，整体一共n段，其中第i和(i+1)段的结点Ni,a到Ni+1,b直达的边叫做C(i,a)→(i+1,b)。则终点前的那一段中，第k个结点到终点段里的第m个终点，其路径是唯一的。
所以结点Nn-1,k到终点Nn,m的最短路径只可能是
边C(n-1,k)→(n,m)，最短路径也就是该边长度。
然后看末段的前第二段，也就是整体的第(n-2)段。这里的一个结点Nn-2,k去终点Nn,m的路径就不唯一了。但第(n-1)段内每个结点去终点的路径唯一，而第(n-2)段的一个结点Nn-2,i到(n-1)段的一个结点Nn-1,j的路径唯一，所以， 对于终点Nn,m而言，如果结点Nn-2,i非要通过Nn-1,j到达这个终点的话，那么路径就是唯一的。
如果我们设第x段有Lx个结点，那么，结点Nn-2,i去(n-1)段的路径一共也就Ln-1条，分别对应着Ln-1个在(n-1)段的结点。而这Ln-1个在(n-1)段的结点去同一个终点Nn,m的路径又各自唯一。 因此结点Nn-2,i去终点Nn,m的路径一共Ln-1条。于是Nn-2,i去终点Nn,m之最短路径只需从这Ln-1条里挑最短的那个就行了。
现在看一般的情况。
既然在(n-2)段的结点我们可以通过比较大小来解决，那么在(n-2)段结点去终点的最短路径已知的情况下，我们也可以比较大小得知(n-3)段去往终点的最短路径。以此类推，起点到终点的问题也就能解决了。如上图所见，对于第i段的结点Ni,j，因为后面的第(i+1)段的每一个结点去往终点Nn,m的最短路径已经算出来了， 而Ni,j去终点Nn,m的路径也就是这Li+1条，无非是第(i+1)段的每一个结点去往终点Nn,m的最短路径各自在前面多一条边C(i,j)→(i+1,k)(1≤k≤Li+1)罢了。既然如此，从Ni,j到Nn,m的最短路径不就是这Li+1条相互比较大小取最短的那个么？仅此而已。
接着继续往前，我们也能找到第(i-1)段的每一个结点去Nn,m的最短路径。就此一直往前，手段的每一个起点到Nn,m的最短路径都能算出来。 同理，每一个起点到每一个终点的最短路径都能算出来了。不过我们还要记得，每次的最短路径中的下一跳必须都记下来，因为这个要实现动态规划就必须做到反向构造最优解。 我们不仅要明白最短路径有多短，还得弄清楚最短路径怎么走。
虽然上述行为和迪杰斯特拉算法是反过来的，核心逻辑一模一样，但它确实是动态规划而非贪心。
这个问题的内容是：在一个带权连通图里寻找最小哈密顿回路——要求经过所有结点又能回到一开始的起点，且经过路径总长度最小。 该问题有多个变体，有有向图和无向图的、有单起点和多起点的。
TSP问题的动态规划算法可以参照这里解决， 不过它是针对无向图的。而有向图的话则需要更多的时间与空间开销。接下来我们解读一下他写的文章。
首先，设整体的起点为s，再记所有的结点组成的集合叫G，则除去s剩下的就是G-{s}。如果我们在G-{s}中选取一个结点i，我们要求s之后的第一站必须是i， 即非要先走结点i再走其它的全部结点后返回到s，那么这种条件下，能走的最短回路就取决于剩下结点的顺序了。现在，咱们用d(i,V)表示：自结点i开始（不涉及从s到i的部分），经过V中所有结点且只经过一次，再一步到位返回到s的路径长度。 也就是说，d(i,V)是结点s通过某些方式到结点i，再经过V中全部结点后返回到s的这个回路长度的一部分。其中V是一个结点构成的集合。
d(i,V)只涉及从i到s的，s到i的不包括。
当V是∅时，自结点i出发就一步到位返回起点s，此时回路就是s→...→i→s。d(i,V)包含的边只有结点i到s的。 随后，我们设结点a到结点b的边长度为Ca,b，显然d(i,∅)≡Ci,s成立。
对于一般情况，设V中是编号为a1~am的m个结点。自结点i始下一跳就有m个选择，选了以后再下一跳就有(m-1)个选择。显然，整体上阶乘数量级的那么多可能性导致我们无法暴力穷举。但要是我们事先知道了结点aj出发通往V中剩下结点再返回s的最短回路的话，结点i后先经过aj再经过V中剩余结点返回s的最短路径就定下来了。换言之，当V中的d(aj,V-{aj})已知时，路径距离i→aj→V中剩下结点最优方案→s的最短距离就确定了，正是ci,aj+d(aj,V-{aj})。
结点i的下一跳有m个选择，在这m个选择中我们取最小那个，即为d(i,V)。这样一来，我们发现了状态转移方程：d(i,V)=MINk∈V{ci,k+d(k,V-{k})}。
V是空集时，结果为结点i到s的边长度。V中只有一个结点k时，结果为i→k→s。至于起点s到结点i怎么走，完全可以进行大量假设，用“非要经过”的“非要”二字即可。整体上，直接计算d(s,G)。 计算过程就是不同路径选择下的树状的探索。这其中，更小的距离还需要一个或多个数组记下来以简化后续计算工作。
然而，上面的动态规划还是指数级别的，时间复杂度非常大。实际上，TSP问题是一个NP完全问题，用多项式时间是无法解决的（至少在当今社会的生产力水平下）。 为此历史上有很多人提出了一些各种各样的解决TSP问题的方法，有分支限界的，有启发式搜索的，有蚁群算法的（有科学家把一群蜜蜂放在了几朵花之间，发现蜜蜂可以成功解决这个问题）、模拟退火算法的。
辛酸网 ©版权所有