算法设计与分析_王红梅_第6章 动态规划法-课件（PPT讲稿）.ppt

算法设计与分析清华大学出版社第6章动态规划法 概述 图问题中的动态规划法 组合问题中的动态规划法 查找问题中的动态规划法 实验项目——最大子段和问题算法设计与分析清华大学出版社 概述 最优化问题 最优性原理 动态规划法的设计思想算法设计与分析清华大学出版社最优化问题:有 n个输入,它的解由这 n 个输入的一个子集组成,这个子集必须满足某些事先给定的条件,这些条件称为约束条件,满足约束条件的解称为问题的可行解。满足约束条件的可行解可能不只一个,为了衡量这些可行解的优劣,事先给出一定的标准,这些标准通常以函数的形式给出,这些标准函数称为目标函数,使目标函数取得极值(极大或极小)的可行解称为最优解,这类问题就称为最优化问题。 最优化问题算法设计与分析清华大学出版社例:付款问题: 超市的自动柜员机( POS 机)要找给顾客数量最少的现金。假定 POS 机中有 n 张面值为 p i (1≤i≤n) 的货币,用集合 P ={p 1, p 2, …, p n}表示,如果 POS 机需支付的现金为 A,那么, 它必须从 P中选取一个最小子集 S,使得(式 ) ????? mi iiSmApSp 1 |)|(,如果用向量 X=( x 1, x 2, …, x n)表示 S中所选取的货币,则(式 ) ??????Sp Spx i ii0 1 算法设计与分析清华大学出版社那么, POS 机支付的现金必须满足(式 ) Apx ni ii???1并且(式 ) ??? ni ixd 1 min 在付款问题中,集合 P是该问题的输入,满足式 的解称为可行解,式 是解的表现形式,因为向量 X中有 n个元素,每个元素的取值为 0或1,所以,可以有 2 n个不同的向量,所有这些向量的全体构成该问题的解空间,式 是该问题的约束条件,式 是该问题的目标函数,使式 取得极小值的解称为该问题的最优解。算法设计与分析清华大学出版社 最优性原理对于一个具有 n 个输入的最优化问题,其求解过程往往可以划分为若干个阶段,每一阶段的决策仅依赖于前一阶段的状态,由决策所采取的动作使状态发生转移,成为下一阶段决策的依据。从而, 一个决策序列在不断变化的状态中产生。这个决策序列产生的过程称为多阶段决策过程。 S 0P 1P 2P n 多阶段决策过程 S 1S 2S n -1S n 算法设计与分析清华大学出版社 S n -1S n S 1S 0s 1,1s n,kn p 1,1s 1,k1p 1,k1s 1,r1 ………s n -1, kn -1p n,kn …p n -1, kn -1 …动态规划的决策过程 s n -1,1…… s n -1, rn -1 s n,1s n, rn ……算法设计与分析清华大学出版社在每一阶段的决策中有一个赖以决策的策略或目标, 这种策略或目标是由问题的性质和特点所确定,通常以函数的形式表示并具有递推关系,称为动态规划函数。多阶段决策过程满足最优性原理( Optimal Principle ): 无论决策过程的初始状态和初始决策是什么,其余的决策都必须相对于初始决策所产生的当前状态,构成一个最优决策序列。如果一个问题满足最优性原理通常称此问题具有最优子结构性质。算法设计与分析清华大学出版社 动态规划法的设计思想动态规划法将待求解问题分解成若干个相互重叠的子问题,每个子问题对应决策过程的一个阶段, 一般来说,子问题的重叠关系表现在对给定问题求解的递推关系(也就是动态规划函数)中,将子问题的解求解一次并填入表中,当需要再次求解此子问题时,可以通过查表获得该子问题的解而不用再次求解,从而避免了大量重复计算。算法设计与分析清华大学出版社原问题的解原问题……填表子问题 1子问题 2子问题 n 动态规划法的求解过程