[發(fā)明專利]一種基于相互關系表求解復雜網絡最大流的方法

在審

• 申請?zhí)枺?/td>: 201410368344.8
• 申請日: 2014-07-30
• 公開（公告）號: CN104217101A
• 公開（公告）日: 2014-12-17
• 發(fā)明（設計）人: 侯開虎;朱栩穎;楊維平;陳婷;張飛;曹麗銀
• 申請（專利權）人: 昆明理工大學
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發(fā)明涉及一種基于相互關系表求解復雜網絡最大流的方法，屬于工業(yè)工程領域。

背景技術

許多系統(tǒng)包含了流量問題。例如，公路系統(tǒng)中有車輛流，控制系統(tǒng)中有信息流，供水系統(tǒng)中有水流，金融系統(tǒng)中有現(xiàn)金流等。最大流問題就是指在一定的條件下，要求流過網絡的物流、能量流、信息流等流量為最大的問題。

最大流問題已有40多年的研究歷史，這段時期內，人們建立了最大流問題較為完善的理論，同時開發(fā)了大量的算法。如Ford和Fulkson增截軌算法、Dinic阻塞流算法、Goldberg推進和重標號算法以及Goldberg和Rao的二分長度阻塞流算法等，這些經典算法及相關技術對網絡最大流問題的研究起到了非常重要的推動作用。

最近十幾年來，隨著計算機科學技術在全世界的快速發(fā)展，網絡最大流問題得到了足夠的重視和深入的研究，并極大地推動了計算機解決最大流問題的研究進展。然而，研究工作仍遠遠沒有結束：首先，沒有利用相互關系表這一數(shù)據(jù)存儲結構針對求解最大流問題進行研究；其次，沒有在雙向流問題上設計方向性規(guī)定；最后，在設計程序化的統(tǒng)一查找模式上沒有采取順序查找與迭代的方式進行最大流問題的求解。

依據(jù)以上存在的不足，本文擬采用基于相互關系表的存儲模型對網絡最大流問題進行研究設計。通過找到統(tǒng)一的運算標準，進行程序化的查找運算，顯化其內在的關系。提供對巨型復雜情況下的網絡問題的求解的方法。

發(fā)明內容

本發(fā)明提供了一種基于相互關系表求解復雜網絡最大流的方法，以用于解決在實現(xiàn)在大規(guī)模復雜的網絡圖中，擁有很多節(jié)點數(shù)，并且每條路徑上帶有不定的方向時，通過程序化的查找方式針對網絡最大流問題進行求解。

本發(fā)明的技術方案是：一種基于相互關系表求解復雜網絡最大流的方法，首先通過網絡圖轉換出唯一對應確定關系的相互關系表；然后根據(jù)相互關系表依次尋求相應的一條通路；接著將得到的相應通路上的每一個流量減去相應通路上的基流量，得到新的相互關系表；再根據(jù)得到的新相互關系表，重復尋求相應的通路，直到不能尋找到通路為止；最后把所有通路的基流量進行累加操作，則得到對應網絡圖的最大流量。

所述方法的具體步驟如下：

Step1、通過網絡圖轉換出唯一對應確定關系的相互關系表；其中，相互關系表為根據(jù)網絡圖中n個可達點構建n-1行、n-1列的二維對應關系表，二維對應關系表以可達點起始點處開始表格數(shù)從1個依次在步長為1的情況下遞增至n-1個，二維對應關系表對應表格中的數(shù)值為任意兩個可達點沿著對應行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出發(fā)，選取V_m對應行X_i中任意一個正的；或者從所在的Y_j列中選取任意一個負的，再接著從所在的X_i行中選取任意一個正的；