第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

本文来源：https://www.bwwdw.com/article/qfs1.html