贪心法与动态规划(“问题”beplayapp体育下载)共22张.pptx

该【贪心法与动态规划(“问题”beplayapp体育下载)共22张 】是由【知识徜徉土豆】上传分享，beplayapp体育下载一共【22】页，该beplayapp体育下载可以免费在线阅读，需要了解更多关于【贪心法与动态规划(“问题”beplayapp体育下载)共22张 】的内容，可以使用beplayapp体育下载的站内搜索功能，选择自己适合的beplayapp体育下载，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此beplayapp体育下载到您的设备，方便您编辑和打印。第8章贪心法与动态规划(2)
石志国
大纲
◎贪心法的基本概念,以及使用贪心法解决问题:哈夫曼编码、单源最短路径、最小生成树、背包问题
◎动态规划的基本概念,以及使用动态规划解决问题:多源最短路径、背包问题、图像压缩和最长公共子序列问题。
(D,C,20)(D,E,60)
对于一个n×n的矩阵,Floyd算法使用的迭代矩阵序列如下:
最终,可以得到从A到E的最短路径。
子问题重叠性是指在利用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题可能会被重复计算多次。
现在的问题是:如何在每个阶段都作出一个恰当的决策,使由这些决策组成的一个决策序列所构成的一条线路的总距离最短。
灰度值的范围为0-255。
换言之,每个状态都是“过去历史的一个完整总结”。
最终,可以得到从A到E的最短路径。
最终,可以得到从A到E的最短路径。
与分治法和贪心法联系与区别
灰度值的范围为0-255。
此时像素段Si所需存储空间为:L[i]*b[i]+11位。
其中,Warshall算法是一个用于求图的传递闭包的算法。
将各个阶段求出的的解合并为原问题的解,即构造一个最优解。
与分治法和贪心法联系与区别
上述求解的方法称为动态规划法(DynamicProgramming)。
问题提出
动态规划是解决多阶段决策最优化问题的一种方法。
如图所示的一个线路网络,两点之间的连线上的数字表示两个点之间的距离,要求求出一条从A到E的路径,使得总距离最小。
问题提出
从图可以看出,从A到E可以划分为5个阶段,除起点A和终点E外,其它各点既是上一阶段的终点又是下一阶段的起点。
例如从A到B的第一阶段中,A为起点,B1和B2为终点,这里就存在两种情况供选择。
同理,在第2和第3阶段都存在多种情况供选择。现在的问题是:如何在每个阶段都作出一个恰当的决策,使由这些决策组成的一个决策序列所构成的一条线路的总距离最短。
问题提出
一个容易想到的方法是愚公移山的想法(exhaustivesearch),即穷举法。
将从A到E的所有可能路线的距离都计算出来,然后两两互相比较,找出最短路线。
其缺点是计算比较复杂。
问题提出
实际上,求从A到E的最短距离问题,可以转化为两个性质完全相同,但规模较小的子问题
即分别从B1、B2到E的最短路径问题,这时,从A到E的最短距离(记为SD(A))问题可以表示为:
动态规划法
同样,计算SD(B1)又可以归结为性质完全相同,但规模更小的问题,即分别求C1,C2,C3到E的最短路径问题SD(Ci)(i=1,2,3),
而求SD(Ci)又可以归结为求SD(D1)和SD(D2)两个子问题。由于SD(D1)和SD(D2)是已知的,因此,可以从这两个值开始,逆向递归计算出SD(A)的值。
最终,可以得到从A到E的最短路径。
上述求解的方法称为动态规划法(DynamicProgramming)。
2动态规划法概述
。
(1)基本思想
在现实生活中,有一类问题可以将其活动过程分解成若干个相互联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。
在每个阶段所作的决策选择依赖于当前状态,又影响它以后的发展。当各个阶段决策确定后,就组成一个决策序列,从而就确定了整个过程的一条活动路线。
这种将一个问题看作是一个前后相互关联且具有链状结构的多阶段过程称为多阶段决策过程。如图所示。其中,“状态”是指各决策阶段开始时的客观条件。
(1)基本思想
在多阶段决策过程中,某一阶段会存在多个决策序列,如果在进行决策时遵循如下原则:
求解过程为自底向上(即从终点到起点),每一步的选择总是依赖于上一步的选择,且此步仅仅把不可能的决策序列排除在外。
则这种解决多阶段决策的最优化的过程称为动态规划法。