论文部分内容阅读
网络最大流问题是经典的组合优化问题,随着网络规模的增加,提高算法效率成为解决问题的关键.为了降低求解大规模网络最大流的计算量,本文模拟人类思维逐步求解复杂问题的思想,提出一种基于粒计算求解网络最大流问题的简单方法.本文首先将大规模复杂网络粒化为多个规模较小的子网络,再分别求解各子网络最大流,最后将子网络最大流合成得到原网络最大流.本文方法有效地降低了计算的复杂性,为在大规模复杂网络中快速获取最大流提供了方便,并给出一个解决最大流问题的新思路.不同网络上测试的实验结果显示,最大流的近似解误差可控制在1%左右,而平均运行时间只有经典算法(Ford-Fulkerson算法)运行时间的10%,表明本文方法的有效性.
With the increase of network size, increasing the efficiency of the algorithm becomes the key to solve the problem.In order to reduce the computational complexity of solving the maximum flow in large-scale networks, this paper simulates the idea that human minds gradually solve complex problems, A simple method based on kernel computing is proposed to solve the problem of the maximum flow in the network.In this paper, a large-scale complex network is first granulated into several smaller sub-networks, and then the maximum flow of each sub-network is solved separately, Get the maximum flow of the original network.The method proposed in this paper can effectively reduce the computational complexity and provide a convenient way to obtain the maximum flow rapidly in a large-scale and complex network, and give a new idea to solve the maximum flow problem.Experiments on different networks The results show that the approximate solution error of the maximum flow can be controlled at about 1%, while the average running time is only 10% of the running time of the classical algorithm (Ford-Fulkerson algorithm), which shows the effectiveness of the proposed method.