数据结构与算法 贪婪法

第8章贪婪法★贪婪法的设计思想★贪婪法解背包问题★MST（最小生成树）问题Prim（普里姆）算法Kruskal（克鲁斯卡尔）算法★单源（单起点）最短路径问题Dijkstra（狄克斯特拉）算法★本章习题西华大学数学与计算机学院黄襄念贪婪法设计思想★贪婪法（Greedyalgorithms）贪婪法常用来解决最优化问题。犹如登山一样，一步一步向前推进。从某个初始点出发，根据当前局部的而不是全局的最优决策，以满足约束方程为条件，使目标函数值增加最快或最慢为规则，决定本步的局部最优解。如最速上山法各步的方向选择——梯度。计算机学家把贪婪法作为一种通用设计技术，通过一系列步骤来构造问题的解，每一步对当前获得的局部最优解进行扩展，直到全局最优解为止。每一步选择满足（与动态规划法不同）：——是可行解：满足约束条件——局部最优：当前步骤下，所有选择中的局部最佳选择（贪婪）——不可修改：当前局部解一旦得到，后续步骤无法改变它贪婪法：全局最优解是由一系列步骤的局部最优解构成。优点：比动态规划法的时间和空间效率高，算法设计较简单。对某些问题，贪婪法不能获得全局最优解。算法设计时，需要考虑问题是否适合用贪婪法解，即贪婪法是否能够得到全局最优解！西华大学数学与计算机学院黄襄念简例：找零钱【简例】找零钱已知：有4种面额硬币：25分、10分、5分、1分要求：用最少数量的硬币支付48分零钱。（48：问题规模）算法步骤1.支付满足约束条件（≤48分）的最大硬币（25分）——贪婪2.检查余额（48–25）=0？YES:算法停止；NO:返回1计算结果：（25，10，10，1，1，1）共用6个硬币算法策略总是作出当前最佳选择——局部最优。每一步选择最大硬币，是为了把余额减到最小——追求“最速”结果讨论针对这4种面额，贪婪法的确能给出全局最优解。现在换3种面额：7分、5分、1分，找零钱11分。贪婪法结果：7,1,1,1,1共5个钱币。最优解：5,5,1共3个钱币。贪婪法不一定能得到全局最优解。西华大学数学与计算机学院黄襄念贪婪法的两个性质（基本要素）贪婪法的两个性质——判断贪婪法是否适用最优子结构当前规模的最优解包含其子问题的最优解。贪婪选择一系列局部最优选择可达到全局最优，每次选择得到一个局部最优解。动态规划法与贪婪法动态规划法：全局最优解与各步所有子问题都有关，而非仅限于最优子问题（未来决策）。自底向上计算（规模↑）贪婪法的视界局限：当前状态的局部最优选择，不能预见未来。自顶向下计算（规模↓）——贪婪法不能得到最优解时，动态规划法可以得到最优解。——贪婪算法设计简单，时空效率比动态规划法高。——比较“数塔”、“多段图”问题的两种算法过程。西华大学数学与计算机学院黄襄念背包问题★背包问题（KnapsackProblem）两类背包连续背包——物品可任意比例切分（贪婪法能求得最优解）01背包——物品不可切分（贪婪法不一定能求得最优解）连续背包的最优化模型（实数xk表示物品k放入背包的比例系数）三种贪婪策略价值最大：满足约束条件下，每次装入价值最大的物品。——不一定能找到最优解（背包承重量消耗太快）重量最小：满足约束条件下，每次装入重量最轻的物品。——不一定能找到最优解（装入总价值增加太慢）单位价值最大：满足约束条件下，每次装入价值/重量最大的物品——能找到最优解11max0(),,,1,...,1nnkkkkkkkfxvxWxwxkn西华大学数学与计算机学院黄襄念背包问题的贪婪算法连续背包的贪婪算法00000[1..([1...]/[1...])[]/[],[].]0(,[1...],[1..0(*[1)([])[]1[][].[1...],,,)]]GreedyKnapsacknwnvnWVfxnWWVinwiWxi//解向量初始=0，空背包//背包的当前承重量//背包中物品总价值//对w,v按价值/重量降序排序//n个物品循环，当前物品为第i个//当前物品未超重//当前物品整个装入背包：xi=1//背包当前承重量减小//当前物品价值记入总价值//当前物品超重：放入一部分，装满背包问：当前物品超重时，为什么不取后面的物品，而是取当前物品的一部分装入背包？西华大学数学与计算机学院黄襄念最小生成树(MST)问题★最小生成树问题（MinimumSpanningTree,MST）应用举例：城市交通道路网、通信线路网的花费最低生成树：包含连通图全部顶点的连通无环子图，或称：支撑树最小生成树：带权连通图权重最小的一棵生成树树的权重：所有边的权重之和最小生成树问题：求带权连通图的最小生成树的问题生成树、最小生成树图例：ADCB1235ADCB123有环连通图w(T1)=6w(T2)=9w(T3)=8T1：最小生成树(MST)ADCB135ADCB125西华大学数学与计算机学院黄襄念普里姆(Prim)算法Prim（普里姆）算法不断扩展子树→逐步生成MST1.初始树：从图中任选一个顶点v0作为初始生成树2.扩展树：把不在树中、与树距离最近的顶点加入树中（贪婪）与树的距离：到树中所有顶点的距离3.算法停止：全部顶点都包含于树中。每次只扩展一个顶点，扩展次数=|V|-1=n-10()*(*{}(){*}{,**})1||1TTTTTTTTPrimMSTGfortodoevurVVetuVVvEiVruEEeEnV在中选与当前树距离最小的边//输入图G=V,E，生成树T=VT,ET//任选顶点v0作为初始生成树//u*移入VT，v*是树中顶点//边移入ET//返回边集西华大学数学与计算机学院黄襄念普里姆(Prim)算法*u*v0v子树TkMST扩展过程示意图西华大学数学与计算机学院黄襄念Prim算法过程图例Prim算法过程例每次扩展树时，需要知道非树中顶点（候选顶点）与树的最小距离——把图的顶点集分为2个子集：树中顶点集、候选顶点集——给顶点附加2个属性：与树邻接的最近顶点名和边长——名为空，边长∞：该候选顶点与树的任何顶点都不相邻BCFAED1344655682(,)A(,),(,)(,),(3,6)(,5)BACDEAFABCFAED1344655682(,),(,3)ABA,4(),(,)(,6,1),()CDEAFBB树中顶点集候选顶点集西华大学数学与计算机学院黄襄念Prim算法过程图例（续）树中顶点集候选顶点集(,),(,3)(,1)ABACB,(),(,6)(4,6)DEABFC(,),(,3)(,1),(,4)ABACBFB(),(,),25FDEFBCFAED1344655682(,),(,3)(,1),(,4)(,2)ABACBFBEF5(),DFF(B,4)和F(C,4)生成图不唯一正确性证明略，时间效率与图的表示和集合V-VT的优先队列有关（略）BCFAED1344655682BCFAED1344655682西华大学数学与计算机学院黄襄念克鲁斯卡尔(Kruskal)算法Kruskal（克鲁斯卡尔）算法（俗称：避环法）算法策略（正确性证明略）——边排序：按权重递增排序——子图扩展：逐条扫描有序边表，不形成回路的边加入当前子图开始时：各顶点为根共n棵单节点树。结束时：一棵MST算法步骤1.边E排序：权重递增排序，带权图G=V,E,W2.初始化边集ET为空（初始子图）3.从E中取下一条边e={u,v}（贪婪），E←E-{e}4.若Find(u)≠Find(v),执行Union(u,v)：ET←ET∪{e}5.若|ET|≤n-1，转3；否则，算法结束Find(u)找u所在树的根。Union(u,v)合并u、v所在的树：e加入ETFind(u)≠Find(v)：u、v所在树的根不同，u、v不属于同一棵树，e加入ET后不会形成回路！思考：最小生成树有多少条边？（n个节点）西华大学数学与计算机学院黄襄念Kruskal算法过程图Kruskal算法过程图BCFAED1344655682树中边集候选边集（权重递增）BC,EF,AB,BF,CF12344AF,DF,AE,CD,DE55668BCBC,EF,AB,BF,CF12344AF,DF,AE,CD,DE55668BCFAED1344655682西华大学数学与计算机学院黄襄念Kruskal算法过程图（续）BC,EFBC,EF,AB,BF,CF12344AF,DF,AE,CD,DE55668树中边集候选边集(非降序)BC,EF,ABBC,EF,AB,BF,CF12344AF,DF,AE,CD,DE55668BC,EF,AB,BFBC,EF,AB,BF,CF12344AF,DF,AE,CD,DE55668BC,EF,AB,BF,DF其他边将构成回路BCFAED1344655682BCFAED1344655682BCFAED1344655682西华大学数学与计算机学院黄襄念离散集合的Find和Union操作离散集合的Find和Union操作集合的代表元：用集合中某个元素代表该集合（如树根，堆顶）。根据具体情况，集合的任一元素都可以作为代表元，有的对代表元有要求如最小元、最大元等。Union(x,y)集合合并，Find(x)查找特定元素所在集合。如集合S={1,2,3,4,5,6}，其子集{1},{2},{3},{4},{5},{6}Union(1,4)={1,4},Union(5,2)={5,2}Union(4,5)={1,4,5,2}Kruskal生成MST算法，需对每一条待加入边{u,v}进行判断——看它是否与当前森林中某一棵树构成简单回路。Find(u)、Find(v)查找边{u,v}的两节点u、v是否属于同一棵树：若是——将它们的边加入森林中必然构成回路。不是——Union(u,v)，它们的边加入森林，即它们所在的两棵树合并为一棵树。西华大学数学与计算机学院黄襄念离散集合的Find和Union操作（续）集合的有根树描述一个集合表示成一棵有根树，每个结点表示一个元素。非根结点都有一个指针指向它的父亲（父指针），根结点的父指针为空。集合的合并例合并下图中元素5和元素6所代表的两个集合，Union(5,6)145236145236把5子树的根与6子树的根用一条有向边相连成为一棵树，即完成两个集合的合并，理解为原无向边{1,3}加入5子树。用有向边是为了从任意节点开始查找所在根节点西华大学数学与计算机学院黄襄念Union操作规则Union操作规则：考虑Find操作，如果树高越大，则Find操作的键比较次数就会增加。上例Union操作没考虑这点，明显的缺点是Union后树高可能会变得很大（想想：为什么？），最坏情况下树变成线性表（链表），Find操作成为线性效率Ω(n)而非对数级。例如：集合{1},{2},{3},{4},{5}的一种合并过程如图，最后得到一条线性链。需避免此种情况出现。12542312314231Union(1,2)Union(1,3)Union(3,4)Union(2,5)Union规则：将较小树附加到较大树的根上。树的大小可用节点数或者树高度量。实现时，每个节点存放一个非负整数节点秩rank(x)：表示以x节点为根的子树高度。Union时，判断两个根节点秩，若rank(x)≥rank(y)，则把x作为y的父亲。西华大学数学与计算机学院黄襄念Uniion、Find与路径压缩技术路径压缩技术：执行Find时结合路径压缩技术，可进一步提升以后Find操作的效率。54231按此顺序执行Union操作1T12T23T34T41T12T23T34T4树高T1T2T3T4执行Find操作，找到某代表元所在树根后，再将这条路径上所有节点的父指针修改为指向树根。虽然这增加了一次Find的时间，但为以后多次Find节省了