通信网络理论基础 06-树与流-2007-BIG.pptxVIP

通信网络理论基础 王晟 博士 教授 博导 Part 06: 树与流 2014年春季 通信网络理论基础 2 / 50 树与流 1 最小生成树算法 最小生成树的各种解法突出地显示了贪婪算法的力量。 3 / 50 最小生成树算法 请着重体会：最优条件与算法的关系. 采用类似思路 综合了两个算法的思路 2014年春季 通信网络理论基础 4 / 50 最小生成树算法 4 最优性条件 1 2 3 5 Kruskal算法 Prim算法 Sollin算法 Steiner树问题 2014年春季 通信网络理论基础 路径最优条件 5 / 50 2014年春季 通信网络理论基础 树上边与割集 6 / 50 S2 S1 2014年春季 通信网络理论基础 割最优条件 7 / 50 S2 S1 2014年春季 通信网络理论基础 8 / 50 最小生成树算法 4 最优性条件 1 2 3 5 Kruskal算法 Prim算法 Sollin算法 Steiner树问题 2014年春季 通信网络理论基础 从最优条件到算法 9 / 50 2014年春季 通信网络理论基础 10 / 50 Kruskal算法思想 2014年春季 通信网络理论基础 路径最优条件在哪里？ 11 / 50 2014年春季 通信网络理论基础 一个例子 12 / 50 10 15 20 35 2014年春季 通信网络理论基础 Kruskal算法实现 13 / 50 2014年春季 通信网络理论基础 14 / 50 最小生成树算法 4 最优性条件 1 2 3 5 Kruskal算法 Prim算法 Sollin算法 Steiner树问题 2014年春季 通信网络理论基础 Prim算法 15 / 50 Kruskal算法 Prim算法 2014年春季 通信网络理论基础 Prim算法伪码 16 / 50 DijkstraAlg (G(V, E), s) PrimAlg (G(V, E), s) 2014年春季 通信网络理论基础 17 / 50 最小生成树算法 4 最优性条件 1 2 3 5 Kruskal算法 Prim算法 Sollin算法 Steiner树问题 2014年春季 通信网络理论基础 Sollin算法 18 / 50 2014年春季 通信网络理论基础 Sollin算法伪码 19 / 50 2014年春季 通信网络理论基础 一个例子 20 / 50 2014年春季 通信网络理论基础 21 / 50 最小生成树算法 4 最优性条件 1 2 3 5 Kruskal算法 Prim算法 Sollin算法 Steiner树问题 2014年春季 通信网络理论基础 Steiner树问题 22 / 50 2014年春季 通信网络理论基础 SPH算法 23 / 50 2014年春季 通信网络理论基础 一个例子 24 / 50 2014年春季 通信网络理论基础 基于最小生成树的求解思路 25 / 50 2014年春季 通信网络理论基础 26 / 50 应用：负载平衡的路由 ae, 1 ce, 1 be, 5 边上数值代表带宽 2014年春季 通信网络理论基础 27 / 50 最小生成树算法小结 2014年春季 通信网络理论基础 28 / 50 树与流 关于流的算法都比较困难，属于高级论题。这里仅介绍其中最容易理解的部分。 2014年春季 通信网络理论基础 29 / 50 最大流算法 4 最大流问题 1 2 3 5 剩余网络 Ford-Fulkerson算法 两种增广路径算法 Preflow-Push算法 2014年春季 通信网络理论基础 最大流问题 30 / 50 2014年春季 通信网络理论基础 例子 31 / 50 2014年春季 通信网络理论基础 32 / 50 最大流算法 4 最大流问题 1 2 3 5 剩余网络 Ford-Fulkerson算法 两种增广路径算法 Preflow-Push算法 2014年春季 通信网络理论基础 直觉 33 / 50 20 0 我们找到s到t的路径p，看它能运送 多少流到t；然后一直这样找下去， 直到没有可以运送流的路径为止。 0 0 0 0 20 20 10 10 10 允许“反向推送”；目的是可以“修正”以前的步骤中寻得的路径。 2014年春季 通信网络理论基础 剩余网络 34 / 50 rij = uij – xij rji = xij rij: (i,j)的剩余容量 20 0 0 0 0 0 20 20 10 10 10 允许“反向推送”；目的是可以“修正”以前的步骤中寻得的路径。 2014年春季 通信网络理论基础 35 / 50 最大流算法 4 最大流问题 1 2 3 5 剩余网络 Ford-Fulkerson算法 两种增广路径算法 Prefl