中科院陈玉福算法课件ch8ppt

第四章 贪心算法
算法基本思想 调度问题 最小生成树问题 单点源最小路径问题 Huffman编码
贪心算法的基本思想
找零钱：给孩子找回87分硬币，现有硬币规格50分、10分、 5分、2分、1分。 50+3*10+5+2＝87 一般方法：尽量找面值大的硬币。 装箱问题：有物品n件，重量分别是 w1,…,wn ; 有箱子m个： B1,…，Bm，每个的容量都是C(C≥wi)。设计装箱方法，使得 所用箱子最少。 1. NF(Next Fit)方法：前面的箱子不能再装了，才开始装下一 个箱子。 2. FF(First Fit)方法：每个物品都选择装进第一个可装的箱子 贪心算法的基本思想： 在每一步决策中总是作出在当前看来是最好的选择 贪心准则，局部最优。
=1≤iΒιβλιοθήκη ≤n∑ pyi i
贪心算法抽象控制流程
proc Greedy(A, n) // A[1:n]代表输入 solution={}; //解初始化为空集 for i to n do x:=Select(A); if Feasible(solution, x) then solution:=Union(solution, x); end{if} end{for} return(solution); end{Greedy} Select(A)是按照贪心 准则选取A中的输入 项； Feasible(solution, x)是 判断已知的解的部分 solution与新选取的x 的结合是否是可行 解。 Union(solution, x)x与 已经选到的部分 solution结合成解的更 大部分
GreedyJob获得最优解
假设贪心算法所选择的作业集J不是最优解，则一定有相容作 业集I，其产生更大的效益值。假定I是具有最大效益值的相容作 业集中使得|I∩J|最大者，往证 I=J。 反证法：若I=J 不成立，则这两个作业集合之间没有包含关 系。这是因为算法GreedyJob的特性和假定I 产生的效益值比J的 效益值更大。假设a是J\I中具有最大效益的作业，即J中比a具有 更大效益的作业(如果有的话)都应该在 I 中。如果作业 b∈I\J 且 pb>pa，那么由算法中对J中作业的选取办法（相容性要求），J中 至少有 fb个效益值≥pb的作业，其期限值≤ fb。这些作业一定在 I 中，因而 I 中至少有个fb+1作业，其期限值≤ fb ，这与 I 的相容性 矛盾。所以，I\J中事件的效益值均不超过pa。 称区间[k-1,k]为时间片k，相容作业集 I 的一个调度表就是指定 I 中各个作业的加工时间片。如果 I 有一个调度表 S 将时刻 fa前 的时间片均安排给I∩J中的作业，且I\J中最早被安排的是作业b， 在时间片k上，则k>fa。

A B D E F
C
A B C
B A A B B C C D
C D F H H H H E
0 E 0 G 0 0 0 0 F G 0 0
G
D E
H
F G
图G和它的邻接链表
1 A 2 B 4 D E H 5 6 F G C 7 3
H
1 A 2 B 3 D E H 5 6 F G C 8 7
8
4
图G的宽度优先搜索树
Vertex 1 Vertex 2
2 3 0
4 0 Vertices
Vertex 3 Empty list Edges Vertex 4 2 3 0
1 2 3 4 5 6 7 8 9
(c)
(d)
图的遍历算法
有根树
如果指定树的一个顶点为根，则这棵树称为有根树。在有 根树中，邻接根的顶点称为根的儿子，而根称为这些儿子 的父亲。对于不是根的顶点，除了它的父亲之外其它与之 邻接的顶点都称为该顶点的儿子，该顶点也自然称为它的 这些儿子的父亲。没有儿子的顶点称为叶顶点。 从根到每一个叶顶点都有一条唯一的路，这些路的最长者 的长度称为该树的高度；顶点的高度是以它为根的子树的 高度；顶点的深度是从根顶点到它的路的长度。深度相同 的顶点成为同层的。
⎡1 ⎢1 ⎢ ⎢0 ⎢ M = ⎢0 ⎢0 ⎢ ⎢0 ⎢0 ⎣ 0 1 0 0 0 0⎤ 1 0 0 0 0 0⎥ ⎥ 1 1 0 0 0 0⎥ ⎥ 0 0 1 0 0 0⎥ 0 0 1 1 1 0⎥ ⎥ 0 0 0 1 0 1⎥ 0 0 0 0 1 1⎥ ⎦
右边的图不是连通的，有两个连 通分支。它含有两个圈，不是 树。
算法BFS的复杂性分析
空间复杂度为 S (n, m) = O(n) ； 时间复杂度，当G用邻接矩阵表示时：T (m, m) = O(n 2 )； 当G由邻接链表表示时， T (n, m) = O(n + m) 。 除结点v外，只有当结点w满足Visited(w)=0时才被加到队列上， 然后，Visited(w)的值马上被修改增加1.因此每个结点有一次机 会被放到队列上。需要的队列空间至多是n-1，其余变量所用 的空间为O(1)，S(n,m)=O(n)。 在极端情况下，v邻接于全部其 他n-1个结点，此时队列需要n-1的空间。又Visited需要Θ(n)的 空间，所以S(n,m)=Θ(n)。 如果使用邻接链表，语句4的for循环要做d(u)次，而语句3～11的 while循环需要做n次，因而整个循环做∑d(u)=2m次O(1)操 作，又Visited的赋值需要n次操作，因而T(n,m)=Θ(n+m)。 如果采用邻接矩阵，则语句3～11的while循环总共需要做n2次O(1) 操作，Visited赋值需要n操作，因而T(n,m)=Θ(n2)。

背包问题 已知容量为 M 的背包和 n 件物品。第 i 件物品的重量为 wi ，价值
是 pi 。因而将物品 i 的一部分 xi 放进背包即获得 pi xi 的价值。问题是：怎样装包 使所获得的价值最大？即是如下的优化问题：
84
第四章 贪心算法
max ∑ pi xi 1≤ i ≤ n
(4.1.3)
∑ wi xi ≤ M
n=3, M=20, p=(25, 24, 15), w=(18,15,10) 如果以价值最大为贪心准则，则贪心算法的执行过程是：首先考虑将物品 1 装包， 此时获得效益值 25，包的剩余容量是 2。然后考虑将物品 2 装包，但物品 2 的重 量 15 超出包的剩余容量，只能装入该种物品的 2/15，此时获得的总效益值为
第四章 贪心算法
83
第四章 贪心算法
§1.贪心算法基本思想
找零钱 假如售货员需要找给小孩 67 美分的零钱。现在，售货员手中只有 25 美分、10 美分、5 美分和 1 美分的硬币。在小孩的催促下，售货员想尽快将 钱找给小孩。她的做法是：先找不大于 67 美分的最大硬币 25 美分硬币，再找不 大于 67－25＝42 美分的最大硬币 25 美分硬币，再找不大于 42－25＝17 美分的 最大硬币 10 美分硬币，再找不大于 17－10＝7 美分的最大硬币 5 美分硬币，最 后售货员再找出两个 1 美分的硬币。至此，售货员共找给小孩 6 枚硬币。售货员 的原则是拿尽可能少的硬币找给小孩。
证明 设 x = (x1, x2 ,L, xn ) 是 GreedyKnapsack 所生成的解，但不是最优解。
第四章 贪心算法
85
因而必有某个 xi 不为 1。不妨设 x j 是第一个这样的分量。于是，当1 ≤ i < j 时，

计算机算法设计与分析 The Design and Analysis of Computer Algorithms
中国科学院研究生院 陈玉福
关于计算机算法
计算机科学 是一种创造性思维活动，其教育必须面向设计； 计算机算法 是任何定义好了的计算程式，它取某些值或值 的集合作为输入，并产生某些值或值的集合作为输出。 计算机算法的特征 – 数据输入与输出； – 确定性： 算法的每一步计算（包括判断）必须要有确切 的定义，即每一步计算动作必须是清楚的，无二义性。
空间复杂性
考虑空间复杂性的理由
在多用户系统中运行时，需指明分配给该程序的内存 大小； 想预先知道计算机系统是否有足够的内存来运行该程 序； 用空间复杂性来估计一个程序可能解决的问题的最大 规模； 一个问题可能有若干个不同的内存需求解决方案，从 中择优。
指令空间: 存储编译后的程序指令
指令空间的大小取决于如下因素： 把程序编译成机器代码的编译器，编译器不同，则产 生的机器代码的长度就会有差异； 编译时实际采用的编译器选项，如优化模式、覆盖模 式，选用优化模式可缩短代码长度，但会增加运行时 间； 目标计算机的配置，如带有浮点处理硬件的，每个浮 点操作转换为一条机器指令，否则，必须生成仿真的 浮点计算代码，使整个机器代码加长。 一般情况下，指令空间对于所解决的特定问题不够敏 感。
– 可实现性：每种计算至少在原理上能由人用纸和笔在有
限的时间内完成。 – 有穷性： 一个算法总是在执行了有穷步之后终止。
关于算法设计与分析
如何设计算法：问题的数学模型、经典算法、分析改进。 如何表示算法：输入数据结构、描述算法的语言、算法 流程、逻辑结构。C++ 或 ALGEN（伪代码）。 如何分析算法：发现算法特性、估计对各种应用的适合 程度、相同应用中与其它算法的比较。确定输入数 据模型、确定每项基本操作所用时间及出现频率、 统计数据、分析推求。 如何测试算法：正确性、有穷性；白盒法、黑盒法。

MaxMin复杂性分析
• T(n)来表示MaxMin所用的元素比较数，则上述递归算法导出 一个递归关系式
n =1 ⎧0 ⎪ T (n) = ⎨1 n=2 ⎪ T( n/2 ) +T( n/2 ) + 2 n > 2 ⎤ ⎣ ⎦ ⎩ ⎡
• 当n是2的方幂时，设 n = 2 k ，有
•
• • •
T (n) = 2T (n / 2) + 2 = 2(2T (n / 4) + 2) + 2 L = 2k −1T (2) + = 3n / 2 − 2
以比较为基础的排序时间下界
每两个元素A[i]和A[j]的比较只 有两种可能： A[i]<A[j]或A[j]<A[i]， 形成二叉树。当A[i]<A[j]时进入 左分支，当A[i]>A[j] 进入右分 支。各个叶结点表示算法终止。 从根到叶结点的每一条路径与一 种唯一的排列相对应。由于n个 不同元素的不同排列共有n！个 因此比较树有n！个外部结点 。 比较树中最长路径的长度（其是 比较树的高）即是算法在最坏情 况下所做的比较次数。要求出所 有以比较为基础的排序算法在最 坏情况下的时间下界，只需求出 这些算法所对应的比较树的高度 的最小值。
k: 0, 1, 2, 3, 4, 5, 6, 7, 8 LINK : 2, 8, 5, 4, 7, 3, 0, 1, 6
使用链接表的归并排序程序
proc MergeSortL(low, high, p) // Link是全程数组A[low..high] //的下标表, p指示这个表的开始处。利用Link将A按非降 //顺序排列。 global A[low..high]; Link[low..high]; if high-low+1<16 then //设定子问题的最小规模Small InSort(A,Link, low,high,p)； else mid:=⎣(low+high)/2⎦； MergeSortL(low,mid,q); //返回q表 MergeSortL(mid+1,high,r); //返回r表 MergeL(q,r,p); 将表q和r合并成表p end{if} end{MergeSortL}

八皇后问题
使用回溯法找到八个皇后的摆 放位置，使得它们不会互相攻 击。
0/1背包问题
利用回溯法找到最优的物品选 择方案，使得总价值最大且不 超过背包容量。
八皇后问题
八皇后问题是一个经典的回溯法应用，要求在8x8的棋盘上放置8个皇后，使 得它们不会互相攻击。
解决方法是使用递归的回溯法，在每一行放置一个皇后，然后递归地处理下 一行。
回溯法和动态规划的比较
回溯法和动态规划都可以用来解决搜索问题，但它们在求解方式和效率上有 一些区别。
回溯法通过试错的方式搜索解空间，可能需要遍历大量的解空间；而动态规 划则通过状态的存储和复用来避免重复计算，提高效率。回溯法的优化1
剪枝
通过判断条件和提前终止搜索，剪掉不必要的分支。
2
双向搜索
从目标状态和初始状态同时进行搜索，减少搜索空间。
回溯法的代码实现
回溯法的实现可以使用伪代码或具体的编程语言。 以下是伪代码示例：
procedure backtrack(c) is if reject(P, c) then return if accept(P, c) then output(P, c) s <- first(P, c) while s != NULL do backtrack(s) s <- next(P, s)
欢迎通过示例代码进一步学习回溯法的实现细节。
总结
回溯法是一种强大的搜索算法，广泛应用于各种问题领域。 了解回溯法的应用场景和技巧，可以帮助我们解决更加复杂的问题。 在使用回溯法时，需要注意剪枝和双向搜索等优化方法，以提高求解效率。
《算法8回溯法》PPT课 件
探索回溯法的魅力，从算法基础到应用实例，让我们一起深入了解回溯法的 奥秘。

• •
8.2.1 栈式存储分配与活动记录 使用栈式存储分配法意味着程序运 行时，每当进入一个过程(或函数)就有一 个相应的活动记录累筑于栈顶，此记录 含有连接数据、形式单元、局部变量、 局部数组的内情向量和临时工作单元等； 在进入过程和执行过程的可执行语句之 前，再把局部数组所需空间累筑于栈顶， 从而形成过程工作时的完整数据区。
TOP
临时工作单元 内情向量 简单变量 形式单元 2 1 参数个数 返回地址 老SP
SP
0
第八章 运行时存储空间组织
4 3 TOP＋3 2 1 TOP SP 0
参数个数n
…
T2 T1 P的活动记录 现行SP值
第八章 运行时存储空间组织
8.2 简单的栈式存储分配
• 我们首先考虑一种简单程序语言的 实现，这种语言没有分程序结构，过程 定义不允许嵌套，但允许过程的递归调 用，允许过程含有可变数组。例如，C语 言除不允许含有可变数组外，就是这样 一种语言。C语言的程序结构如下：
第八章 运行时存储空间组织
• • • • • • • • •
第八章 运行时存储空间组织
•
满足这些条件的语言有FORTRAN，还有 BASIC等语言。在这些语言中，编译程序可以完 全确定程序中数据项所在的地址(通常为相对于 各数据区起始地址的位移量)。由于过程调用不 允许递归，因此数据项的存储地址就与过程相联 系。过程调用所使用的局部数据区可以直接安排 在过程的目标代码之后，并把各数据项的存储地 址填入相关的目标代码中，以便在过程运行时访 问这个局部数据区。在此，不存在对存储区的再 利用问题；目标程序执行时不必进行运行时的存 储空间管理，过程的进入和退出变得极为简单。
第八章 运行时存储空间组织

proc nQueens(n) integer k,n,X[1..n]; X[1]:=0; k:=1; //k是当前行,X[k]是当前列 while k>0 do X[k]:=X[k]+1;//转到下一列 while X[k]≤n and Place(k)=false do X[k]:=X[k]+1; end{while} if X[k]≤ n then if k=n then Print(X); else k:=k+1; X[k]:=0; //转到下一行 end{if} else k:=k-1;//回溯 end{if} end{while} end{nQueens}
旅行商问题的回溯算法
proc BackTSP(n,W) //W是G的邻接矩阵, cl是当前 //路径的长度，fl是当前所知道的最短周游长度. in teger k,n,X[1..n]; real W[1..n,1..n],cl,fl; for i to n do X[i]:=0; end{for} k:=2; cl:=0; fl:=+∞; while k>1 do X[k]:=X[k]+1 mod n;//给X[k]预分配一个值 for j from 1 to n do if NextValue(k)=true then cl:=cl+W(X[k-1],X[k]); break; end{if} X[k]:= X[k]+1 mod n; //重新给X[k]分配值 end{for} if fl ≤ cl or k=n and fl < cl+W[X[k],1] then cl:=cl-W(X[k-1],X[k]); k:=k-1; //回溯 elif k=n and fl ≥ cl+W(X[k],1) then fl:=cl+W(X[k],1); cl:=cl-W(X[k-1],X[k]);

i
i
m[i][j]
s[i][j]
回溯过程
void Traceback(int i, int j, int * * s) { if (i= = j) return; Traceback(i, s[i][j], s); Traceback(s[i][j]+1, j, s); cout << “Multiply A” << i << “,” << s[i][j]; cout << “and A” <<(s[i][j] +1) << “,” << j << endl; } • 以s[i][j]为元素的2维数 组却给出了加括号的全部 的信息。因为s[i][j]=k说 明，计算连乘积A[i..j]的 最佳方式应该在矩阵Ak和 Ak+1之间断开，即最优加 括号方式为 (A[i..k])(A[k+1..j])。 可以从 s[1][n]开始，逐步 深入找出分点的位置，进 而得到所有括号。
V1 9 9 7 1 2 3 3 7 3 7 4
11
V2 2 2 4
V3 6 2 9
11
V4 9 4 13 3 5
10 14
V5
6 5
7
4 2 5
s
1
t
12 16
11
8
2 5
8
10
6
16
11
矩阵连乘积问题
• 给定n个数字矩阵A1，A2，…，An，其中Ai与Ai+1是可乘的， 设Ai是pi-1×pi矩阵, i=1,2,…,n。 • 求矩阵连乘A1A2⋅⋅⋅An的加括号方法，使得所用的数乘次数最少 • 三个矩阵连乘：(A1A2)A3和A1(A2A3) ，乘法次数分别为 p0p1p2+p0p2p3和p0p1p3+p1p2p3 • 例子：p0=10, p1=100, p2=5, p3=50, 两种方法：7500 和 75000 • 最优子结构性质：(A1…Ak)(Ak+1…An) m(1,n)=m(1,k) + m(k+1,n)+p0pkpn • 目标值递推关系式