最大流问题以及应用.ppt

最大流问题以及应用 答 辩 人 ：吕永强 指导老师 ：王朝阳 目 录 1.选题背景 2.课题内容 3.体会心得 4.致 谢 选题背景 最大流问题在生活中的方方面面都有广泛的 应用。 交通运输网络中的人流、车流、物流,供水网络中的水流、金融系统中的现金流通信系统中的信息流等等，都属于最大流问题。 课题内容 1.标号法 一.标号过程，通过标号过程找到一条 增广路径； 二.增广过程，沿着增广路径增加网络 流流量的过程 优点 ：会得到一个最小割集，也就找到了网络中的 “瓶颈”。也就找到了提高总流量的 方法 。 缺点：由于对增广路选择的任意性导致该算法的时间复杂度 不仅仅依赖 网络规模还与各边容量有关 。 2.Edmonds-Karp修正算法 “先标号的先扫描”。 对已给标号的顶点进行扫描时，先对所有和邻接的未给标号的顶点给予标号 优点：相对于Ford-Fulkerson算法，其使得流量增加总是沿着一条长度最短的路径从流向的。 缺点：时间复杂度相对于标号法而言减少了但 仍然很大 Dinic算法 Dinic算法是标号法 的改进算法。 Dinic算法则是兼取以上两种方法。在分层时用的宽度优先法，而寻求增广路径时·则采用深度优先策略。 是目前这 三中算法中 最高 效的一个。 1.初始化流量进行BFS得到层次图。 2.若汇点不在层次图内则算法结束。 3.在层次图内进行DFS增广。 4.转 到步骤2直至无法增广。 Dinic算法的优点 通过分层切断了 原来网络中的许多不必要的链接 每次 DFS 结束后 会找到一条路径容量最小的边 ，那这条边之前的点可能引发 新的增广路，若找到 该点则可回溯到该点，从而减少从始点开始的开销。 心得体会 从最大流问题的课题 的研究来看，其实数学可以应用于生活的 方方面面。 对于处理问题的 时间复杂度相当重要的，在处理问题是应该优先考虑。 在处理实际问题时可能是很复杂的 ，如果可以建立一个网络图 利用最大流问题的解法，问题就会简单很多 。 谢谢大家 * * dinic算法基本步骤 *