Chapter-5贪心策略.ppt

5 贪心策略Greedy Strategy 引例 假设有4种硬币，面值分别为2角5分、1角、5分和1分。现在要求以最少的硬币个数找给顾客6角3分。 单源最短路径问题 G = (V, E) 是一个有向图，每条边上有一个非负整数表示长度值，其中有一个顶点称为源节点。所谓的单源最短路径问题就是：求解该源节点到所有其它节点的最短路径值。 不失一般性，假设V = {1,2,3,...,n} 并且源节点s = 1。那么该问题可以使用Dijkstra算法来求解，该算法是一种贪心算法，并且能求得最优解。 埃德斯加.狄克斯特拉(Edsgar Dijkstra) 1930-2002 1956年，成功设计并实现了在有障碍物的两个地点之间找出一条最短路径的高效算法，这个算法被命名为“狄克斯特拉算法”，解决了机器人学中的一个十分关键的问题，即运动路径规划问题，至今仍被广泛应用。 1968年3月，Communications ? of ? ACM登出了狄克斯特拉的一封影响深远的信，在信中他根据自己编程的实际经验和大量观察，得出如下结论：一个程序的易读性和易理解性同其中所包含的无条件转移控制的个数成反比关系，也就是说，转向语句的个数愈多，程序就愈难读、难懂。因此他认为“goto语句是有害的”，并从而启发了结构化程序设计的思想。 1972年的图灵奖授予荷兰的计算机科学家埃德斯加.狄克斯特拉。 1983年，ACM为纪念Communications of ACM 创刊25周年，评选出从1958-1982的四分之一个世纪中在该杂志上发表的25篇有里程碑意义的论文，每年一篇，狄克斯特拉一人就有两篇入选，是仅有的这样的两位学者之一 。 在程序设计技术、算法和算法理论、编译器、操作系统等诸多方面，狄克斯特拉都有许多创造，作出了杰出贡献。 开始时，我们将所有的节点划分为两个集合X = {1}, Y = {2,3,4,..,n}。所有已经计算好的节点存放在X中，Y中表示还没有计算好的。Y中的每个节点y有一个对应的量λ[y]，该值是从源节点到y (并且只经由X中的节点) 的最短路径值。 Dijkstra算法 假设V = {1,2,3,...,n} 并且s = 1。 选择一个λ[y] 最小顶点y∈Y，并将其移动到X 中。 若 y 被从Y 移动到X 中，Y 中每个和y 相邻的顶点w 的λ[w]都要更新(表示经由y 到w 的一条更短的路径被发现) 。 证明: (数学归纳法) 1) 显然λ[1] = δ[1] = 0。 假设当前将 y从Y中 移动到X 中，并且在y 之前移动到X 中的任何一个顶点c，都有λ[c] =δ [c]。 下面证明λ[v] = δ[v]。 我们知道：必定存在一条从源节点1 到节点y的真正最短路径，该路径长度值用δ[v]表示 ，并且这条最短路径总可以用以下节点序列表示： λ[y] ≤λ[x]+length[x, y] //算法要求 =δ[x]+length[x, y] //归纳假设 =δ[y] //(A)是最短路径 最小生成树 设G =(V,E)是连通无向带权图，(V,T)是G的一个子图，并且T是一颗树，那么称(V,T)是G的生成树。如果T的权之和是所有生成树中最小的，那么则称之为最小生成树。 网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权c[v][w]表示建立城市v 和城市w 之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。 假定G 是连通的，如果G 是非连通的，那么，可以对G 的每个子图应用求解最小生成树的算法。 Kruskal算法 1. 对G的边E按权重以非降序排列。 2. 初始时输出树T={}；依次取排序表中的每条边，若加入T不形成回路，则加入T；否则将其丢弃； 3. 不断重复步骤2，直到树T包含n-1条边，算法结束。 正确性证明 证明：我们只要证明，使用Kruskal 算法过程中，每次循环所得到的T (从空集增至最小生成树)总是图G 的最小生成树的子集即可。证明使用归纳法＋反证法。 (1) G总是具有一个最小生成树，不妨记为T* (2) 当前要加入的边为e= (x,y) (3) 包含x的那棵子树的所有顶点用X表示，有x ∈X, y∈V ?X (4) 假设在e= (x,y)加入之前得到的T均满足T?T* 令T =T∪{e}，下面我们要证明T 也是图G 的最小生成树的子集。 依据归纳假设，有T?T* 。 i) 如果e∈T*, 显然有T?T* ii) 如果 e ? T*, 我们知道T*中必定包含这样一条边e =(w,z) ,且w∈X