动态规划算法入门、原理、应用

《动态规划算法入门、原理、应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、动态规划算法101rNxfe{OJ}1.3算法设计该问题属于组合优化的NP完全问题，即最优化问题。0-1背包的状态转换方程:/U,j]=max{/[z-lj-w.]+vf.（；＞vv,.）,/[/-1,川其中：f[ij]表示前，件物品选择若干件放在承重为丿•的背包中，可以取得的最大价值；将前，件物品选择若干件放在承重为J的背包这个子问题，若是只考虑第，件物品的策略（放或不放），那么问题就转化为一

2、个只和前7-1件物品相关的问题。>如果不放，问题转化为将前i-1件物品选择若干件放在承重为丿•的背包中，此时价值为>如果放，则问题转化为将前—1件物品选择若干件放在承重为丿的背包屮，此时价值为/[MJ-wJ+v.1.4实例（只要理解这张表是如何生成的，就算理解动态规划算法）首先要明确这张表是至底向上，从左到右生成的。用e2单元格表示e行2列的单元格，这个单元格的意义是用來表示只有物品e时，有个承重为2的背包，那么这个背包的最大价值是0,因为e物品的重量是4,背包装不了。对于（12单元格，表示只冇物品c,d时,承重为2的背包，所能装入的最大价值，仍然是0,因为物品e

3、,d都不是这个背包能装的。同理…那么对于承重为8的背包，a8=15,是怎么得出的呢？根据0-1背包的状态转换方程，需要考察两个值，一个是/[M.jT对于这个例子来说就是b8的值9,另一个是/+表示有一个承重为6的背包（等于当前背包承重减去物品a的重量），当只有物品b,c,d,e四件可选时，这个背包能装入的授大价值，即b6；2动态规划算法动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。如何拆分问题，才是动态规划的核心。而拆分问题，靠的就是状态的定义和状态转移方程的定义。因此动态规划算法中最重要的两个概念为给定一个数

4、列，长度为N,求这个数列的最长上升（递增）子数列（LIS）的长度。以172834为例。这个数列的最长递增了数列是1234,长度为4；次长的长度为3,包括17&123等。问题重新左义给定一个数列，长度为Nc设禺为：以数列屮第k项结尾的最长递增子序列的长度。求耳…你中的最大值。显然，这个新问题与原问题等价。而对于坨来讲，F...Fn都是厶的了问题：因为以第R项结尾的最长递增了序列，包含着以笫1-1中某项结尾的最长递增子序列。坨即为状态。2.2状态转移方程状态转移方程，就是定义了问题和子问题z间的关系，是带有约束条件的递推式。继续上述例子，状态转移方程可以表示为：Fk

5、=max（斥+1人>A.,zg3动态规划问题的求解步骤动态规划所处理的问题是一个多阶段决策问题，一般山初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线（通常是求最优的活动路线）。动态规划的设计都有着一定的模式，一般要经历以下儿个步骤。1）划分阶段：按照问题的吋间或空间特征，把问题分为若干个阶段。在划分阶段吋,注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。2）确定状态和状态变最:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无示效性。3）

6、确定决策并写出状态转移方程：因为决策和状态转移冇着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。4）寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。4动态规划算法的应用4.1最短路径>Dijkstra算法（单源最短路径）最短路径长度1381319219W20从

7、VO到各终点的M短路径及其t度VI13VO.VI13VO,VIV28V0.V2■■■■■■■■■V3cc13V0.V2.Y313Q2V3■■■■■■■V430V0.V430(2^41^O.V430V0.V419QV2.V3.V4V520QV1X620-V0.V1.V6>20V0.VLV6VjV2:8V0.V2—1:13V3:13V()・23V4:19QV2.3V4V6:20

8、Floyd