求解网络最大流问题的信念传播算法

为解决目前网络最大流问题求解效率低、数据溢出等问题,设计求解网络最大流问题的信念传播算法.根据网络最大流问题的特性,使最大流问题的线性规划方程与信念传播算法传递方程结合,得到描述函数,将带权随机有向图映射为对应的因子图模型;在此模型基础上,利用信念传播算法的信息迭代方程进行特征值收敛计算,提高寻优效率.选取若干随机有向...     

求解最小费用最大流的新方法

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

最小费用最大流问题的一种新算法

现有的最小费用最大流算法都有自身的缺陷,增广链的选取不当会给计算带来不便,同时费用也达不到理想的效果。鉴于对最小费用最大流算法的增广链选取和最小费用的探索,文章通过对费用差的定义给出了一种求最小费用最大流的新算法。新算法的原则是优先选择费用差最小的有向路径进行增广,当费用差相同时就选择修正后的路径。通过对最小费用最大流算法的改进,新算法易理解且便于计算。通过实例说明了新算法的有效性和执行效率。     

最小费用最大流算法(C++)实现

最小费用最大流是一类网络优化问题,它与最大流的区别在于,它不仅要考虑流量问题,还要考虑费用因素,其优化的目标是流量最大且费用最小。本文综合求最大流原理和求最短路原理,在直接输入初始状态下就求出任何一个网络图的最小费用值,最大流值以及其他一些相关数据。该算法程序可以为我们减少大量计算,提高工作效率,因而它在信息学竞赛,国际信息学竞赛,大学生数学建模比赛等方面都能得到应用。     

最小费用最大流

针对当前很多最小费用最大流算法存在的问题和缺陷,用实例做出修正和完善.     

最小费用最大流算法（C＋＋）实现

最小费用最大流是一类网络优化问题，它与最大流的区别在于，它不仅要考虑流量问题，还要考虑费用因素，其优化的目标是流量最大且费用最小。本文综合求最大流原理和求最短路原理，在直接输入初始状态下就求出任何一个网络图的最小费用值。最大流值以及其他一些相关数据。该算法程序可以为我们减少大量计算，提高工作效率，因而它在信息学竞赛，国际信息学竞赛，大学生数学建模比赛等方面都能得到应用。     

最小费用最大流新解尝试

最小费用最大流是有向图中常见的问题,一般的解法是从已给出的初始流量构造增广链,逐步得到最大流。最小元素法是运输问题初始方案的构造方法之一,仿照这种方法构造出来的最小费用最大流问题的＂最小元素法＂,并且对于比较简单的有向图求解最小费用最大流问题,容易得到最优解。     

一种基于改进堆优化Dijkstra算法的最小费用最大流算法

通过最短路径算法在残存网络中搜索汇点的最小费用路径是流网络中求解最小费用最大流的主要方式,而Dijkstra算法是最高效的最短路径算法之一。本文通过证明残存网络中不存在负循环,采用改进的堆优化Dijkstra算法在残存网络中搜索最小费用路径以提升算法的效率。实验结果表明,与经典的基于最短路径快速算法的最小费用最大流算法和基于Bellman-Ford算法的最小费用最大流算法对比,本文提出的改进算法具有更高的时间效率。     

基于最小费用最大流问题的“排序”算法

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

基于最小费用最大流的大规模资源调度方法

并行作业是大规模资源调度的研究热点.已有研究工作通常采用队列进行资源调度建模,仅能满足局部最优解,只能适应调度目标固定不变的场景,灵活性不够.提出了一种基于最小费用最大流的大规模资源调度建模方法,将任务的资源需求和物理资源供给问题转换成最小费用最大流图的构造和求解问题.首先,选择公平性、优先级和放置约束三种典型度量作为切入点,从资源视角映射为图的构造问题,通过改变图的结构使其具备适应性调整能力.其次,针对图的求解时间复杂度高的问题,实现了一种增量式优化算法.最后,实验对比公平性、优先级和放置约束三种资源调度典型系统,验证了本方法可通过按需配置,支持多种调度目标,具备灵活性.并通过实验仿真验证了万级规模下基于图的资源调度延迟,比基于未优化图算法的资源调度延迟最多降低10倍.     

求解多文字可满足SAT问题的置信传播算法

可满足(SAT)问题是指:是否存在一组布尔变元赋值,使得合取范式公式中每个子句至少有一个文字为真.多文字可满足SAT问题是指:是否存在一组布尔变元赋值,使得CNF公式中每个子句至少有两个文字为真.显然,此问题仍然是一个NP难问题.为了研究解决多文字可满足SAT问题的算法,引入随机实例产生模型,设计求解多文字可满足SAT问题的置信传播算法.最后,用实例模型产生了大量数据进行实验验证,结果表明:该算法求解多文字可满足SAT问题的性能优于其他启发式算法.     

A two-phase algorithm for the biobjective integer minimum cost flow problem

We present an algorithm to compute a complete set of efficient solutions for the biobjective integer minimum cost flow problem. We use the two phase method, with a parametric network simplex algorithm in phase 1 to compute all non-dominated extreme points. In phase 2, the remaining non-dominated points (non-extreme supported and non-supported) are computed using a k best flow algorithm on single-objective weighted sum problems.     

一种求解最小双费用流问题的算法

多目标优化是网络最优化的一个重要子问题。通过实际应用案例,抽象出一种带容量限制的双费用权网络模型,并由此提出了相应的最小双费用流问题。之后,借鉴网络分层的思想,根据双费用权网络的特点设计出一个求解该问题的双层原始对偶算法,并严谨地证明了算法的正确性,估计出算法的复杂度为O(n2v0)。此外,对算法进行了推广改进,使其能求解一般k费用权网络中的最小k费用流问题。最后,通过一个实例来演示算法的执行。     

Probabilistic tree-based representation for solving minimum cost integer flow problems with nonlinear non-convex cost functions

The minimum cost flow problem (MCFP) is the most generic variation of the network flow problem which aims to transfer a commodity throughout the network to satisfy demands. The problem size (in terms of the number of nodes and arcs) and the shape of the cost function are the most critical factors when considering MCFPs. Existing mathematical programming techniques often assume the cost functions to be linear or convex. Unfortunately, the linearity and convexity assumptions are too restrictive for modelling many real-world scenarios. In addition, many real-world MCFPs are large-scale, with networks having a large number of nodes and arcs. In this paper, we propose a probabilistic tree-based genetic algorithm (PTbGA) for solving large-scale minimum cost integer flow problems with nonlinear non-convex cost functions. We first compare this probabilistic tree-based representation scheme with the priority-based representation scheme, which is the most commonly-used representation for solving MCFPs. We then compare the performance of PTbGA with that of the priority-based genetic algorithm (PrGA), and two state-of-the-art mathematical solvers on a set of MCFP instances. Our experimental results demonstrate the superiority and efficiency of PTbGA in dealing with large-sized MCFPs, as compared to the PrGA method and the mathematical solvers.     

网络最大流的自适应求解算法——SAPR算法

为提升对大规模不同拓扑结构网络的求解速度,通过评估基本操作的执行效率、动态调整活跃顶点的选择方式及盈余流的推进方式,提出了一种可高效求解多类拓扑网络的自适应预流推进算法——SAPR(self-adaptive push-relabel)算法.在The First DIMACS implementation Challenge提供的七类不同拓扑结构网络上,对SAPR算法及四种适用于特定拓扑网络的算法进行了对比实验,结果表明:SAPR算法在一半的数据上能持平高效的H_PRF算法,而另一半能超越H_PRF算法.SAPR算法的高效性和强稳定性解决了传统算法在多类拓扑网络中不能都取得高效率的问题.     

一种改进的警示传播算法求解Max-SAT问题

Max-SAT问题是SAT问题的优化版本,目标是在给定的子句集中找到一组变元赋值,使得满足子句数最多,该问题是典型的NP-hard问题。随着大数据和人工智能的深度发展,过去原有的算法已不再适用,设计新的求解算法或对已有的求解算法进行优化是目前研究的热点。针对警示传播算法求解随机Max-3-SAT问题的局限性,提出了一种基于变元权值计算的警示传播算法,结合随机游走算法,给出一种新型算法WWP+WalkSAT,通过改进求解的局限性,更好地得到一组有效的初始解,从而提高算法的局部搜索能力。利用2016年Max-SAT国际竞赛部分基准实例,将WWP+WalkSAT算法与八种局部搜索算法进行精度方面的对比实验。实验结果表明,WWP+WalkSAT算法有较好的性能。     

一种求解命题公式骨干集的警示传播算法

警示传播WP算法是一类重要的信息传播算法,在命题公式的可满足性判定中非常有效。通过对WP算法的数学原理分析发现,当算法收敛时以高概率固定部分变元的赋值,可以对公式进行化简。基于这样的特征修改WP算法的迭代方程和变元赋值条件,设计了一种求解命题公式骨干集的信息传播算法。当变元数目超过400时,与经典骨干集求解算法对比,效率提高了40%,与目前常用算法对比也有10%的提高。结果表明,所提算法求解命题公式骨干集时非常有效。     

可满足性问题中信念传播算法的收敛性分析

信念传播算法是基于因子图模型的消息传递算法,通过图中的边,将消息从一个结点传递给另一个结点,以高概率地确定部分变量的取值,这种方法被实验证明在求解可满足性问题时非常有效.然而,目前还未对其有效性从理论角度给予解释.通过对信念传播算法的收敛性分析,试图从理论上解释算法的有效性.在信息传播算法的信息迭代方程中,参数的取值范...     

一种改进的基于最大流的Web社区挖掘算法

针对原始最大流算法给每条边的边容量分配一个常量值,在社区质量及成员数量上造成的问题,提出了一种改进的Web社区挖掘算法。该算法考虑不同边的重要性差异,将加权PageRank算法中页面的重要度转化为衡量页面之间边重要性的传递概率值,并使用该值对边容量进行赋值。实验结果表明,改进的算法有效地提高了Web社区的质量。