考虑板坯设计的组炉优化模型

针对炼钢生产中的组炉优化问题,建立了一种考虑板坯设计的混合整数规划模型,并提出了一种基于非二分图匹配算法、二分图匹配算法、装箱算法、网络最大流算法的启发式求解算法。该算法首先使用非二分图匹配算法确定炉次,然后使用二分图匹配算法和装箱算法将剩余合同匹配到已有炉次中,最后使用网络最大流算法调整炉次中合同对应的板坯重量。实验结果表明利用该算法可以在较短的时间内给出较优的组炉方案,为计划员提供足够的决策支持。     

求最大权伪对集的一个算法

图的可以含有环的对集称为图的伪对集。William 和 Anderson 给出了求图的最大基数伪对集的一个算法。本文给出了求图的最大权伪对集的一个算法,它是 Edmonds 算法的一个推广。     

大规模网络最大流对偶图算法模型及实现

在网络最大流算法的研究中,为了减少计算量,提出了许多改进的方法.基于图论中的最大流最小割定理,利用网络流图的对偶图的最短路径求网络最大流,对求最短路径的Dijkstra算法进行了研究,给出了一种改进的Dijkstra算法模型,该算法采用了堆排序中的小根堆来选择最短路径结点,使用集合运算对堆中的结点进行处理,使得参加运算的结点数减少,提高了算法的效率.     

线性模拟电路的一种故障定位法——改进的节点定位法

本文采用节点导纳矩阵表示的故障诊断方程,给出了线性有源网络节点故障定位算法,该方法避免了不必要的运算。整个节点故障定位过程中只需讨论双图公共生成树是否存在,并对此问题提出了新的判断方法,当算法不能对故障唯一定位时,仍有可能给出故障区域。该算法用FORTRAN语言编制成程序在IBM-PC微型机上进行了验证。     

指派问题的新算法

给出了关于指派问题的新算法：在差额最大的行或列中优先寻找最小元素．一般地说，此算法优于匈牙利法及[2]所论及的方法．     

图的字典积的整数流

得到对连通图G1和阶数大于3的图G2,他们的字典积G1[G2]有非零4-流.特别当G2是二部图时,G1[G2]有非零3-流.通过一个完全不同的方法,也得到了如果G1有非零3-流且具有完美匹配或G2有非零3-流,那么G1[G2]有非零3-流.     

动态网络中最大流快速增量求解

利用损毁网络与原网络的结构包含性,提出了一种基于增广路径选择树的最大流增量算法MFIA-ART.算法在原网络最大流的求解过程中,对简单路径集等相关的中间结果给予缓存,构成增广路径候选集,当网络拓扑改变时直接在其中查找有效的增广路径,无需对新的残余网络进行复杂计算.同时为了避免遍历包含饱和边的简单路径,进一步利用增广路径选择树ART来组织所有可能的增广路径集,从而可以通过一条从根节点到某个叶节点的路径找到所有需要的增广路径,获得最大流量.其遍历的深度为ART树的高度H,远小于所有增广路径的数量,因而显著地提高了求解最大流的效率.实验结果表明,MFIA-ART相对于采用经典的Dinic算法重新计算最大流的方法,在时间性能方面有数量级的提高,尤其适合应用于简单路径数量较少的稀疏性网络.     

最小生成树边与边的权的调整

图的最小生成树已经有了好算法，但当图增加或删去几条边或少数几条边的边调整时，最小生成树的边、权可能发生变化，用原算法寻找最小生成树时，显得比较麻烦．利用破回路算法给出一个简单的 方法．并给出了相应的示例．     

最大流问题的DNA计算两阶段法

给出了最大流问题的DNA计算两阶段法：第一阶段采用路序问题DNA算法得到包括所有增广路的路集,算法有两点改进,即采用等码长编码和不进行排序,这减少了生化实验时间．第二阶段算法思路是：设置一个逐步减小的增量△,对每个确定的△值从第一阶段得到的路集中寻找并增广容量不小于△值的增广路,对整数容量网络,当△＜1时获得最大流．证明了算法的正确性和复杂性,并指出在以增广路为基础的最大流算法中,本算法复杂度最低,这说明DNA计算和电子计算相结合的巨大优势．     

一种三边Switch-box的布线问题及其图论算法

本文将一种VLSI中的三边Swithc-box的布线转化为图论中的求偶图的最大非交叉匹配问题,并在文献[1]思想的基础上提出了一个求偶图的最大非交叉匹配的有效算法。该算法已在IBM PC/XT上用FORTRAN77实现。最后给了算法用于三边Switch-box布线的实例。     

区间图上的并行算法设计

对区间图上的图问题并行求解,给出两种算法设计方法,利用这两种方法,对最小团覆盖,最大团,最大独立集,最小支配集,Hamiltonian回路,最佳道路覆盖,最小带宽和Steiner树的计算问题,在EREW PRAM模型上给出O(logn)时间,使用O（n)处理器的高效并行算法。     

区间图上的并行算法设计

对区间图上的图问题并行求解,给出两种算法设计方法.利用这两种方法,对最小团覆盖、最大团、最大独立集、最小支配集、Hamiltonian 回路、最佳道路覆盖、最小带宽和Steiner 树的计算问题, 在EREW PRAM 模型上给出O(logn) 时间,使用O(n) 处理器的高效并行算法.     

网络流量最优化算法的讨论

讨论了一个实现网络流量最优化算法,本算法给出了流网络的最大流量,还给出达到最大流量的若干方案,可以广泛应用于各种流网络的规划中。     

用最小费用流的允许边算法求解指派问题

构造指派问题的最小费用最大流模型,并将基于对偶原理的允许边算法用于该模型,提出了求解指派问题的一种新算法。该算法按照互补松驰条件,通过修改已标号节点的势,在容量-费用网络中逐步扩大允许网络,并在其中增广流量,直至求得容量-费用网络的最小费用最大流,此最大流中的非0流边即对应于指派问题的最优指派。在迭代过程中,后续迭代充分利用了上一迭代的信息,有效节省了计算量。对于非标准指派问题,可以直接求解,而不需要先将其转化为标准形式。     

最大匹配问题的DNA试管计算模型

最大匹配问题是找给定图G中任意两条边都没有公共端点的最大边集,是NP完全问题.算法的关键是将数学问题转换到DNA链上,对图中的每条边进行适当的编码,利用生物操作及生物酶产生链及最终链的分离.给出了基于分子生物技术的图的匹配问题的DNA计算的试管方式.结果表明,提出的算法是有效可行的.     

计算网络最大流的表格法

给出了计算网络最大流的表格法，避免了标号法(由Ford-Fulkerson提出)在计算最大流过程中选择增流链的随机性，并通过实例给出了具体算法步骤．     

用节点子树剪枝构造网络最短路径

人网络联结图的邻接矩阵出发，提出了在Ｉｎｔｅｒｎｅｔ网络环境下直接构造网络最短主树的一种方法－－节点子树剪枝法，在无约束条件和有约束条件，给出Ｉｎｔｅｒｎｅｔ最短主树算法，该算法用于计算Ｉｎｔｅｒｎｅｔ环境下可扩展的ＩＰ路由表具有较高效率。     

混合图网络上的 s-t-流(运筹学与控制论)

在混合图的框架下,给出网络上路段、路径、路径系统、路段s-t-流、路径s-t-流及正向路径s-t-流等定义,并表明无圈路径系统上的最大流一定是正向路径s-t-流。设计一个分解路段s-t-流为路径s-t-流的多项式时间的分解算法,并做算法分析证明其可行性与复杂性。给出并证明一个表现分解前后的路段流与路径流之间关系的分解定理。给出并证明关于路段s-t-流的收发点的流量守恒公式。进一步讨论两种流的互相转化及其有关性质,特别地,给出了它们互相转化的方式,并证明了当它们互相转化时流值不变。此项工作改进与推广了Ford和Fulkerson,Korte和Vy-gen及其它学者关于s-t-流的基础理论工作。     

求解单圈多部图的匹配算法

给出了一个多部图及其匹配问题的定义,提出了求解单圈多部图匹配问题的一个算法。该算法提出多部图顶点间的可达性定义,并使用试探与缩小规模相结合的方法以及求二部图的最大匹配算法,求解单圈多部图的最大匹配问题。经过验证,算法的效率比较高。     

基于最小生成树的立体匹配算法

在传统的局部立体匹配算法中,代价聚合要对相关邻域内的点进行加权聚合,这种方式计算量大,非常耗时。文章提出一种基于最小生成树的立体匹配算法,该方法将图论中的最小生成树引入代价聚合和视差细化中,使得图像中所有点都对兴趣点进行聚合支持,弥补了局部算法在弱纹理区误匹配率高的局限性,提高了匹配的准确性,并且最小生成树能够对图像所有点进行层次性的划分,极大地简化了计算量。实验证明,该算法能够快速得到平滑且精度高的视差图。