算法设计与分析chap8(dynamic programming2014)

计算二项式系数
二项式系数(Binomial Coefficient )
是n元素集合中k个元素组合的数量(0≤k ≤n)，记作 C(n.k)或者Cnk，来源于二项式公式：
(a+b)n=Cn0an+…+Cnian-ibi+…+Cnnbn
Cn0=Cnn=1
递推关系式：
当n>k>0时，Cnk=Cn-1k-1+Cn-1k
10
标准动态规划的基本框架 1. 2. 3. 4. 5. 6. 7. 对fn+1(xn+1)初始化; {边界条件} for k:=n downto 1 do for 每一个xk∈Xk do for 每一个uk∈Uk(xk) do begin fk(xk):=一个极值; xk+1:=Tk(xk,uk); t:=φ(fk+1(xk+1),vk(xk,uk)); {∞或－∞} {状态转移方程} {基本方程(9)式}
15
多段图
multistage graph problem
s
v2 v3
vk-1
t
Forward approach Backward approach
证最佳原理成立
多段图(multistage graph problem)
V1 9 V2 V3 1 V4 6 5 3 5 4 V5
2
2
7 3
s 1
2
3
算法分析与设计
动态规划
Dynamic programming
动态规划的定义
动态规划(Dynamic programming)是一种算法设计技术， 是用来解决一种多段决策过程最优的通用方法。 多段决策过程最优

第38页
安师大数学计算机科学学院
2014年6月28日星期六
1.4.3 归纳证明
定理1-1 对于n≥0，程序1-5是正确的。 证明：（归纳法证明） 当n是1位数时，程序显然是正确的。 假定函数PrintDigit对所有位数小于k（k＞1）的正 整数都能正确运行，当 n 的位数为 k 位时，此时有 n≥10 ，算法必定先执行语句 cout<<n%10; 然后执 行语句if(n>10) PrintDigit(n/10);。
第31页
安师大数学计算机科学学院
2014年6月28日星期六
可以用所谓的递归树（recursive tree）来描述程 序1-4的函数Fib执行时的调用关系。
图1-2 计算Fib（4）的递归树
第32页
安师大数学计算机科学学院
2014年6月28日星期六
递归数据结构 使用递归方式定义的数据结构称为递归数据结构 （recursive data structure）。
第10页
Begin
Rm%n
Y
r=0？ N
Swap(m.n)
End
安师大数学计算机科学学院
2014年6月28日星期六
假设 m=21 和 n=45，求21和45的最大公因子
第一步：r=m%n=21%45=21； 第二步：r 不等于0，转入第三步； 第三步：互换，m=n=45, n=r=21，返回第一步。 第一步：r=m%n=45%21=3； 第二步：r 不等于0，转入第三步； 第三步：互换，m=n=21 ， n=r=3，返回第一步。 第一步：r=m%n=21%3=0； 第二步：r 等于0，算法结束，3即为21和45的最大公因子。
2014年6月28日星期六

都变成负值为止
Department of Electronic Information
30
Fun Time
z
=
9
+
21x2
−
3 4
x4
−
2x5,
s.t.
x3
−
1 2
x2
+
41x4
=
3
x1 x6
+ −
5 2
x2
5 2
x2
+ −
41x4 43x4
+ +
2x5 = 10 +8x5 = 1
• 选出使目标函数增加的非基本变量作为入基变量 • z 行中的正系数非基本变量都满足要求
Department of Electronic Information
24
单纯形表
max z = −x2 + 3x3 − 2x5,
s.t.
x1
+
3x2
−
x3
+
2x5
=
7
x4 − 2x2 + 4x3 = 12
x2 x3 x5
z 0 -1 3 -2 x1 7 3 -1 2 x4 12 -2 4 0 x6 10 -4 3 8
Department of Electronic Information
23
单纯形算法的第 1 步–选取入基变量
• 查看单纯形表的第 1 行（也称之为 z 行）中标有非 基本变量的各列中的值
2x2 − 7x4 ≤ 0 x1 + x2 + x3 + x4 = 9
x2 − x3 + 2x4 ≥ 1 xi ≥ 0, i = 1, 2, 3, 4

2
ACM国际大学生程序设计竞赛
ACM国际大学生程序设计竞赛（英文 全称：ACM International Collegiate Programming Contest（ACM-ICPC或 ICPC）是由美国计算机协会（ACM）主办 的，一项旨在展示大学生创新能力、团队 精神和在压力下编写程序、分析和解决问 题能力的年度竞赛。经过30多年的发展， ACM国际大学生程序设计竞赛已经发展成 为最具影响力的大学生计算机竞赛。赛事 目前由IBM公司赞助。
主要内容介绍（续）
• • • • 第 7章 第 8章 第 9章 第10章 概率算法 NP完全性理论 近似算法 算法优化策略
1
相关先导基础课程和算法概述
专业基础课程： 数据结构、计算机语言(C++)、操作系统 如何编写计算机程序： • 数据结构+算法 = 程序 • 算法：计算机软件的“灵魂” 算法是计算机科学和计算机应用的核心
1.2 算法复杂性分析
Ω的定义：如果存在正的常数C和自然数N0，使得当NN0时 有f(N)Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它 的一个下界，记为f(N)=Ω (g(N))。即f(N)的阶不低于g(N)的阶。 θ的定义：定义f(N)= θ (g(N))当且仅当f(N)=O(g(N))且 f(N)= Ω (g(N))。此时称f(N)与g(N)同阶。 o的定义：对于任意给定的ε＞0，都存在正整数N0，使得 当NN0时有f(N)/Cg(N)ε,则称函数f(N)当N充分大时的阶比 g(N)低，记为f(N)=o(g(N))。 例如，4NlogN+7=o(3N2+4NlogN+7)。
调试：“调试只能指出有错误，而不能指出它们不存在 错误” 9 作时空分布图：验证分析结论，优化算法设计