[发明专利]一种基于相互关系表求解复杂网络最大流的方法

说明书

技术领域

本发明涉及一种基于相互关系表求解复杂网络最大流的方法，属于工业工程领域。

背景技术

许多系统包含了流量问题。例如，公路系统中有车辆流，控制系统中有信息流，供水系统中有水流，金融系统中有现金流等。最大流问题就是指在一定的条件下，要求流过网络的物流、能量流、信息流等流量为最大的问题。

最大流问题已有40多年的研究历史，这段时期内，人们建立了最大流问题较为完善的理论，同时开发了大量的算法。如Ford和Fulkson增截轨算法、Dinic阻塞流算法、Goldberg推进和重标号算法以及Goldberg和Rao的二分长度阻塞流算法等，这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用。

最近十几年来，随着计算机科学技术在全世界的快速发展，网络最大流问题得到了足够的重视和深入的研究，并极大地推动了计算机解决最大流问题的研究进展。然而，研究工作仍远远没有结束：首先，没有利用相互关系表这一数据存储结构针对求解最大流问题进行研究；其次，没有在双向流问题上设计方向性规定；最后，在设计程序化的统一查找模式上没有采取顺序查找与迭代的方式进行最大流问题的求解。

依据以上存在的不足，本文拟采用基于相互关系表的存储模型对网络最大流问题进行研究设计。通过找到统一的运算标准，进行程序化的查找运算，显化其内在的关系。提供对巨型复杂情况下的网络问题的求解的方法。

发明内容

本发明提供了一种基于相互关系表求解复杂网络最大流的方法，以用于解决在实现在大规模复杂的网络图中，拥有很多节点数，并且每条路径上带有不定的方向时，通过程序化的查找方式针对网络最大流问题进行求解。

本发明的技术方案是：一种基于相互关系表求解复杂网络最大流的方法，首先通过网络图转换出唯一对应确定关系的相互关系表；然后根据相互关系表依次寻求相应的一条通路；接着将得到的相应通路上的每一个流量减去相应通路上的基流量，得到新的相互关系表；再根据得到的新相互关系表，重复寻求相应的通路，直到不能寻找到通路为止；最后把所有通路的基流量进行累加操作，则得到对应网络图的最大流量。

所述方法的具体步骤如下：

Step1、通过网络图转换出唯一对应确定关系的相互关系表；其中，相互关系表为根据网络图中n个可达点构建n-1行、n-1列的二维对应关系表，二维对应关系表以可达点起始点处开始表格数从1个依次在步长为1的情况下递增至n-1个，二维对应关系表对应表格中的数值为任意两个可达点沿着对应行X_i（i=0,…n-2)以及对应列Y_j(j=1,…n-1)方向的交点处所表示的网络图中的流量值                                               ；可达点V_l（l=0,…n-2）对应的行为X_i（i=0,…n-2)，Y_j(j=1,…n-1)对应的可达点为V_m（m=1,…n-1）；

Step2、从起始点V₀开始，在它所在的X₀行中找到任意一个；

Step3、从所在的Y_j列对应的可达点V_m出发，选取V_m对应行X_i中任意一个正的；或者从所在的Y_j列中选取任意一个负的，再接着从所在的X_i行中选取任意一个正的；