第6章 动态规划法(完)
更新时间:2023-06-03 05:28:01 阅读量: 实用文档 文档下载
- 机器人大乱斗第6章推荐度:
- 相关推荐
算法设计与分析 清华大学出版社 (第二版)PPT课件
第6章 动态规划法
算法设计与分析 清华大学出版社 (第二版)PPT课件
第6章 动态规划法6.1 概 述6.2 图问题中的动态规划法
6.3 组合问题中的动态规划法6.4 查找问题中的动态规划法 6.5 实验项目——最大子段和问题
Page 2
第6章 动态规划法
2014-6-17
算法设计与分析 清华大学出版社 (第二版)PPT课件
6.1 概 述6.1.1 最优化问题 6.1.2 最优性原理
6.1.3 动态规划法的设计思想
Page 3
第6章 动态规划法
2014-6-17
算法设计与分析 清华大学出版社 (第二版)PPT课件
第6章 动态规划法 付款问题:
超市的自动柜员机( POS 机)要找给顾
客数量最少的现金。例如,要找4元6角 现金,可以找46个1角钱,但最好是找2 个 2元、 1个5角和 1个 1角,这样总的数 量只有4张,是最少的。
Page 4
第6章 动态规划法
2014-6-17
算法设计与分析 清华大学出版社 (第二版)PPT课件
假定 POS 机中有 n 张面值为 pi(1≤i≤n) 的货币,用集合 P={p1, p2, …, pn}表示,如果POS机需支付的现金为A,那么,它必 须从P中选取一个最小子集S,使
pi S ,
pi 1
m
i
A (m | S |)
(式6.1)
满足式6.1的解是可行解
例如,假设POS机里有4个2元,2个1元,3个5角,4个2角和 1个1角。 2,2,2,2, 1,1, 0.5,0.5,0.5, 0.2,0.2,0.2,0.2, 0.1
需要找4.6元,则可行解有: 4.6=2+2+0.5+0.1 4.6=2+1+1+0.5+0.1 ……Page 5 第6章 动态规划法 2014-6-17
算法设计与分析 清华大学出版社 (第二版)PPT课件
如果用向量X=( x1, x2, …, xn)表示S中所选取的货币,则
1 xi 0
pi S
pi S
(式6.2)
式6.2是解的表现形式2,2,2,2, 1,1, 0.5,0.5,0.5, 0.2,0.2,0.2,0.2, 0.1 对于可行解 4.6=2+2+0.5+0.1 解的表现形式为: 1,1,0,0, 0,0, 1,0,0, 0,0,0,0, 1 对于可行解 4.6=2+1+1+0.5+0.1 解的表现形式为: 1,0,0,0, 1,1, 1,0,0,, 0,0,0,0, 1 ……Page 6 第6章 动态规划法 2014-6-17
算法设计与分析 清华大学出版社 (第二版)PPT课件
那么,n POS机支付的现金必须满足
xi 1
i
pi A
(式6.3)
式6.3的解是约束条件
4.6=2+2+0.5+0.1 2,2,2,2, 1,1, 0.5,0.5,0.5, 0.2,0.2,0.2,0.2, 0.1 1,1,0,0, 0,0, 1, 0, 0, 0, 0, 0, 0, 1 1*2+1*2+0*2+0*2+…+0*0.2+0*0.2+1*0.1=4.6 n 并且
d min xii 1
(式6.4)
式6.4的解是目标函数
对于可行解 4.6=2+2+0.5+0.1 d=4 对于可行解 4.6=1+1+1+1+0.5+0.1 d=6
使式6.4取得极小值的解称为该问题的最优解Page 7 第6章 动态规划法 2014-6-17
算法设计与分析 清华大学出版社 (第二版)PPT课件
那么,POS机支付的现金必须满足
xi 1并且
n
i
pi An i 1
(式6.3)
d min xi
(式6.4)
在付款问题中,集合P是该问题的输入,满足式6.1的 解称为可行解,式6.2是解的表现形式,因为向量X中有n个 元素,每个元素的取值为0或1,所以,可以有2n个不同的 向量,所有这些向量的全体构成该问题的解空间,式6.3是 该问题的约束条件,式6.4是该问题的目标函数,使式6.4取 得极小值的解称为该问题的最优解。Page 8 第6章 动态规划法 2014-6-17
算法设计与分析 清华大学出版社 (第二版)PPT课件
6.1.1 最优化问题 最优化问题:有n个输入,它的解由这n个输入的一 个子集组成,这个子集必须满足某些事先给定的条件, 这些条
件称为约束条件,满足约束条件的解称为问题 的可行解。满足约束条件的可行解可能不只一个,为 了衡量这些可行解的优劣,事先给出一定的标准,这 些标准通常以函数的形式给出,这些标准函数称为目 标函数,使目标函数取得极值(极大或极小)的可行 解称为最优解,这类问题就称为最优化问题。
Page 9
第6章 动态规划法
2014-6-17
算法设计与分析 清华大学出版社 (第二版)PPT课件
6.1.2 最优性原理对于一个具有 n 个输入的最优化问题,其求解 过程往往可以划分为若干个阶段,每一阶段的决策 仅依赖于前一阶段的状态,由决策所采取的动作使 状态发生转移,成为下一阶段决策的依据。从而, 一个决策序列在不断变化的状态中产生。这个决策 序列产生的过程称为多阶段决策过程。S0 P1
S1
P2
S2
Sn-1
Pn
Sn
多阶段决策过程Page 10 第6章 动态规划法 2014-6-17
算法设计与分析 清华大学出版社 (第二版)PPT课件
-2 剩2.6
-2 剩0.6
-0.5 剩0.1 -0.2 剩0.4
-0.1 剩0 (4张) -0.2 剩0.2 -0.2 (5张) 剩0 -0.1 剩0.1 -0.1 (6张) 剩0
-0.1 剩0.34.6 -1 剩1.6 -0.1 剩0.5 -1 剩0.6 -0.1 剩0.4 -0.5 剩0.1
-0.1 剩0.2-0.1 剩0.3
-0.1 剩0.1-0.1 剩0.2
-0.1 (7张) 剩0-0.1 剩0.1 -0.1 剩0
-0.1 剩0 (5张)
(8张)
Page 11
第6章 动态规划法
2014-6-17
算法设计与分析 清华大学出版社 (第二版)PPT课件
可以把每一阶段作为一个子问题来处理,然后按顺序 求解各个子问题。 最优决策是在最后阶段形成的,然后向前推导,直到 初始阶段,得到一个最优决策序列。 在每一阶段的决策中有一个赖以决策的策略或目标, 这种策略或目标是由问题的性质和特点所确定,通常 以函数的形式表示并具有递推关系,称为动态规划函 数。Page 12 第6章 动态规划法 2014-6-17
算法设计与分析 清华大学出版社 (第二版)PPT课件
S1 …
Sn-1 sn-1,1 …
Snsn,1
s1,1p1,1
S0
p1,k1
s1,k1
……
pn-1,kn-1
sn-1,kn-1
pn,kn
… …
sn,kn
… …
s1,r1
sn-1,rn-1
sn,rn
…
动态规划的决策过程Page 13 第6章 动态规划法 2014-6-17
算法设计与分析 清华大学出版社 (第二版)PPT课件
多阶段决策过程满足最优性原理(Optimal Principle):无论决策过程的初始状态和初始决策是 什么,其余的决策都必须相对于初始决策所产生的当 前状态,构成一个最优决策序列。 即,在多阶段决策中,各子问题的解只与它前面的子 问题的解有关,并且各子问题的解都是相对于当前状 态的最优解,整个问题的最优解是由各个子问题的最 优解构成。 如果一个问题满足最优性原理通常称此问题具有最优 子结构性质。Page 14 第6章 动态规划法 2014-6-17
算法设计与分析 清华大学出版社 (第二版)PPT课件
A
B
C
D
E
原问题E的解依赖于子问题C和D的解,子问题 D的解依赖于子问题C和B的解,子问题C的解 依赖于子问题A和B的解,子问题B的解依赖于 子问题A的解,因此,动态规划的求解过程从 初始子问题A开始,逐步求解并记录各子问题 的解,直至得到原问题E的解。P
age 15 第6章 动态规划法 2014-6-17
算法设计与分析 清华大学出版社 (第二版)PPT课件
6.1.3 动态规划法的设计思想动态规划法将待求解问题分解成若干个相互重 叠的子问题,每个子问题对应决策过程的一个阶段, 一般来说,子问题的重叠关系表现在对给定问题求 解的递推关系(也就是动态规划函数)中,将子问 题的解求解一次并填入表中,当需要再次求解此子 问题时,可以通过查表获得该子问题的解而不用再 次求解,从而避免了大量重复计算。
Page 16
第6章 动态规划法
2014-6-17
算法设计与分析 清华大学出版社 (第二版)PPT课件
例:计算斐波那契数: 0 F ( n) 1 F (n 1) F (n 2)
n 0 n 1 n 2
n=5时分治法计算斐波那契数的过程。F(5) F(4) F(3) F(2) F(0) F(1) F(2) F(0) F(3) F(1)
F(2)F(1)Page 17
F(1) F(1) F(0)
第6章 动态规划法
2014-6-17
算法设计与分析 清华大学出版社 (第二版)PPT课件
注意到,计算F(n)是以计算它的两个重叠子问 题 F(n-1)和F(n-2)的形式来表达的,所以,可以设 计一张表填入n+1个F(n)的值。 动态规划法求解斐波那契数F(9)的填表过程 : 0 0 1 1 2 1 3 2 4 3 5 5 6 8 7 8 9 13 21 34
Page 18
第6章 动态规划法
2014-6-17
算法设计与分析 清华大学出版社 (第二版)PPT课件
动态规划法的求解过程原问题
子问题1
子问题2
……
子问题n
填 表 原问题的解Page 19 第6章 动态规划法 2014-6-17
算法设计与分析 清华大学出版社 (第二版)PPT课件
用动态规划法求解的问题具有特征: 能够分解为相互重叠的若干子问题; 满足最优性原理(也称最优子结构性质): 该问题的最优解中也包含着其子问题的最优 解。
(用反证法)分析问题是否满足最优性原理: 1. 先假设由问题的最优解导出的子问题的解不 是最优的(即先假设问题的最优解中不包含 其子问题的最优解); 2. 然后再证明在这个假设下可构造出比原问题 最优解更好的解,从而导致矛盾。Page 20 第6章 动态规划法 2014-6-17
算法设计与分析 清华大学出版社 (第二版)PPT课件
动态规划法设计算法一般分成三个阶段: (1)分段:将原问题分解为若干个相互重叠的子 问题; (2)分析:分析问题是否满足最优性原理,找出 动态规划函数的递推式; (3)求解:利用递推式自底向上计算,实现动态 规划过程。 动态规划法利用问题的最优性原理,以自底向 上的方式从子问题的最优解逐步构造出整个问 题的最优解。Page 21 第6章 动态规划法 2014-6-17
正在阅读:
第6章 动态规划法(完)06-03
噶米城市道路施工图设计中的块石挡土墙设计注意事项(43个要点)12-27
女生空乘面试自我介绍02-24
高考英语易考词汇变形归纳与总结04-20
合作社的发展对农药经销渠道的挑战与机遇20121126郑州农药V1.006-08
新安全生产法主要负责人和安全管理人员职责09-04
经典诵读三百篇04-27
竞争法在经济法中的地位01-21
CAD技巧120个绝对实用05-26
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 规划法
- 动态
- 关系代数、SQL查询测验答案
- 高中生物竞赛辅导:第五章 遗传学与进化
- 新课标I版02期 2014届高三名校数学理试题分省分项汇编 专题10 立体几何 Word版含解析
- 机场信息化建设ESB的设计
- 小学标点符号练习题及答案
- 常用的E-mail中英文对照
- 心血管和肾科团队知识比赛题库20160108
- 植物配植一览总表
- 七年级数学上册 第一章 1.2展开与折叠(一)教学设计 北师大版
- 锅炉突发事故专项应急预案
- 高二期中考试后家长会发言稿
- 知名跨国纺织服饰公司高管名单全国
- 微型定量自动投饵机的设计_周晓林
- 神魔大陆副本攻略 王城地狱难度通关技巧
- Office 高级应用教案6
- 中学数学数形结合论
- 2011届高考英语完形填空专项练习题
- 核电站汽轮机冷端系统优化
- 全国计算机应用能力考试
- 【安康职业技术学院排名】安康职业技术学院特色专业-安康职业技术学院录取分数线