贪婪技术9

算法分析与设计AnalysisandDesignofComputerAlgorithms第九章贪婪技术GreedyTechnique©SchoolofComputerScienceandTechnology,SWUST2贪婪技术(GreedyTechnique)教学内容贪婪技术定义及其解题步骤背包问题的贪婪策略(KnapsackProblem)Prim算法Kruskal算法Dijkstra算法哈夫曼树(HuffmanTrees)要求掌握贪婪技术的原理、效率分析方法，以及在常见问题问题中的应用。©SchoolofComputerScienceandTechnology,SWUST3找零钱问题(change-makingproblem)用当地面额为d1d2…dm的最少数量的硬币找出金额为n的零钱。如d1=25,d2=10,d3=5,d4=1，n=48该问题的一个解是：1个25，2个10，3个1，且该解是最优的。这种方法称为贪婪法，建议通过一系列步骤来构造问题的解，每一步对目前构造的部分解做一个扩展，直到获得问题的完全解。必须满足：可行、局部最优、不可取消©SchoolofComputerScienceandTechnology,SWUST4贪婪技术(GreedyTechnique)A(1)A(2)…A(n-1)A(n)某一问题的n个输入B1(1)B1(2)…B1(m)该问题的一种解（可行解）是A的一个子集满足一定的条件约束条件Bk(1)Bk(2)…Bk(m)…目标函数取极值最优解©SchoolofComputerScienceandTechnology,SWUST5背包问题(KnapsackProblem)问题描述已知有n种物品和一个可容纳W重量的背包，每种物品I的重量为wi，假定将物品I的某一部分xi放入背包就会得到pixi的效益(0≤xi≤1,pi0)，采用怎样的装包方法才会使装入背包物品的总效益为最大呢？问题的形式描述极大化∑pixi约束条件∑wixi≤W0≤xi≤1,pi0,wi0,1≤i≤n1≤i≤n1≤i≤n©SchoolofComputerScienceandTechnology,SWUST6背包问题(KnapsackProblem)方案1：按物品价值降序装包方案2：按物品重量升序装包方案3：按物品价值与重量比值的降序装包©SchoolofComputerScienceandTechnology,SWUST7贪婪策略最优解的证明基本思想设X={x1,x2,...,xn}为贪婪策略得到的解设Y={y1,y2,...,yn}为该问题的最优解很明显，X≠Y，如果成立，则不用证明了。证明过程：依次比较X和Y中的每个元素，如果发现不一样，则用X中的替换Y中相应元素，比较完后得到一个新的解Y’=X此时，如能证明Y’的最优值就是Y的最优值或者比Y还好，则说明X就是最优解。©SchoolofComputerScienceandTechnology,SWUST8算法连通图的一棵生成树是包含图的所有定点的连通无环子图（一棵树）。加权连通图的一棵最小生成树是图的一棵权重最小的生成树。©SchoolofComputerScienceandTechnology,SWUST9算法©SchoolofComputerScienceandTechnology,SWUST10算法为了知道连接树中顶点的最短边的信息，可以把不在树中的顶点分为两个集合，“边缘”集合和“不可见”集合。边缘集合只包括那些不在树中，但至少和树中一个顶点相邻的顶点。图中所有其他顶点都是不可见顶点。确定了一个加入树中的顶点u后，需要两步操作把u*从集合V-VT移动到树的顶点集合中对于集合V-VT中每个剩下的顶点u，如果它用一条比u的当前距离标记更短的边和u*相连，分别把它的标记更新为u*以及u*与u之间边的权重。©SchoolofComputerScienceandTechnology,SWUST11算法实例©SchoolofComputerScienceandTechnology,SWUST12算法是否能产生一个最优解用归纳法和反证法来证明：假设Ti-1是某些最小生成树T的一部分，我们需要证明，通过Prim算法从Ti-1成生的Ti也是一棵最小生成树的一部分。©SchoolofComputerScienceandTechnology,SWUST13算法Kruskal算法把一个加权连通图G=V,E的最小生成树看作是一个具有|V|-1条边的无环子图，并且边的权重和是最小的。该算法通过对子图的一系列扩展来构造一个最小生成树，这些子图总是无环的，但在算法的中间阶段，并不一定是连通的。该算法首先将图中边按照权重的非递减顺序进行排序，然后从一个空子图开始，试图安顺序把边加到当前的子图中。©SchoolofComputerScienceandTechnology,SWUST14算法算法Kruskal(G)//构造最小生成树的Kruskal算法//输入：加权连通图//输出：ET按照边的权重w(ei)的非递减顺序对集合E排序ETφ;ecounter0;k0;Whileecounter|V|-1kk+1ifETU{eik}无回路ETETU{eik};ecounterecounter+1;ReturnET©SchoolofComputerScienceandTechnology,SWUST15算法实例©SchoolofComputerScienceandTechnology,SWUST16算法链接两个顶点的新边时的可能情况Union-Find（并查）算法在某个城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：我朋友的朋友是我的朋友；我敌人的敌人是我的朋友；已知关于n个人的m条信息（即某2个人是朋友或者敌人），假设所有是朋友的人一定属于同一个团伙，请计算该城市最多有多少团伙？©SchoolofComputerScienceandTechnology,SWUST17（并查）算法英文：DisjointSet，即“不相交集合”将编号分别为1…N的N个对象划分为不相交集合，在每个集合中，选择其中某个元素代表所在集合。常见两种操作：合并两个集合查找某元素属于哪个集合©SchoolofComputerScienceandTechnology,SWUST18（并查）算法用编号最小的元素标记所在集合；定义一个数组set[1..n]，其中set[i]表示元素i所在的集合；©SchoolofComputerScienceandTechnology,SWUST19(i)不相交集合：{1,3,7},{4},{2,5,9,10},{6,8}Union-Find（并查）算法每个集合用一棵“有根树”表示定义数组set[1..n]set[i]=i,则i表示本集合，并是集合对应树的根set[i]=j,ji,则j是i的父节点.©SchoolofComputerScienceandTechnology,SWUST20(i)15247103689©SchoolofComputerScienceandTechnology,SWUST21（并查）算法©SchoolofComputerScienceandTechnology,SWUST22快速求并©SchoolofComputerScienceandTechnology,SWUST23算法(single-sourceshortest-pathsproblem)已知一个n结点的有向图G=(V,E)和边的权函数c(e)，求由G中某指定结点v0到其他各个结点的最短路径。v0v2v1v3v4v5204550101515201035303路径长度(1)v0v210(2)v0v2v325(3)v0v2v3v145(4)v0v445©SchoolofComputerScienceandTechnology,SWUST24产生最短路径的贪心策略逐条构造这些最短路径;假定已构造了i条最短路径，则下面要构造的路径应该是下一条最短的最小长度路径。生成从v0到所有其它结点的最短路径的贪心方法就是按照路径长度的非降次序生成这些路径。©SchoolofComputerScienceandTechnology,SWUST25产生最短路径的贪心策略给每一个顶点附加两个标记：数字d指出目前为止的最短路径长度另一个标记当前构造出来的树中标出顶点的父母在确定了加入树中的顶点v*以后，还要做两个操作：把u*从边缘集合移到树顶点集合对于余下的每一个边缘顶点u，如果通过权重为w(u*,u)的边和u*相连，当du*+w(u*,u)du时，把u的标记分别更新为u*和du*+w(u*,u)。©SchoolofComputerScienceandTechnology,SWUST26©SchoolofComputerScienceandTechnology,SWUST27算法实例数组Θ(|V|2)，邻接表Θ(|E|log|V|)©SchoolofComputerScienceandTechnology,SWUST28哈夫曼树(HuffmanTrees)使用此算法可对字符进行变长编码。算法的贪心策略是每次选择概率最小的两个节点来构造一棵二叉树，依次下去，把所有节点包含进来后，就形成了一棵最优二叉树。思考算法的效率？与动态规划的最优二叉树构造算法比较？哈夫曼树(HuffmanTrees)哈夫曼树(HuffmanTrees)©SchoolofComputerScienceandTechnology,SWUST31带有限期的作业排序问题描述假定只能在一台机器上处理n个作业，每个作业均可在单位时间内完成；又假定每个作业I都有一个截止期限di0(是整数)，当且仅当作业i在它的期限截止之前被完成时，则获得pj0的效益。这个问题的一个可行解是这n个作业的一个子集合J，J中的每个作业都能在各自的截止期限之前完成，可行解的效益值是J中这些作业的效益之和∑p。具有最大效益值的可行解就是最优解。©S