资源描述：
《《动态规划法》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第6章动态规划法6.1概述6.2图问题中的动态规划法6.3组合问题中的动态规划法6.4查找问题中的动态规划法6.5实验项目——最大子段和问题6.1概述6.1.1最优化问题6.1.2最优性原理6.1.3动态规划法的设计思想最优化问题：有n个输入，它的解由这n个输入的一个子集组成，这个子集必须满足某些事先给定的条件，这些条件称为约束条件，满足约束条件的解称为问题的可行解。满足约束条件的可行解可能不只一个，为了衡量这些可行解的优劣，事先给出一定的标准，这些标准通常以函数的形式给出，这些标准函数称为目标函数，使目标函数
2、取得极值（极大或极小）的可行解称为最优解，这类问题就称为最优化问题。6.1.1最优化问题例：付款问题：超市的自动柜员机（POS机）要找给顾客数量最少的现金。假定POS机中有n张面值为pi(1≤i≤n)的货币，用集合P={p1,p2,…,pn}表示，如果POS机需支付的现金为A，那么，它必须从P中选取一个最小子集S，使得（式6.1）如果用向量X=(x1,x2,…,xn)表示S中所选取的货币，则（式6.2）那么，POS机支付的现金必须满足（式6.3）并且（式6.4）在付款问题中，集合P是该问题的输入，满足式6.1的
3、解称为可行解，式6.2是解的表现形式，因为向量X中有n个元素，每个元素的取值为0或1，所以，可以有2n个不同的向量，所有这些向量的全体构成该问题的解空间，式6.3是该问题的约束条件，式6.4是该问题的目标函数，使式6.4取得极小值的解称为该问题的最优解。6.1.2最优性原理对于一个具有n个输入的最优化问题，其求解过程往往可以划分为若干个阶段，每一阶段的决策仅依赖于前一阶段的状态，由决策所采取的动作使状态发生转移，成为下一阶段决策的依据。从而，一个决策序列在不断变化的状态中产生。这个决策序列产生的过程称为多阶段决
4、策过程。S0P1P2Pn多阶段决策过程S1S2Sn-1SnSn-1SnS1S0s1,1sn,knp1,1s1,k1p1,k1s1,r1………sn-1,kn-1pn,kn…pn-1,kn-1…动态规划的决策过程sn-1,1……sn-1,rn-1sn,1sn,rn……在每一阶段的决策中有一个赖以决策的策略或目标，这种策略或目标是由问题的性质和特点所确定，通常以函数的形式表示并具有递推关系，称为动态规划函数。多阶段决策过程满足最优性原理（OptimalPrinciple）：无论决策过程的初始状态和初始决策是什么，其余
5、的决策都必须相对于初始决策所产生的当前状态，构成一个最优决策序列。如果一个问题满足最优性原理通常称此问题具有最优子结构性质。6.1.3动态规划法的设计思想动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。原问题的解原问题……填表子问题1子问题2子问题n动态规划法的求解过程
6、n=5时分治法计算斐波那契数的过程。F(5)F(4)F(3)F(3)F(2)F(2)F(1)F(2)F(1)F(1)F(0)F(1)F(0)F(1)F(0)例：计算斐波那契数：01234567890112358132134动态规划法求解斐波那契数F(9)的填表过程：注意到，计算F(n)是以计算它的两个重叠子问题F(n-1)和F(n-2)的形式来表达的，所以，可以设计一张表填入n+1个F(n)的值。用动态规划法求解的问题具有特征：能够分解为相互重叠的若干子问题；满足最优性原理（也称最优子结构性质）：该问题的最优解
7、中也包含着其子问题的最优解。（用反证法）分析问题是否满足最优性原理：先假设由问题的最优解导出的子问题的解不是最优的;然后再证明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。动态规划法设计算法一般分成三个阶段：（1）分段：将原问题分解为若干个相互重叠的子问题；（2）分析：分析问题是否满足最优性原理，找出动态规划函数的递推式；（3）求解：利用递推式自底向上计算，实现动态规划过程。动态规划法利用问题的最优性原理，以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。6.2图问题中的动态规划法6.2.
8、1TSP问题6.2.2多段图的最短路径问题6.2.1TSP问题TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。各个城市间的距离可以用代价矩阵来表示。C=∞3675∞2364∞2375∞带权图的代价矩阵设s,s1,s2,…,sp,s是从s出发的一条路径长度最短的简单回路，假设从s到下一个城市s1已经求出，则问题转化为求从s1到s的最
