《贪婪算法》PPT课件

2020/5/21,1,第三部分算法设计方法,2020/5/21,2,相关章节,Chapter13贪婪算法Chapter14分而治之算法Chapter15动态规划Chapter16回溯Chapter17分枝定界,2020/5/21,3,贪婪算法的特点,通过分阶段地挑选最优解，较快地得到整体的较优解示例：Huffman最优编码，Dijkstra最短路径特点：既可能得到次优解，也可能得到最优解，依赖于具体问题的特点和贪心策略的选取多步判断最优子结构性质贪心选择性质,2020/5/21,4,分而治之算法的特点,通过把问题化为较小的问题来解决原问题，从而简化或减少了原问题的复杂度示例：折半查找、快速排序、归并排序特点：自顶向下、问题化解子结构不重复分、治、合,2020/5/21,5,动态规划算法的特点,将问题分成子问题来做，从某一集合中选出子集，进行逐项的测试比较逐步达到整个解，通过逐步逼近最优解而最终得到满足条件的解自底向上，利用中间结果，迅速构造问题的解空间树，以空间换时间示例：Floyd（多源点最短路径）算法特点：能够得到最优解多步判断最优子结构性质,2020/5/21,6,回溯算法的特点,也是从某一集合中选出子集，进行逐项的测试比较逐步达到整个解，通过逐步逼近最优解而最终得到满足条件的解在搜索解空间树时，能够跳过无解分枝！示例：迷宫问题、八皇后问题特点：能够得到最优解最优化问题的通法,2020/5/21,7,分枝定界算法的特点,在系统搜索问题的解空间树时，加入上下界的条件检查以达到有效剪枝的目的特点：能够得到最优解多步判断多米诺性质,2020/5/21,8,Chapter13贪婪算法,中国地质大学信息工程学院,2020/5/21,9,内容提要,13.1示例问题提出13.2贪婪算法的思想13.3贪婪算法的应用货箱装船拓扑排序单源最短路径最小耗费生成树,2020/5/21,10,贪婪算法是指：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪婪算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题，他能产生整体最优解或者是整体最优解的近似解。贪婪算法的基本思路如下：1.建立数学模型来描述问题。2.把求解的问题分成若干个子问题。3.对每一子问题求解，得到子问题的局部最优解。4.把子问题的解局部最优解合成原来解问题的一个解。,2020/5/21,11,算法的基本思路,从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。存在问题：1.不能保证求得的最后解是最佳的；2.不能用来求最大或最小解问题；3.只能求满足某些约束条件的可行解的范围。,2020/5/21,12,最优化问题的几个概念,每个最优化问题包含一组限制条件和一个优化函数可行解：符合限制条件的问题求解方案最优解：使优化函数取得最佳解的可行解例如：Huffman树，从可用的二叉树中选取权重最小的两棵子树，进行合并,2020/5/21,13,例13-1渴婴问题,2020/5/21,14,求解：设各种饮料的满意度已知。令Xi为婴儿将要引用的第i种饮料的量，需要解决的问题是：找到一组实数Xi（14-2-5：101-4-5：6,2020/5/21,28,总结,贪婪算法并不总能保证得到最优解启发式算法：算法并不保证得到最优解，但是通常所得结果与最优解相差无几或很接近。例如：机器调度算法启发式算法具有直觉倾向近似算法：具有限定功能的启发式算法,2020/5/21,29,3、应用1：货箱装船,2020/5/21,30,假设n=8,c=400w1,.w8=100,200,50,90,150,50,20,80利用贪婪算法时，所考察货箱的顺序为7,3,6,8,4,1,5,2。货箱7,3,6,8,4,1的总重量为390个单位且已被装载，剩下的装载能力为10个单位，小于剩下的任何一个货箱。在这种贪婪解决算法中得到x1,.,x8=1,0,1,1,0,1,1,1且,可以证明：利用贪婪算法能产生最佳装载,2020/5/21,31,货箱装载的C+算法实现,voidIndirectSort(intw,intt,intn)/假设w已经按照重量升序排列for(inti=1;i1-3-4-5-6序列2：2-5-1-3-4-6,2020/5/21,42,拓扑排序的特点,拓扑排序输出的序列可能有多种!利用拓扑排序，可以判断一个有向图是否为有向无环图算法失败：表示有向图中有环路,2020/5/21,43,拓扑排序用贪婪算法实现,设n是有向图中的顶点数设V是一个空序列While(true)设w不存在入边（v,w）,其中顶点v不在V中如果没有这样的w，break。把w添加到V的尾部If(V中的顶点个数少于n)算法失败elseV是一个拓扑序列,2020/5/21,44,拓扑排序的实现,（1）数据结构的选择实现方法：将序列V用一维数组v来描述，用一个栈来保存加入V的候选顶点；另有一个一维数组InDegree，InDegreej表示与顶点j相连的节点i的数目，其中顶点i不是V中的成员，它们之间的有向图的边表示为（i，j）。NetWork:修改有向图的基类函数,2020/5/21,45,boolNetwork:Topological(intv)intn=Vertices();int*InDegree=newintn+1;InitializePos();for(inti=1;i=n;i+)InDegreei=0;for(i=1;i=n;i+)intu=Begin(i);while(u)InDegreeu+;u=NextVertex(i);,邻接矩阵：(n2)邻接链表：(n+e),2020/5/21,46,LinkedStackS;for(i=1;i=n;i+)if(!InDegreei)S.Add(i);i=0;while(!S.IsEmpty()intw;S.Delete(w);vi+=w;intu=