算法设计与分析 第6章 动态规划法.ppt

第六章动态规划法
1
2
3
4
概述
图问题中的动态规划法
组合问题中的动态规划法
5
查找问题中的动态规划法
小结
五个海盗抢了一百颗钻石,每颗都价值连城。五个海盗都很贪婪,他们都希望自己能分得最多的钻石,但同时又都很明智。于是他们按照抽签的方法排出一个次序。首先由抽到一号签的海盗说出一套分钻石的方案,如果5个人中有50%(或以上)的人同意,那么便依照这个方案执行,否则的话,这个提出方案的人将被扔到海里喂鱼,接下来再由抽到二号签的海盗继续说出一套方案,然后依次类推到第五个。记住,五个海盗都很聪明哦!
海盗分钻石问题
你想到了什么?
历史及研究问题
动态规划是运筹学的一个分支,20世纪50年代初美国数学家Bellman等人在研究多阶段决策过程的优化问题时,提出了著名的最优性原理,创立了解决这类过程优化问题的新方法——动态规划法。
多阶段决策问题:求解的问题可以划分为一系列相互联系的阶段,每个阶段都需要做出决策,而且一个阶段决策的选择会影响下一个阶段的决策,从而影响整个过程的活动路线,求解的目标是选择各个阶段的决策是整个过程达到最优。
动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),可以人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。
动态规划是考察问题的一种途径,或是求解某类问题的一种方法。
动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比其它方法求解更为方便。
历史及研究问题
概述——多阶段决策过程
当某问题有n个输入,问题的解由这n个输入的一个子集组成,这个子集必须满足某些事先给定的条件,这些条件称为约束条件,满足约束条件的解称为问题的可行解。满足约束条件的可行解可能不只一个,为了衡量这些可行解的优劣,通常以函数的形式给出一定的标准,这些标准函数称为目标函数(或评价函数),使目标函数取得极值(极大或极小)的可行解称为最优解,这类问题称为最优化问题。
概述——多阶段决策过程
在0/1背包问题中,物品i或者被装入背包,或者不被装入背包,设xi表示物品i装入背包的情况,则当xi=0时,表示物品i没有被装入背包,xi=1时,表示物品i被装入背包。根据问题的要求,有如下约束条件和目标函数:
付款问题:超市的自动柜员机(POS机)要找给顾客数量最少的现金。
假定POS机中有n张面值为pi(1≤i≤n)的货币,用集合P={p1, p2, …, pn}表示,若POS机需支付的现金为A,则必须从P中选取一个最小子集S,使得
()
如果用向量X=( x1, x2, …, xn)表示S中所选取的货币,则
()
最优化问题
则,POS机支付的现金必须满足
()
集合P是该问题的输入,,,因向量X中有n个元素,每个元素的取值为0或1,所有这些向量的全体构成该问题的解空间,,,。
并且
()
最优化问题
最优性原理
①状态:表示每个阶段开始时,问题或系统所处的客观状况。状态既是该阶段的某个起点,又是前一个阶段的某个终点。通常一个阶段有若干个状态。
状态无后效性:如果某个阶段状态给定后,则该阶段以后过程的发展不受该阶段以前各阶段状态的影响,也就是说状态具有马尔科夫性。
适于动态规划法求解的问题具有状态的无后效性
②策略:各个阶段决策确定后,就组成了一个决策序列,该序列称之为一个策略。由某个阶段开始到终止阶段的过程称为子过程,其对应的某个策略称为子策略。
最优性原理
具有n个输入的最优化问题,其求解过程划分为若干个阶段,每一阶段的决策仅依赖于前一阶段的状态,由决策所采取的动作使状态发生转移,成为下一阶段决策的依据。
一个决策序列在不断变化的状态中产生。这个决策序列产生的过程称为多阶段决策过程。
S0
P1
P2
Pn
S1
S2
Sn-1
Sn