技术文章 > 最大流量算法

最大流量算法

2018-01-18 04:22

文档管理软件,文档管理系统,知识管理系统,档案管理系统的技术资料:
最大流量算法也可以被用于网络中某两个相关点的相互影响的数值计算。如开源/自由软件开发阵营的名誉网adovogato 就非常有趣,该网站通过程序员相互评分和一个改进的算法来计算某人在自由软件开发中的知名度高低,不少牛人都被评为master(大师级)。等有时间我去会会,初步目标是游侠级。
算法的目的:求解出一个传输网络中的饱和传输量。
算法对于新手比较复杂,实际上简化为口头表述就容易记忆和活学活用了。其数学表达方式可以参考 Ford 和 Fulkerson算法或 labeling algorithm 标记算法。《离散数学结构》(影印版)8.4节--我有,不借,呵呵。
假设南方有一城A运物资到北方一城B,可以使用全部铁路运输网络。
先随便选一条从A能连接到达B的路径开始,通过观察很容易知道该路径的最大运输量。
再随便选择第二条路径,第二条路径有部分路段可能和第一条路径重复。对于原来运量已经饱和的路段,无法增加运量。如果该路段重复且运输方向恰好相反,可以分析是否可以减少其运量,如果有前方交叉口至少一条未饱和路段可以分担负荷且第二条路径的运量尚未饱和,那就可以调度相应的运量,因为这样做不会减少总的最大运输量,通过重分配利用了最多的未饱和路段。这样通过第二条路径我们可以增大或者不影响总运量。
反复如此,直到最后一条路径被使用即可得到总的最大运量和各个路段应该分配的运量。
以上文字论证仅参考用,可能不严密。