首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到19条相似文献,搜索用时 78 毫秒
1.
网络最大流部分割矩阵算法   总被引:1,自引:1,他引:0  
毛华  毛晓亮  李斌 《计算机科学》2011,38(12):229-231,246
网络最大流问题是图论研究中一个经典的模块。首先,利用粗糙集属性约简的差别矩阵算法思想,定义网络的一个部分割容量矩阵。其次,通过集合的交和并运算,找出网络的所有割集,从而得到最小容量割集。之后,在最大流最小割定理的基础上,得到网络的最大流。  相似文献   

2.
近年来,随着各种网络的飞速发展,对最大流问题的研究也取得了很大的进展。文章简述了网络最大流问题的现状,提出了一种求解网络最大流与最小截问题的算法。此算法使得计算网络最大流变得简便,且具有很强的实用性。  相似文献   

3.
小容量网络上的最大流算法   总被引:10,自引:1,他引:9  
最大流问题是一类经典的组合优化问题。描述了一种小容量网络,这种网络有强的实际应用背景,同时给出了专门解这种网络上最大流问题的算法。该算法比通用的算法快。它已经突破了最大流问题的O(mn)时间障碍,具有较强的理论意义,也为解决许多实际应用问题提供了更有效的算法。同时,由于判断一个网络是否为小容量网络非常简单,因此该算法也具有普遍意义。  相似文献   

4.
点和边有容量约束的网络最小费用最大流算法*   总被引:1,自引:0,他引:1  
分析了目前网络最小费用最大流算法存在的问题,提出网络最小费用最大流新算法。概括出条件约束下的网络最小费用最大流问题的两目标优化数学模型,针对点和边有容量约束的网络最小费用最大流问题特点,定义了有向路径、有向路径单位流费用和残量网络的概念。依据可行流分解定理,以邻接矩阵为网络数据存储结构,使用数据结构中的遍历方法,实现了网络最小费用最大流新算法。该算法在不破坏平面性条件下,可以求解点和边有容量约束的网络最小费用最大流。最后,通过实例进行了算法测试和比较。算法测试表明:点和边有容量约束的网络最小费用最大流算法是完全可行和有效的。  相似文献   

5.
针对目前网络最大流算法存在的问题,研究一种适应性更广的新算法。定义了有向路径和残量网络的概念,依据可行流分解定理,引入人工智能中搜索的方法,以邻接矩阵为网络数据存储结构,提出条件约束下的网络最大流新算法。最后,通过实例进行了算法测试和比较。算法测试表明:点和边有容量约束的网络最大流新算法是完全可行和有效的。  相似文献   

6.
基于最小费用最大流问题的“排序”算法   总被引:1,自引:0,他引:1  
由于现有的求解最小费用最大流问题的方法都存在其局限性,为了更好地解决实际问题,在已有最短路算法以及最小费用算法的基础上作了改进,给出了一种求解基于最大流的最小费用问题的算法.文中针对小规模网络给出求两点之间最小费用的一种简单易行的方法,此外该算法可以在一个图上完成,这样可以节省许多画图时间,增强了算法的直观性和可控性.并且构建石油运输的网络模型,结合最小费用最大流算法,给出该模型从产地到销地的最优运输方案,最后通过具体的模型实例验证了该方法的效率和实用性.  相似文献   

7.
网络最大流问题研究进展   总被引:27,自引:1,他引:26  
网络最大流问题和它的对偶问题——最小截问题,是一对经典组合优化问题,它们在许多工程领域和科学领域有重要的应用,是计算机科学和运筹学重要的内容,最大流问题已经有40多年的研究历史,近年来,随着各种网络的飞速发展,最大流问题的研究也取得了很大的进展,对最大流问题研究做了详细的总结,并对下一步研究趋势进行了预测。  相似文献   

8.
庞博  谢政  陈挚  张军 《计算机工程》2010,36(7):252-254
动态(时间依赖的)容量网络与传统静态网络相比更具现实意义,在交通网络、物流网络和通信网络中都有着广泛的应用。在时间依赖网络最短路算法的基础上,研究具有实际背景的动态容量网络的最小最大时间流问题,给出求动态容量网络的最小最大时间流的多项式算法和算法的应用实例,其时间复杂度为O(mMv)。  相似文献   

9.
文中给出了一种求解网络最小费用最大流的新方法,寻找由始点到终点的每条有向链,找到有向链可通过的最大容量,根据最大容量计算出此条有向链的最小费用最大流,根据最大容量和最小费用最大流可以计算出单位费用.选取单位费用最小的有向链进行最大容量的增广.文中通过对最小费用路算法进行改进,使得该算法容易理解,却又避免了最小费用路算法每次都要经过剩余网络进行增广,从而大大提高了求解最小费用最大流执行的效率.该算法通过实例给出了具体算法步骤并且表明了算法的实用性  相似文献   

10.
网络最大流问题是图论中的经典问题之一,对于最大流问题有很多经典的算法,但这些经典算法皆有不足之处。针对其不足,文中通过引入容量差的概念,对算法进行了一些改进。改进算法的原则是优先选择路径最短且容量差最大的路径进行增广,若当路径长度一样并且容量差也一样时就要对其修正,然后选择修正后的路径,这样每次增广至少使一条弧达到饱和。通过实例说明了改进算法的可行性,整个运算过程可以在一个图上完成,直观性强并且方便计算,较传统算法更为有效。  相似文献   

11.
基于虚拟顶点最大流的城市路网通行能力算法   总被引:1,自引:0,他引:1       下载免费PDF全文
针对城市道路路网通行能力的确定问题,通过引入虚拟起、讫点改造路网。应用图论中最大流最小割定理,对最大流算法进行了改进;提出了一种在容量限制下确定路网通行能力的算法,使得多起点、多讫点的道路路网通行能力的确定得以简化。用算例验证了算法的正确性。  相似文献   

12.
无线网络容量一直是无线网络领域的研究热点,而网络编码通过赋予中间节点对接收数据包进行编码、组合的能力,可以有效提高网络容量,达到最大流—最小割定理确定的理论上限.本文在Gupta和Kumar提出的信号干扰噪声比模型基础上,首先分析网络节点均匀分布时发送节点与目的节点进行多跳传输的无线网络容量计算方法;接着推导出了基于网络编码的无线网络容量计算公式,并利用MATLAB中求解线性规划问题的函数linprog()求解网络最大流及各链路流量,以此求出无线网络容量上界.通过对无线网络容量上界进行MATLAB仿真,得到如下结论:无线网络容量上界随节点数量的增加呈现先增加后减少的趋势;且当节点数量趋于无穷大时,网络容量趋于零;与传统的存储转发模式相比,采用网络编码有利于提高网络容量.  相似文献   

13.
王仁群  彭力 《计算机应用》2016,36(9):2357-2361
针对数据中心网络(DCN)的链路拥塞问题,提出了一种拓扑感知型拥塞控制算法(TACC)。首先,根据广义超立方体拓扑多维正交和单维全连接的结构特点,结合网络流的最大流最小割定理,提出了拓扑感知地选取分布流量请求的不相交路径策略;然后,根据带宽需求自适应选取不相交路径;最后,利用已选取路径的剩余带宽为权重动态调整每条路径的流量分配比例,从而达到缓解网络链路拥塞、均衡网络负载和减轻目的节点侧数据重组压力的目的。实验结果表明,与链路关键性路由算法(LCRA)、多路径健忘路由算法(MORA)、最小割多路径路由(MCMP)算法和免拥塞路由策略(CFRS)相比,TACC算法在均衡链路负载和优化算法部署时间方面有良好的表现。  相似文献   

14.
视频分割是视频处理领域的基本问题,也是该领域的研究前沿和热点问题之 一,在视频监控、编辑合成等方面都有着重要的应用。传统的视频分割方法大多依赖帧间局部 相似性或运动的连续性进行区域划分,对遮挡、大幅度运动等情况的分割效果较差,需要大量 的手工交互。论文通过在视频空间建立跨时空域的相似性邻接关系,提出一种新的视频分割图 分割模型,并且采用最大流/最小割算法对相应的模型进行快速求解,从而实现视频的有效分割。 论文算法只需要用户在视频的关键帧图像上进行少量交互,便自动获取整个视频分割结果;并 且,该分割过程不受前景对象遮挡、快速运动等情况的影响,具有很好的稳定性。  相似文献   

15.
针对传统边缘检测算法无法准确提取目标及其边缘的问题,基于交互式图论的最大流/最小割理论提出了一种新的边缘检测算法,设计了一种新的代价函数OE_COST 目标边缘代价函数;通过建立图割模型,能够在分割出目标的同时提取出目标边缘。算法通过交互式选择背景及目标像素集合作为硬性约束,通过图像特征(如灰度级、空间信息等)建立代价函数作为软性约束,同时施加软硬约束达到提取目标边缘的目的。实验结果表明,本算法可以准确提取出目标及其边缘轮廓。  相似文献   

16.
提出了一种基于TCP/IP协议栈来实现网络家电网关的方法.利用TCP/IP协议栈中的IP,TCP,DHCP,DDNS等协议来实现一个完整的具备各种功能的家庭网关.这种设计将可以使现有的家庭计算机网络中的网关,如宽带路由器等只需要做少量的改动,就可成为一个网络家电的网关,满足实现未来网络家电远程控制和集中控制的需求.  相似文献   

17.
一种基于图割的改进立体匹配算法   总被引:5,自引:0,他引:5  
针对基于图割法的立体匹配算法耗时太长的问题,提出了一种基于简化网格图的立体匹配算法.算法 通过区域匹配算法得到每个像素的初始视差值,然后只保留完整网格图的部分可能的视差值,去除其余大部分的节 点和边缘,建立简化的网格图.该方法大大缩减了网格图的容量,缩短匹配所用时间,并且能够选用更大的视差范 围.实验证明,该算法能够得到比较理想的视差图,而且大大缩短立体匹配所用时间.  相似文献   

18.
最大流最小割的理论决定了网络的最大吞吐量,网络编码可以使这一理论在单元多播的网络环境下得以实现,其核心思想是在网络的中间节点引入编码功能,对收到的数据包进行相应编码后再转发出去,有别于传统网络的简单存储和转发操作.文章介绍了网络编码的原理、优势,分析了线性网络编码理论,并对其构造方法进行了改进,降低了复杂度.  相似文献   

19.
袁正午  段莉丹 《计算机应用》2012,32(11):3089-3091
针对无线射频识别(RFID)系统中的标签防碰撞问题,详细分析典型的二进制算法、动态二进制算法及后退式二进制算法的原理,同时考虑识别次数和传输位数这两方面的性能,提出了一种快速高效的防碰撞算法。通过对标签进行预处理以及在阅读器中设置堆栈,有效地减少碰撞算法中的识别次数和传输冗余信息。仿真结果表明该算法在次数效率和位数效率性能上有较大的提高。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号