动态规划 Floyd最短路径算法 高文宇 gwyy@163.com.

Presentation on theme: "动态规划 Floyd最短路径算法 高文宇 gwyy@163.com."— Presentation transcript:

1 动态规划 Floyd最短路径算法 高文宇

2 不同难度的动态规划 状态数为线性的 状态数为平方级的 状态数为立方级的 …

3 活动选择问题 活动选择问题：在一系列给出的活动中选出一个最大兼容活动子集（数目最多）。
例如以下示例中，子集{a3, a9, a11}是一个解，然而最优解是{a1, a4, a8, a11} ，或{a2, a4, a9, a11}，最优解的大小为4。

4 带权活动选择问题 带权的活动选择问题：给定一系列活动Ai，其对应的开始时间为si，结束时间为fi，每个活动还有一个对应的权值vi（价值），问题是需要找出若干个相容的活动，使得总的权值最大。

5 预处理 按活动的结束时间Fi递增的顺序对活动排序，并依次编号。对活动j定义p(j)为使得活动i与j相容的最大标记i<j。简单地说，活动i是最右边的在活动j开始之前结束的活动。如下图所示。

6 考虑一个最优解 假设存在一个最优解O，现在来分析活动n属于或不属于O。
（1）若n∈O，则处于p(n)和n之间的活动不能属于O，此时问题变为在活动{1,2,…,p(n)}中寻找最优解，再加上活动n； （2）若n不属于O，则问题变为在活动{1,2,…,n-1}中寻找最优解。

7 递归解 定义OPT(j)为活动{ 1, 2, …, j }上的最优解，则有： 总的状态数为线性，即OPT(1) ~ OPT(n)

8 状态数为平方级的动态规划 矩阵乘法顺序 最优二叉查找树 背包问题

9 图中所有点对间的最短路径 Floyd算法 Floyd-Warshall 算法考虑最短路径上的中间节点（intermediate），简单路径 p = 〈v1, v2,..., vl〉上的中间节点是除v1 和 vl,以外的任意节点。

10 递归解 设 G 的节点为 V = {1, 2,..., n}，对参数k考虑节点集 {1, 2,..., k} 。对任意一对节点 i, j ∈ V, 考虑从 i 到 j 且中间节点都属于集合 {1, 2,..., k}的所有路径，设 p 是其中的最短路径。记为d(i, j, k)有如下结论。 若 k 不是路径 p的中间节点，则p的所有中间节点属于集合 {1, 2,..., k - 1}。即d(i, j, k)= d(i, j, k-1) 若 k 是 p的中间节点，则如下图,可将p分解为两条子路径，即i~ k~ j。p1 是从 i 到 k 中间节点属于集合 {1, 2,..., k - 1}的最短路径， p2 是从 k 到 j 中间节点属于 {1, 2,..., k - 1}的最短路径。

11 递归解 Floyd-Warshall 算法的递归解。 d(i, j, k)表示从 i 到 j 且中间节点都属于集合 {1, 2,..., k}的所有路径中的最短路径的权值。

12 Floyd算法示例 1

13 Floyd算法示例 2

14 Floyd算法 Floyd /* A[ ] contains the adjacency matrix with A[ i ][ i ] = 0 */ /* D[ ] contains the values of the shortest path */ /* N is the number of vertices */ /* A negative cycle exists iff D[ i ][ i ] < 0 */ void AllPairs( TwoDimArray A, TwoDimArray D, int N ) { int i, j, k; for ( i = 0; i < N; i++ ) /* Initialize D */ for( j = 0; j < N; j++ ) D[ i ][ j ] = A[ i ][ j ]; for( k = 0; k < N; k++ ) /* add one vertex k into the path */ for( i = 0; i < N; i++ ) if( D[ i ][ k ] + D[ k ][ j ] < D[ i ][ j ] ) /* Update shortest path */ D[ i ][ j ] = D[ i ][ k ] + D[ k ][ j ]; }

15 任务 （1）编程实现Floyd最短路径算法。 （2）如何使用Path矩阵构造出最短路径经过的节点。
（4）比较Dijkstra算法和Floyd算法。

16 再见 再见