可见枚举法需要指数时间——没有实际意义.PPT

* * 普通方法 对顶点 i , j ?V={1, 2, …, n} 之间的一条路径，如果考虑所经过的中间顶点、这些中间顶点的排列，那么这个排列数就是 （n-2）!，可见普通的枚举法不可行。 观察：如果对 i , j ?V 之间的路径——比如中间顶点集合进行分类，有可能找到高效、可行的计算方法。 * * 动态规划方法 考察图 G 中两个顶点，i，j 之间的距离，这个距离必定对应某一条从 i 到 j 的最短路径。 现在分析，这条路径上的中间顶点及其排序，这个也是显然十分复杂的。 换一种思路，分析那些中间顶点所在的集合，显然，这个集合就是V，有点味道了！！ 顶点 n 在不在这个集合中？？回答这个问题，我们可能就找到思路。因为我们可以明确划分两种情况：在 or 不在。 * * 动态规划方法 先说 不在，那么原问题就变成一个子问题 G\{n}，这个子问题的中间顶点所在集合是 V\{n} ； 再来看如果 在， 那么原问题就转化为两个子问题 i 到 n 的距离 + n 到 j 的距离。这两个子问题的中间顶点所在集合都是 V\{n}。 分别从这一个 或者 两个子问题出发，不难将其按照上述方法进一步将它们分成下一层级的子问题，…… 此即动态规划的 递推思路 * * 动态规划方法描述 设 V={1, 2, …, n}， i 和 j 是 V 中两个顶点，定义 是从 i 到 j，并且经过的中间顶点所在集合为 的距离——最短路径的长度。则： d[i, j] 若 k = 0 若 1≤ k ≤ n 显然，当 k = n 时， 就是图 G 中从 i 到 j 的距离。 * * 等价描述 设 V={1, 2, …, n}， i 和 j 是 V 中两个顶点，定义 是从 i 到 j，并且不经过 {k+1, k+2, …, n} 中任何顶点的最短路径的长度。则： 若 1≤ k ≤ n d[i, j] 若 k = 0 = d[k,i,j] * * … i j j i k … j i … … = * * 注意到，计算只经过集合 中顶点，从 i 到 j 的距离，只需要分两种情况讨论：“不经过第 k 个点” 和 “经过第 k 个点”。 “不经过第 k 点” 等价于 “中间顶点集合 = ” “经过第 k 个点” 的距离是：“从 i 到 k 的距离” 和 “从 k 到 j 的距离”，这两条路径的中间顶点集合 = 。 * * 输入: n×n 维矩阵 D0[1···n, 1··· n]，记有向图 G＝({1, 2, ···, n}, E) 中的边 (i, j) 的长度为 D[i, j]。 输出: 矩阵 D，使得 D[i, j] 等于 i 到 j 的距离。 Algorithm of Floyd * * 1. D = D0 2. for k = 1 to n 3. for i = 1 to n 4. for j = 1 to n 5. D[k, i, j] = min{D[k-1, i, j]，D[k-1, i, k] + D[k-1, k, j] } 6. end for 7. end for 8. end for 将输入矩阵 D0 复制到 D 注意 k 出现在两个地方:层次、行列数 * * ASP 流程简图 D0[1···n, 1··· n], D 结束 Y for i = 1…n D[k-1, i，j] = min ( D[k-1, i, j], D[k-1, i，k]，D[k-1, k，j] ) D = D0 for j= 1…n for k = 1…n * * 注意 第 5 步 中，采用的都是矩阵 D，会产生矛盾吗？ 不会！ 原因是所采用的都是 “历史数据”，在状态转移方程中 if i = k ，then d[k][k][j] = d[k-1][k][j]—— 第 k 行的值不变 d[k][i][i] = d[k][j][j] = 0， k = 0, 1, 2, …, n if j = k ，then d[k][i][k] = d[