算法设计与分析(第四章).ppt

* 单源最短路径 例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。 * 单源最短路径 迭代 S u dist[2] dist[3] dist[4] dist[5] 初始 {1} - 10 maxint 30 100 1 {1,2} 2 10 60 30 100 2 {1,2,4} 4 10 50 30 90 3 {1,2,4,3} 3 10 50 30 60 4 {1,2,4,3,5} 5 10 50 30 60 Dijkstra算法的迭代过程： * 初始化 迭代 * 单源最短路径 2、算法的正确性和计算复杂性 (1)贪心选择性质 (2)最优子结构性质 (3)计算复杂性 对于具有n个顶点和e条边的带权有向图，如果用带权邻接矩阵表示这个图，那么Dijkstra算法的主循环体需要 时间。这个循环需要执行n-1次，所以完成循环需要 时间。算法的其余部分所需要时间不超过 。 * 多机调度问题 多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。 这个问题是NP完全问题，到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略有时可以设计出较好的近似算法。 约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。 * 多机调度问题 采用最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。 按此策略，当 时，只要将机器i的[0, ti]时间区间分配给作业i即可，算法只需要O(1)时间。 当 时，首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为O(nlogn)。 * 多机调度问题 例如，设7个独立作业{1,2,3,4,5,6,7}由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为{2,14,4,16,6,5,3}。按算法greedy产生的作业调度如下图所示，所需的加工时间为17。 * 计算计算法设计与分析 * 贪心算法小结 贪心算法每次选择目前最优的解，即通过一系列局部最优来获得整体最优。 贪心算法只有在具有贪心选择性质时才能保证获得整体最优。 具有贪心选择性质应满足：⑴第一个选择是对的；⑵在作出贪心选择后原问题转化为同样的子问题，即最优子结构性质；⑶由归纳法知问题具有贪心选择性质。 * 计算计算法设计与分析 * 贪心算法的特点 贪心算法的关键是确定正确的贪心选择。 贪心选择每一步所作出的选择是某种意义上局部最优的，且与前面的选择相容。 对不具有贪心选择性质的问题，贪心算法虽然不能保证最终结果最优，但在许多情况下能够得到一个很好的近似解。 贪心算法的时间复杂度一般较低。 * 计算计算法设计与分析 * Kruskal算法的例子 1 2 3 4 5 6 1 6 5 5 5 3 6 6 2 4 1 3 1 4 6 2 2 5 3 3 6 4 1 4 5 2 3 5 3 4 5 1 2 6 3 5 6 5 6 6 1 2 3 4 5 6 √ √ u v w √ √ 考察边5，因为1、4点属于同一个集合，被放弃。 × * 计算计算法设计与分析 * Kruskal算法的例子 1 2 3 4 5 6 1 6 5 5 5 3 6 6 2 4 1 3 1 4 6 2 2 5 3 3 6 4 1 4 5 2 3 5 3 4 5 1 2 6 3 5 6 5 6 6 1 2 3 4 5 6 √ √ u v w √ √ × 选择边6，于是1、3、4、6、2、5点属于一个集合。 √ * 计算计算法设计与分析 * Kruskal算法的例子 1 2 3 4 5 6 1 6 5 5 5 3 6 6 2 4 1 3 1 4 6 2 2 5 3 3 6 4 1 4 5 2 3 5 3 4 5 1 2 6 3 5 6 5 6 6 1 2 3 4 5 6 √ √ u v w √ √ × √ 已经选择边了n–1条边，算法结束。结果如图所示。 * 计算计算法设计与分析 * Prim与Kruskal两算法的复杂性 Prim算法为两重循环，外层循环为n次，内层循环为O(n)，其复杂性为O(n2)。 Kruskal算法中，设边数为e，则边排序的时间为O(eloge)，确定边的时间为O(e)，所以整个时间复杂性为O(eloge)。 边数e和顶点数n最多为：e=n(n – 1)/2。 若边多点少，Prim算法较好； 若边少点多，Kruskal算法较好。 * 计算计算法设计与分析 * 贪心算法 Prim算法与Kruskal算法在策略上有个共同的特点，那就是每