CAJ | 학술논문

网络最大流问题是经典的组合优化问题,随着网络规模的增加,提高算法效率成为解决问题的关键.为了降低求解大规模网络最大流的计算量,针对单源单汇网络提出基于网络分层的最大流问题求解新方法.分层法首先构造原有向网络对应的层次网络,接着在构造出的层次网络中计算各相邻结点层之间的最大流,以此为基础最终获得整个网络最大流的快速估算.分层法有效降低了计算的复杂性,为在大规模网络中快速获取最大流的求解提供了方便,并给出了一个解决最大流问题的新思路.不同网络上测试的实验结果显示,最大流的近似解误差可控制在1％左右,而平均运行时间仅为经典算法(FordFulkerson算法)运行时间的11％,最好情况下的运行时间仅为经典算法运行时间的2％,是two-phase capacity scaling改进算法运行时间的25％,表明分层方法的有效性.
망락최대류문제시경전적조합우화문제,수착망락규모적증가,제고산법효솔성위해결문제적관건.위료강저구해대규모망락최대류적계산량,침대단원단회망락제출기우망락분층적최대류문제구해신방법.분층법수선구조원유향망락대응적층차망락,접착재구조출적층차망락중계산각상린결점층지간적최대류,이차위기출최종획득정개망락최대류적쾌속고산.분층법유효강저료계산적복잡성,위재대규모망락중쾌속획취최대류적구해제공료방편,병급출료일개해결최대류문제적신사로.불동망락상측시적실험결과현시,최대류적근사해오차가공제재1％좌우,이평균운행시간부위경전산법(FordFulkerson산법)운행시간적11％,최호정황하적운행시간부위경전산법운행시간적2％,시two-phase capacity scaling개진산법운행시간적25％,표명분층방법적유효성.