粒计算求解复杂网络最大流的研究

• 作者: 刘倩倩 张燕平 苏建忠 赵姝
• 来源期刊: 小型微型计算机系统
• 学科: 工学
• 关键词: 最大流 复杂网络 粒计算 粒化 合成
• 年，卷（期）: 2014,（11）
• 所属期刊栏目: 计算机网络与信息安全
• 页码范围: 2450-2453
• 页数: 4页
• 分类号: TP18
• 字数: 4029字
• 语种: 中文

摘要

网络最大流问题是经典的组合优化问题,随着网络规模的增加,提高算法效率成为解决问题的关键.为了降低求解大规模网络最大流的计算量,本文模拟人类思维逐步求解复杂问题的思想,提出一种基于粒计算求解网络最大流问题的简单方法.本文首先将大规模复杂网络粒化为多个规模较小的子网络,再分别求解各子网络最大流,最后将子网络最大流合成得到原网络最大流.本文方法有效地降低了计算的复杂性,为在大规模复杂网络中快速获取最大流提供了方便,并给出一个解决最大流问题的新思路.不同网络上测试的实验结果显示,最大流的近似解误差可控制在1％左右,而平均运行时间只有经典算法(Ford-Fulkerson算法)运行时间的10％,表明本文方法的有效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张燕平	安徽大学计算机科学与技术学院	148	1556	21.0	32.0
5	赵姝	安徽大学计算机科学与技术学院	82	555	13.0	19.0
9	刘倩倩	安徽大学计算机科学与技术学院	18	35	4.0	5.0
13	苏建忠	安徽大学计算机科学与技术学院	1	4	1.0	1.0