conclusion of dp problems____by pcpcpc

http://www.comp.nus.edu.sg

MST的一般算法为KRUSKAL或者普里姆算法，

这儿有个另类的：

选出任意’一棵树’(N-1条边);

不断向这个树中添加边,得到一个环,

在这个环中删除一条权值最大的边,

最后即可得到最小生成树.

当无论加入哪条边都不能更新这棵树时即结束.(?)

当石子归并的N〈=3000 时

原来的那个动态规划：F[I，J]：=MIN（F[I，V]，F[V+1，J]+S[I，J]）（0（N^2））

就不能做了。

但是我们从I-〉J 找V，仅仅是为了找到一个最优的，

若用D[I，J]表示F[I，J]最优时的V值，

则V的范围便由（I，J）变为（d[I，J-1]，d[I+1，J]）；

这便是四边形不等式的一个简单应用。

REPORT
CODE

最短路径问题是信息学竞赛中常见的一类中等难题，这是一个非常能联系实际的问题，甚至有时一些看似跟最短路径问题无关的问题也可以归结为最短路径问题。本文就简要分析一下此类问题的算法，以使大家一起探讨一下该类问题，也使没参加信息学竞赛的同学对信息学竞赛有个简单了解。

　　下面我们以具体例题来看看这类问题的解法：

　　例1、假设A、B、C、D、E各个城市之间旅费如下图所示。某人想从城市A出发游览各城市一遍，而所用费用最少。试编程序输出结果。

　　解这类题时同学们往往不得要领，不少同学采用穷举法把所有可能的情况全部列出，再找出其中最短的那条路径；或是采用递归或深度搜索，找出所有路径，再找出最短的那条。这两种方法可见都是费时非常多的解法，如果城市数目多的话则很可能要超时了。

　　实际上我们知道，递归、深度搜索等算法一般用于求所有解问题（例如求A出发每个城市走一遍一共有哪几种走法），而这几种算法对于求最短路径这类最优解问题显然是不合适的，以下介绍的几种算法就要优越很多。

　　首先，对于这类图我们都应该先建立一个邻接矩阵来存放任意两点间的距离数据，以便在程序中方便调用，如下：

const dis:array[1..5,1..5] of integer =( ( 0, 7, 3,10,15),

　　　　　　　　　　　　　　　　　　　　　　( 7, 0, 5,13,12),

　　　　　　　　　　　　　　　　　　　　　　( 3, 5, 0, 5,10),

　　　　　　　　　　　　　　　　　　　　　　(10,13, 5, 0,11),

　　　　　　　　　　　　　　　　　　　　　　(15,12,10,11, 0));

　　以下是几种解法：

　　一、 宽度优先搜索

　　宽度优先搜索并不是一种很优秀的算法，只里只是简单介绍一下它的算法。

　　具体方法是：

　　1、 从A点开始依次展开得到AB、AC、AD、AE四个新结点（第二层结点），当然每个新结点要记录下其距离；

　　2、 再次以AB展开得到ABC、ABD、ABE三个新结点（第三层结点），而由AC结点可展开得到ACB、ACD、ACE三个新结点，自然AD可以展开得到ADB、ADC、ADE，AE可以展开得到AEB、AEC、AED等新结点，对于每个结点也须记录下其距离；

　　3、 再把第三层结点全部展开，得到所有的第四层结点：ABCD、ABCE、ABDC、ABDE、ABEC、ABED……AEDB、AEDC，每个结点也需记录下其距离；

　　4、 再把第四层结点全部展开，得到所有的第五层结点：ABCDE、ABCED、……、AEDBC、AEDCB，每个结点也需记录下其距离；

　　5、 到此，所有可能的结点均已展开，而第五层结点中最小的那个就是题目的解了。

　　由上可见，这种算法也是把所有的可能路径都列出来再找最短的那条，显而易见这也是一种很费时的算法。
 

　　二、 A＊算法

　　A＊算法是在宽度优先搜索算法的基础上，每次并不是把所有可展的结点展开，而是对所有没有展开的结点，利用一个自己确定的估价函数对所有没展开的结点进行估价，从而找出最应该被展开的结点（也就是说我们要找的答案最有可能是从该结点展开），而把该结点展开，直到找到目标结点为止。

　　这种算法最关键的问题就是如何确定估价函数，估价函数越准则越快找到答案。A＊算法实现起来并不难，只不过难在找准估价函数，大家可以自已找资料看看。
 

　　三、等代价搜索法

　　等代价搜索法也是基于宽度优先搜索上进行了部分优化的一种算法，它与A＊算法的相似之处都是每次只展开某一个结点（不是展开所有结点），不同之处在于：它不需要去另找专门的估价函数，而是以该结点到A点的距离作为估价值，也就是说，等代价搜索法是A＊算法的一种简化版本。它的大体思路是：

　　1、 从A点开始依次展开得到AB（7）、AC（3）、AD（10）、AE（15）四个新结点，把第一层结点A标记为已展开，并且每个新结点要记录下其距离（括号中的数字）；

　　2、 把未展开过的AB、AC、AD、AE四个结点中距离最小的一个展开，即展开AC（3）结点，得到ACB（8）、ACD（16）、ACE（13）三个结点，并把结点AC标记为已展开；

　　3、 再从未展开的所有结点中找出距离最小的一个展开，即展开AB（7）结点，得到ABC（12）、ABD（20）、ABE（19）三个结点，并把结点AB标记为已展开；

　　4、 再次从未展开的所有结点中找出距离最小的一个展开，即展开ACB（8）结点……；

　　5、 每次展开所有未展开的结点中距离最小的那个结点，直到展开的新结点中出现目标情况（结点含有5个字母）时，即得到了结果。

　　由上可见，A＊算法和等代价搜索法并没有象宽度优先搜索一样展开所有结点，只是根据某一原则（或某一估价函数值）每次展开距离A点最近的那个结点（或是估价函数计算出的最可能的那个结点），反复下去即可最终得到答案。虽然中途有时也展开了一些并不是答案的结点，但这种展开并不是大规模的，不是全部展开，因而耗时要比宽度优先搜索小得多。
 

　　例2、题目基本同例1、但只要求求A到E点的最短路径（并不要求每个城市都要走一遍）。

　　题目一改，问题的关键变了，所要求的结果并不是要求每个点都要走一遍，而是不管走哪几个点，只要距离最短即可。再用宽度优先搜索已经没有什么意义了，那么等代价搜索能不能再用在这题上呢？

　　答案是肯定的，但到底搜索到什么时候才能得到答案呢？这可是个很荆手的问题。

　　是不是搜索到一个结点是以E结束时就停止呢？显然不对。

　　那么是不是要把所有以E为结束的结点全部搜索出来呢？这简直就是宽度优先搜索了，显然不对。

　　实际上，应该是搜索到：当我们确定将要展开的某个结点（即所有未展开的结点中距离最小的那个点）的最后一个字母是E时，这个结点就是我们所要求的答案！

　　那么，除了等代价搜索外，有没有其它办法了呢？下面就介绍求最短路径问题的第四种算法：
 

　　四、Warshall算法

　　该算法的中心思想是：任意两点i,j间的最短距离（记为Dij）会等于从i点出发到达j点的以任一点为中转点的所有可能的方案中，距离最短的一个。即：

　　Dij=min(Dij,Dik+Dkj，……)，1　　五、动态规划

　　动态规划算法已经成为了许多难题的首选算法，只不过在很多的题目中动态规划的算法表达式比较难找准，而恰恰最短距离问题如果用动态规划算法考虑则可以非常容易地找准那个算法表达式。

　　我们知道，动态规划算法与递归算法的不同之处在于它们的算法表达式：

　　递归：类似f(n)=x1*f(n-1)+x2*f(n-2)………，即可以找到一个确定的关系的表达式；

　　动态规划：类似f(n)=min(f(n-1)+x1,f(n-2)+x2……)，即我们无法找到确定关系的表达式，只能找到这样一个不确定关系的表达式，f(n)的值是动态的，随着f(n-1),f(n-2)等值的改变而确定跟谁相关。

　　就本题来说，我们记f(5)为A到E点的最短距离，则f(4)为A到D点的最短距离，f(1)为A到A点的最短距离（为0）。

　　于是，f(5)的值应该是所有与E点相邻的点的最短距离值再加上该点到E点的直接距离（dis矩阵中的值）所得到的值中最小的一个。 我们可以得到这样一个关系式：

　　f(5)=min(f(1)+dis(1,5), f(2)+dis(2,5), f(3)+dis(3,5), f(4)+dis(4,5))

　　以此关系式作一个递归函数即可求得A到E点的最短距离。不过，为了节省时间，我们可以把f(1)-f(4)已经算得的结果保存起来给后面的递归直接调用，这样就能节约大量的递归空间和时间，这对于数据量大时尤为重要。

　　六、标号法

　　标号法是一种非常直观的求最短路径的算法，单从分析过程来看，我们可以用一个数轴简单地表示这种算法：

　　1、 以A点为0点，展开与其相邻的点，并在数轴中标出。

　　2、因为C点离起点A最近，因此可以断定C点一定是由A直接到C点这条路径是最短的（因为A、C两点间没有其它的点，所以C点可以确定是由A点直接到达为最短路径）。因而就可以以已经确定的C点为当前展开点，展开与C点想连的所有点A’、B’、D’、E’。

　　3、由数轴可见，A与A’点相比，A点离原点近，因而保留A点，删除A’点，相应的，B、B’点保留B点，D、D’保留D’，E、E’保留E’，得到下图：

　　4、此时再以离原点最近的未展开的点B联接的所有点，处理后，再展开离原点离近未展开的D点，处理后得到如下图的最终结果：

　　5、由上图可以得出结论：点C、B、D、E就是点A到它们的最短路径（注意：这些路径并不是经过了所有点，而是只经过了其中的若干个点，而且到每一个点的那条路径不一定相同）。因而A到E的最短距离就是13。至于它经过了哪几个点大家可在上述过程中加以记录即可。
 

　　上述就是解最短路径问题的常用方法，但对于实际的题目到底用哪种方法？用该方法是不是需要做些变动？这种能力往往是很多同学所欠缺的，这只能靠平常地多学多练多总结才能把自己的能力与成绩挂上钩。下面我们就再看一个例题。
 

　　例3、Internet消息发布

　　问题描述：设Internet上有N个站点，通常从一个站点发送消息给其他N－1个站点，需依次发送N－1次。这样从一个站点发布消息传遍N个站点时，可能要较长时间。而当一个站点发布消息给另一个站点后，已获得消息的这两个站点就可以同时发布消息给另外两个站点，此后就有四个站点可以同时发布消息，这种发布消息方法应该会缩短消息传遍N个站点的时间。

　　请您编一个程序，设从每一个站点都可以向其他N－1个站点同时发送消息，编程求出从第一个站点开始发布消息传遍N个站点的最短时间。

　　输入：由文件Input4.dat输入数据，文件的第一行是Internet上的站点数N（11、动态规划：

　　考虑到动态规划可以求出每一个点到起点的最短时间，而我们所需要的答案就是这些最短时间中最长的那个（为什么？）。而至于此题展开了多少条路径，每个点怎么走到的我们都不用管了。

　　2、标号法：

　　使用标号法，处理完毕后，数轴中距离原点最远的一点就是答案（因为点1到该点所花的时间是点1到所有点的距离中最长的，因而它的时间就是题目要求的答案）。此题当然也不是由一条路径走遍所有点，而是几条路径同时走，只不过有长有短，而答案就是最长的那一条。