汇编语言13章贪心算法-2016.pptx

第13章 贪心法 ;引论;13.1优化问题;例:货箱装船问题;很多优化问题是NP－难度问题，迄今找不到它们的多项式算法。所以计算上可行的方法就是求其近似解。 贪心法是求近似解的主要途径。 贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。 贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。 在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。;贪心算法的基本要素;;;13.2贪心法的步骤;贪心法的主要特点是：;例：找零钱问题;例：活动安排问题;贪心算法描述;;例：机器调度 ;;例13.5(续);贪心算法并不总能求得问题的整体最优解。但对于活动安排问题、机器调度问题，上述贪心算法却总能求得整体最优解. 以机器调度问题为例进行证明 证明: 任何可行解使用的机器数≥最大重迭任务数; 所以优化调度使用的机器数≥最大重迭任务数. 贪心解使用的机器数不超过最大重迭任务数：任何时候当算法使用一台新机器时, 当前这些机器上的任务一定是彼此重叠的.;例：最短路算法;13.3贪心算法的应用;13.3.1 Container loading;定理13.1;13.2.2 0/1背包问题;13.2.2 0/1背包问题;0/1背包问题;(续);;(续);(续);例13.9 k-优化算法;例13.9(续1）;例13.9（续2）;例13.9结论;6 0 0种随机测试的统计结果;13.3.1 哈夫曼编码问题;前缀码;构造哈夫曼编码;算法说明;图论（Graph）相关的应用问题;邻接矩阵(adjacency matrix);邻接表(adjacency list);13.3.2 拓扑排序;拓扑排序定义：;13.3.2拓扑排序;使用栈的伪代码;引理13.1;程序13.2拓扑排序;程序13.2拓扑排序（续1）;程序13.2拓扑排序（续2）;算法13.2的时间复杂度;13.3.3 单源最短路径;Dijkstra’s 最短路算法;1.维护一个集合S，该集合中源节点到其他节点的最短路已知，初始时该集合为空 2.从V-S集合中找一节点v，满足源节点到该节点距离最小 3.更新v的邻节点的到源节点的距离值 ;Dijkstra’s 算法;;;;;;;;;;;;;Dijkstra’s 算法分析;;;无权图（Unweighted graphs）;广度优先算法例题;;源节点到其它所有节点的最短路;若图G=(V,E)包含负权回路，则最短路径可能不存在。 例 Bellman-Ford 算法：找出源节点到其它任意节点的最短路，或确定图中包含负值环路;;;;;;;;;;;单源最短路径 非负权重 Dijkstra 算法复杂度：O(E+VlgV) 一般情况下： Bellman-Ford算法复杂度O(VE) 多源最短路径 非负权值， Dijkstra算法复杂度O(VE+V2lgV) 一般情况（权值可能为负） Bellman-Ford算法为O(V2E)或O(V4) ;13.3.6最小生成树;Kruskal’s算法;图13.12构造最小生成树;图13.12构造最小生成树（续1）;图13.12构造最小生成树（续2）;图13.13 Kruskal’s算法的伪代码;算法正确性证明;算法实现－数据结构;Prim’s算法;;Prim’s 算法;图13.5;图13.15 Prim’s 算法举例;Prim’s算法举例（续）;Prim’s 算法复杂度分析;复杂度分析 ;13.3.7偶图覆盖问题（二分覆盖）;例13.10;图13.6 例13.10所使用的图;集合覆盖问题;例13.11;偶图覆盖问题的贪心解;图13.7贪心启发式算法的伪代码;实现问题;图13.8 图13.7的细化;例13.13;使用二维数组存储New的值;使用最大堆;补充：连续背包问题（习题17）;补充：连续背包问题（续）;补充：连续背包问题（续）;作业;复习要求