算法2013s-贪心算法I案例分析.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * 算法设计与分析-贪心算法I 算法设计与分析-贪心算法I 算法设计与分析 * 讲授内容：贪心算法I教　　师：胡学钢、吴共庆 纲要 图等表示 最小扩展树 最优子结构 贪婪选择 Prim’s 贪婪 MST算法 * 算法设计与分析-贪心算法I * 有向图 (digraph) G = (V, E) 是一个有序对的集合，包括 顶点V 的集合 (singular: vertex), 边的集合E ?V ×V . 无向图G = (V, E) 中，边集合E包括无序 的顶点对. 任何情况下 均有 |E| =O(V 2) . 另外，如果 G 是连通的, 那么 |E| ≥ |V| – 1, 这意味着 lg |E| = ?(lgV). 图 (复习) * 算法设计与分析-贪心算法I * 邻接矩阵表示法 一个图G = (V, E)的邻接矩阵, V = {1, 2, …, n}, 为矩阵 A[1 . . n, 1 . . n] A 1 2 3 4 1 2 3 4 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 ?(V 2) 存储空间 ? 稠密表示法. A[i, j] = 1 if (i, j) ? E, 0 if (i, j) ? E. * 算法设计与分析-贪心算法I * 顶点 v ? V 的邻接链表 Adj[v]是和顶点v相邻的顶点的链表。 Adj[1] = {2, 3} Adj[2] = {3} Adj[3] = {} Adj[4] = {3} 对于无向图, |Adj[v]| = degree(v). 对于有向图, |Adj[v]| = out-degree(v). 握手定理：对于无向图∑v∈V = 2|E| ? 邻接表使用的存储空间为 ?(V + E) —是一种 稀疏 表示 (对两种图均适用). 邻接链表表示法 * 算法设计与分析-贪心算法I * 输入: 一个连通的, 无向图 G = (V, E) 其加权函数 w : E → . 为了简化，假设所有边的权各不相同. (CLRS 包括了通用的情况.) 输出: 扩展树 T —连接所有顶点的树 — 其权最小: 最小扩展树 * 算法设计与分析-贪心算法I * MST举例 * 算法设计与分析-贪心算法I * MST T: (G的其他顶点没有画出) 去掉边 (u, v) ? T. 然后,将T划分为两棵子树T1 和T2. 定理：子树 T1 是 G1 = (V1, E1) 的MST， G1是由T1的顶点导出G的子图 。 V1 = T1的顶点, E1 = { (x, y) ∈ E : x, y ∈ V1 }. T2类似. 最优子结构 * 算法设计与分析-贪心算法I * 证明：粘贴拷贝：w(T) = w(u, v) + w(T1) + w(T2). 如果 T1? 是 G1中比T1加权更小的扩展树，那么在G中T?= {(u, v)}?T1 ?? T2 将是一棵比T加权更小的扩展树。 我们得到了重叠子问题了吗? 是的. 很好，那么可以使用动态规划! 是的，但是 MST 表现出更强特征，可以使用更加有效的算法。 证明最优子结构 * 算法设计与分析-贪心算法I * 定理：令 T 为 G = (V, E) 的 MST, 并且令 A ? V。假设 (u, v) ∈ E是连接A和V – A的最小加权边. 那么, (u, v) ∈ T. 贪婪选择特征 局部的最优选择 全局范围内也是最优的. “贪婪”算法的特征 * 算法设计与分析-贪心算法I * 证明. 假设 (u, v) ? T. 粘贴和拷贝. T: (u, v) =连接A 和 V – A的最小加权边 ? A ? V – A 定理的证明 * 算法设计与分析-贪心算法I * T: ? A ? V – A 考虑T中从u到v的唯一的简单路径. 证明. 假设 (u, v) ? T. 粘贴和拷贝. (u, v) =连接A 和 V – A的最小加权边 证明. 假设 (u, v) ? T. 粘贴和拷贝. (u, v) =连接A 和 V – A的最小加权边 定理的证明 * 算法设计与分析-贪心算法I * T: ? A ? V – A 将(u, v) 和这条路径上的第一条边交换，这个边连接A中的一个顶点，同时连接V – A中的一个顶点。 考虑T中从u到v的唯一的简单路径. 证明. 假设 (u, v) ? T. 粘贴和拷贝. (u, v) =连接A 和 V – A的最小加权边 证明. 假设 (u, v) ? T. 粘贴和拷贝.