0009算法笔记【动态规划】动态规划与斐波那契数列问题,最短路径问题

1、动态规划算法：动态规划：通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。基本思想：若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。与分治法区别：动态规划算法与分治法类似，都使用了将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优值的思路，但动态规划不是分治法：关键在于分解出来的各个子问题的性质不同。分治法要求各个子问题是独立的(即不包含公共的子问题)，因此一旦递归地求出各个子问题的解后，便可自下而上地将子问题的解合并成原问题的解。如果各子问题是不独立的，那么分治法就要做许多不必要的工作，重复地解公共的子问题。动态规划与分治法的不同之处在于动态规划允许这些子问题不独立(即各子问题可包含公共的子问题)，它对每个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。相关术语：(1)阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同，描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的。此外，也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。(2)状态：状态表示每个阶段开始面临的自然状况或客观条件，也称为不可控因素。过程的状态通常可以用一个或一组数来描述,称为状态变量。一般状态是离散的,但有时为了方便也将状态取成连续的。(3)无后效性：状态具有下面的性质,如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响,所有各阶段都确定时,整个过程也就确定了。换句话说,过程的每一次实现可以用一个状态序列表示,在前面的例子中每阶段的状态是该线路的始点,确定了这些点的序列,整个线路也就完全确定。从某一阶段以后的线路开始,当这段的始点给定时,不受以前线路,所通过的点,的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展,这个性质称为无后效性。(4)决策：一个阶段的状态给定以后,从该状态演变到下一阶段某个状态的一种选择(行动)称为决策。在最优控制中,也称为控制。在许多间题中,决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量,因状态满足无后效性,故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。决策变量的范围称为允许决策集合。(5)策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。(6)最优性原理:作为整个过程的最优策略,它满足,相对前面决策所形成的状态而言,余下的子策略必然构成―最优子策略。问题特征：(1)最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。(2)重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。算法步骤：(1)分析最优值的结构，刻画其结构特征；(2)递归地定义最优值；(3)按自底向上或自顶向下记忆化的方式计算最优2、斐波那契数列(Fibonaccipolynomial)计算斐波那契数列(Fibonaccipolynomial)的一个最基础的算法是，直接按照定义计算：[cpp]viewplaincopy1.//3m1未优化斐波那契数列计算2.#includestdafx.h3.#includeiostream4.5.usingnamespacestd;6.7.voidinput(int&n);8.intfib(intn);9.10.intmain()11.{12.intn;13.input(n);14.coutfib(n)=fib(n)endl;15.return0;16.}17.18.voidinput(int&n)19.{20.cout请输入n:endl;21.cinn;22.}23.24.intfib(intn)25.{26.if(n==0||n==1)27.{28.return1;29.}30.else31.{32.returnfib(n-1)+fib(n-2);33.}34.}以上代码在n=5时，fib(5)的计算过程如下:1.fib(5)2.fib(4)+fib(3)3.(fib(3)+fib(2))+(fib(2)+fib(1))4.((fib(2)+fib(1))+(fib(1)+fib(0)))+((fib(1)+fib(0))+fib(1))5.(((fib(1)+fib(0))+fib(1))+(fib(1)+fib(0)))+((fib(1)+fib(0))+fib(1))由上面可以看出，这种算法对于相似的子问题进行了重复的计算，因此不是一种高效的算法。实际上，该算法的运算时间是指数级增长的。改进的方法是，我们可以通过保存已经算出的子问题的解来避免重复计算：[cpp]viewplaincopy1.//3m1避免重复运算的斐波那契数列运算2.#includestdafx.h3.#includeiostream4.#includemap5.usingnamespacestd;6.7.voidinput(int&n);8.intfib(intn,mapint,int);9.10.intmain()11.{12.mapint,intmy_Map;13.intn;14.input(n);15.coutfib(n)=fib(n,my_Map)endl;16.return0;17.}18.19.voidinput(int&n)20.{21.cout请输入n:endl;22.cinn;23.}24.25.intfib(intn,mapint,intmy_Map)26.{27.if(n==0||n==1)28.{29.return1;30.}31.else32.{33.mapint,int::iteratoriter=my_Map.find(n);34.if(iter==my_Map.end())35.{36.inttemp=fib(n-1,my_Map)+fib(n-2,my_Map);37.my_Map.insert(pairint,int(n,temp));38.returntemp;39.}40.else41.{42.returniter-second;43.}44.}45.}将前n个已经算出的前n个数保存在数组map中，这样在后面的计算中可以直接易用前面的结果，从而避免了重复计算。算法的运算时间变为O(n)。3、最短路径问题现有一张地图，各结点代表城市，两结点间连线代表道路，线上数字表示城市间的距离。如图1所示，试找出从结点A到结点E的最短距离。我们可以用深度优先搜索法来解决此问题，该问题的递归式为:其中是与v相邻的节点的集合，w(v,u)表示从v到u的边的长度。具体算法如下下：[cpp]viewplaincopy1.//3m1未优化的图的最短路径问题2.#includestdafx.h3.#includeiostream4.#includefstream5.#includestring6.usingnamespacestd;7.8.ifstreamfin(in.txt);9.#definemaxLength2010.11.intmatrix[maxLength][maxLength];//有向图的邻接表12.inttrace[maxLength];//记录下最短线路13.stringNode[maxLength]={A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E};//节点标记14.intv_n;//节点个数15.16.intMinDistance(intv);17.18.intmain()19.{20.finv_n;21.for(inti=0;iv_n;i++)22.{23.for(intj=0;jv_n;j++)24.{25.finmatrix[i][j];26.coutmatrix[i][j]-;27.}28.coutendl;29.}30.memset(trace,0,sizeof(int)*maxLength);31.32.intminD=MinDistance(0);33.cout最短路径：minDendl;34.intk=0;35.coutNode[0]--;36.while(minD0)37.{38.coutNode[trace[k]]--;39.minD=minD-matrix[k][trace[k]];40.k=trace[k];41.}42.coutendl;43.return0;44.}45.46.intMinDistance(intv)47.{48.if(v==v_n-1)return0;//边界值49.intmin=1000,t,j;50.for(inti=v+1;iv_n;i++)51.{52.if(matrix[v][i]0)53.{54.t=matrix[v][i]+MinDistance(i);55.if(mint){min=t;j=i;}56.}57.}58.trace[v]=j;59.returnmin;60.}这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外，其他城市都要访问，所以时间复杂度为O(n!)，这是一个“指数级”的算法，那么，还有没有更好的算法呢？首先，我们来观察一下这个算法。在求从B1到E的最短距离的时候，先求出从C2到E的最短距离；而在求从B2到E的最短距离的时候，又求了一遍从C2到E的最短距离。也就是说，从C2到E的最短距离我们求了两遍。同样可以发现，在求从C1、C2到E的最短距离的过程中，从D1到E的最短距离也被求了两遍。而在整个程序中，从D1到E的最短距离被求了四遍。如果在求解的过程中，同时将求得的最短距离记录在案，随时调用，就可以避免这种情况。于是，可以改进该算法，将每次求出的从v到E的最短距离记录下来，在算法中递归地求MinDistance(v)时先检查以前是否已经求过了MinDistance(v)，如果求过了则不用重新求一遍，只要查找以前的记录就可以了。这样，由于所有的点有n个，因此不同的状态数目有n个，该算法的数量级为O(n)。[cpp]viewplaincopy1.//3m4避免重复运算的图的最短路径问题2.#includestdafx.h3.#includeiostream4.#includefstream5.#includestring6.usingnamespacestd;7.8.ifstreamfin(in.txt);9.#definemaxLength2010.11.intmatrix[maxLength][maxLength];//有向图的邻接表12.intminPath[maxLength];//存储这每个节点到终点的最短路径13.inttrace[maxLength];//记录下最短线路14.stringNode[maxLength]={A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E};//节点标记15.intv_n;//节点个数16.17.intMinDista