【读书笔记】算法漫步 第13章
2023-07-26 21:59 作者:圣斗士-DS-ALGO | 我要投稿
问题12 最大流量
在高速公路网中有车流,在互联网上有信息流,在自来水管网中有水流,在公用电网中有电流。。。网络大都和某种流联系在一起,网络的作用就是要保障那些流的通畅。对于网络中流量的研究是一个具有普遍意义的主题。
研究网络中的流问题可有多个不同的视角和目标追求。
本章作者介绍的是两个节点之间可能经过的最大流量。
为了让读者能够理解,首先介绍了一个只有三个节点的有向带权网络(图)。
然后介绍一个有四个节点的有向带权图。
通过两个实例的介绍,读者可以慢慢体会到这个问题的挑战之处了。
然后,本章详细介绍了经典Ford-Fulkerson算法(1956年发明),从方法的动机,基本的思路,算法执行举例,给出了一种算法描述后,简略讨论了算法为什么会结束、为什么可以求出最优解,运行效率,算法的适用性等问题。
【作者感受】
最大流问题就是在容量网络中,寻找流量最大的可行流。它是一种组合最优化问题,一个特殊的线性规划问题,所以它的应用场景是很多的,涉及很多热门领域,如运筹学。所以,求解最大流问题的算法有很多的。
我个人认为,最大流问题是算法学习的一个分水岭,因为要学习并基本理解,并能够真的能够应用的好,是需要相当高的水平,很多计算机专业的学生都不明白,甚至都没学过(因为很多算法课程都不讲)
当然,在一些经典的应用领域中,有工具提供最大流的方法,或者有高手已经实现好了最大流的程序,用就是了。