-
题名基于一个网络图最大流算法的改进
被引量：8
- 1
-
-
作者
赵礼峰
陈华
宋常城
白睿
-
机构
南京邮电大学理学院
-
出处
《计算机技术与发展》
2010年第12期162-165,176,共5页
-
基金
南京邮电大学科研基金项目(NY207149)
-
文摘
现有的求解网络最大流算法,存在由于增广链选取的顺序不当而无法得到理想的最大流,且在计算过程中每步都需要画一个网络图等问题。针对上述问题展开讨论,并对一些最大流算法进行改进。利用分层网络及容差的概念,在选择增广链的时候优先选择路径最短且容差较大的路径,并将已饱和的弧画上终止符。最后通过具体的算例验证了改进算法可以简单快速地找到增广链,且避免了标号过程,只需要在一个图上即可完成。整个运算过程,直观性强,计算方便。改进的算法较其他的算法具有高效性和实用性的优势。
-
关键词
最大流
增广链
Ford-Fulkerson算法
增广链算法
容差
消链
-
Keywords
maximum flow
augmenting path
Ford-Fulkerson algorithm
augmenting path algorithm
tolerance
eliminating chain
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名一种求解网络图最大流的新算法
被引量：2
- 2
-
-
作者
赵礼峰
董方
-
机构
南京邮电大学理学院
-
出处
《计算机技术与发展》
2014年第2期120-122,126,共4页
-
基金
国家自然科学基金资助项目(GZ210039)
-
文摘
给出一种求解网络最大流的新算法,该算法是针对增广链选取的顺序不当而无法得到理想的最大流,且在计算过程中每步都需要画一个网络图等问题进行的改进。利用分层及度差的概念,在选择增广链时优先选择路径最短且度差较大的路径,相同层次度差相同时优先选择容差较大的路径,在饱和的弧上画上终止符。最后用实例进行了验证并和Ford-Fulkerson算法做了比较,体现了它的高效性,避免了标号,且只需要在一个图上即可完成。整个运算过程直观性强,计算方便。
-
关键词
最大流
增广链
增广链算法
度差
容差
-
Keywords
maximum flow
augmented chain
augmented chain algorithm
degree of difference
allowance
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名带有模糊流量限制的最大流问题
- 3
-
-
作者
邓珍美
陈岩
白晓莉
-
机构
沈阳工业大学理学院
-
出处
《商丘师范学院学报》
CAS
2024年第6期29-34,共6页
-
基金
辽宁省科学技术厅科学技术计划项目(2019-ZD-0209)。
-
文摘
定义构造区间中智数的基本运算,提出中智逻辑并给出数学定义,通过概率论期望的概念提出中智数学期望的定义.结合图论,提出用区间中智数表示网络流中每条弧上的模糊信息,通过改进区间中智数运算并运用增广链算法调整流网络流量,给出中智最大流问题的中智线性规划模型.最后通过算例给出算法具体实现步骤,得到中智环境下的最大流以及流量的波动率,结果说明运算可行,算法合理有效.
-
关键词
区间中智数
增广链算法
数学期望
中智最大流
-
Keywords
neutrosophic number
augmenting chain algorithm
mathematical expectation
neutrosophic maximum flow
-
分类号
N37
[自然科学总论]
-
-
题名基于深度优先的一种网络最大流求解法
被引量：2
- 4
-
-
作者
赵礼峰
孟晓婉
-
机构
南京邮电大学理学院
-
出处
《计算机技术与发展》
2012年第10期161-164,共4页
-
基金
国家自然科学基金资助项目(61070234
61071167)
-
文摘
网络最大流问题在工程和科学领域应用广泛,许多线性规划的实际问题都可转化为网络最大流的模型来求解,开辟了图论应用的新途径。为了解决现有的求解网络最大流算法存在的步骤繁复、计算量大、由于增广链选取的顺序不当而无法得到理想的最大流等问题,文中在原有算法的基础上作了一些改进,应用图的深度优先搜索原理,提出一种新的求解最大流问题的算法。该算法可以简单快速地找到增广链,提高了算法效率和可控性,易于实现,且避免了标号过程,只需要在一个图上即可完成,整个运算过程直观性强,计算方便。
-
关键词
最大流
增广链
增广链算法
深度优先搜索
-
Keywords
maximum flow
augmenting path
augmenting path algorithm
depth first search
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
