共查询到10条相似文献,搜索用时 31 毫秒
1.
厍向阳 《计算机工程与应用》2009,45(33):13-15
针对网络最大流问题,在割集定义和最大流-最小割定理基础上,以邻接矩阵为网络数据存储结构,利用栈作为数据组织形式,遍历网络中所有割集,最小容量的割集即为网络最大流。流量网络其余分支流量由网络结点流量平衡条件来求解。该算法具有:开辟了一种求解流量网络最大流的新的方法,克服了割集和最大流-最小割定理仅仅具有理论价值、没有实用价值的局限性;根据最小容量的割集可以方便确定决定网络最大流的关键分支,为扩展网络流量提供直接技术支持。算法测试表明:基于栈的网络最大流算法是完全可行和有效的。 相似文献
2.
3.
点和边有容量约束的网络最小费用最大流算法* 总被引:1,自引:0,他引:1
分析了目前网络最小费用最大流算法存在的问题,提出网络最小费用最大流新算法。概括出条件约束下的网络最小费用最大流问题的两目标优化数学模型,针对点和边有容量约束的网络最小费用最大流问题特点,定义了有向路径、有向路径单位流费用和残量网络的概念。依据可行流分解定理,以邻接矩阵为网络数据存储结构,使用数据结构中的遍历方法,实现了网络最小费用最大流新算法。该算法在不破坏平面性条件下,可以求解点和边有容量约束的网络最小费用最大流。最后,通过实例进行了算法测试和比较。算法测试表明:点和边有容量约束的网络最小费用最大流算法是完全可行和有效的。 相似文献
4.
5.
6.
针对目前网络最大流算法存在的问题,研究一种适应性更广的新算法。定义了有向路径和残量网络的概念,依据可行流分解定理,引入人工智能中搜索的方法,以邻接矩阵为网络数据存储结构,提出条件约束下的网络最大流新算法。最后,通过实例进行了算法测试和比较。算法测试表明:点和边有容量约束的网络最大流新算法是完全可行和有效的。 相似文献
7.
研究并得到多源多汇网络的极限范围与运行边界.首先,定义临界流,现有研究的最大流和堵塞流是临界流的一部分;其次,得到多源多汇网络的所有临界流,并绘制成临界流曲线,完整刻画网络传输流量能力的极限范围,最大流流量位于曲线最高点、最小流流量位于曲线最低点;再次,利用临界流确定网络流的运行边界,边界内部和边界上均为可行流,边界外均为不可行流,同时提出多源多汇网络临界流、临界流曲线和运行边界的数学定义及求解方法;最后,给出临界流曲线和运行边界在规划和运行领域中的用途,多源多汇网络模型更接近于实际网络,其临界流曲线和运行边界的发现能帮助人们更深入了解实际网络运行的极限范围. 相似文献
8.
从本质上来说,最小割集问题与最大流问题是同一个问题。由于后者的实用性更强,人们对它投入的关注与研究也更多,因而实际中是通过最大流问题来求最小割集问题。最大流-最小割集定理给出了一种用最大流算法求最小割集问题的方法,但在实际应用中,这种方法有时显得繁冗并有些迂回。文章首先介绍了最大流、最小割集的相关概念,然后从实际应用出发提出了一种用最大流求流图最小割集的新算法。随后证明了该算法的正确性,并举例说明了这种算法思想在其它方面的应用。 相似文献
9.
10.
节点和边都有容量的有向平面网络中的最小截和最大流 总被引:5,自引:0,他引:5
在一般网络中,节点和边都有容量的最小截、最大流问题很容易转化为仅边有容量的问题.但传统转化方法用在平面网络中破坏了网络的平面性,使平面网络中节点和边都有容量的问题比仅边有容量的问题难.使用传统转化方法得到的两个问题的算法复杂度均为O(n2logn)(n表示网络中的节点数).对此,作者曾给出了无向平面网络中最小截问题的保持平面性的转化方法.在此基础上,这里进一步讨论有向平面网络中的最小截、最大流问题,给出有向网络中保持平面性的转化方法,并利用此转化得到了复杂度均为O(nlogn)的最小截和最大流算法.从并行计算复杂性角度来看,传统方法转化后的问题是P-完全的.而使用新方法可以得到NC算法,且可以证明节点和边都有容量的有向平面网络中的最小截、最大流问题都是属于NC的. 相似文献