交通网络k-短路径与最小支撑树问题

为了给交通管理部门提供多个路径诱导信息,基于经典的最短路径算法——Dijkstra算法,研究了赋权交通网络的k-短路径问题。k-短路径问题是在网络G中求出给定起讫点对之间的k条路径P1,P2,…,Pk,满足W(P1)≤W(P2)≤…≤W(Pk),其中W(*)表示路径*的权值。在网络G的基础上,通过对G的点、边重新划分以及对边上的权值重新赋值,构造出了1个新的网络G′并讨论了它的几个性质。从而将G的k-短路径问题转换为求解G′的最小支撑树问题,进一步,最小支撑树问题又等价于求G′中一条边的权值。研究结果表明:由于最小支撑树问题具有多项式算法,得到关于k-短路径问题的多项式算法,其时间复杂性为O(k(m+nlg(n))),m和n为G的边数和顶点数。最后通过算例给出了算法的具体执行过程,同时验证了其可行性。     

社交网络中的概率支配集问题

针对一种边权重取值范围为[0,1]的无向带权图,提出在社交网络中有实际应用的概率支配集概念.在图中寻找最少点数的概率支配集称为最小概率支配集问题.证明最小概率支配集问题是NP(非确定性多项式)难问题,表明不太可能存在多项式时间复杂度的精确算法.基于次模函数提出了多项式时间复杂度的贪心近似算法,用于求解最小概率支配集问题...     

哈明距离下费用受限制约束最小支撑树反问题

讨论了瓶颈型哈明距离下费用受限制的约束最小支撑树反问题,通过修改给定网络边上的权,使得修改后网络中指定的支撑树是最小支撑树并且支撑树中的最大边的权不超过给定的常数,用瓶颈型哈明距离来衡量修改的费用,且修改的总费用不超过给定的上界.利用转化的思想,给出瓶颈型哈明距离下费用受限制的约束最小支撑树反问题的多项式算法及证明.     

附有条件的最小支撑树算法

传统最小生成树算法不能解决:度约束条件下的最小支撑树问题;动态网络的最小支撑树问题;边约束条件下的最小支撑树问题。遗传算法可以求解度约束条件下的最小支撑树问题,但存在效率低、编码复杂等缺陷。归纳了3类附有条件的最小支撑树数学模型,在最小支撑树传统算法基础上,提出了3类附有条件的最小支撑树算法。算法测试和比较表明:附有条件的最小支撑树算法是完全可行和有效的。     

约束最小支撑树问题

主要研究两类约束最小支撑树问题,即点约束和边约束最小支撑树问题.点约束最小支撑树问题主要研究了点v不是叶子和点v是叶子两个具体约束问题,边约束最小支撑树问题的约束条件分别为包含给定边e0和不包含给定边e0,对上述问题分别给出了一些基本定理和算法.     

一类特殊的极大＋和支撑树在调整和权值下的逆问题

本文研究的是一类特殊的极大＋和支撑树在调整和权值下的逆问题．给定一个边赋权连通网络G=（VE,c,w）,对于每一条边e∈E,已知一个费用c（e）和一个权值叫（e）,极大＋和支撑树问题是指寻找一棵支撑树T＊,使得其是权值marxw（e）＋∑c（e）最小的一棵支撑树．而在极大＋和支撑树的逆问题中,给定一棵支撑树％,eET它不是已知网络中最优的极大＋和支撑树,要求调整网络中各边的费用c（e）,使死变成调整后网络中最优的极大＋和支撑树,目标函数是使得在l1模意义下的边权调整费用尽可能的小．本文针对已知网络中各边费用都相等这一特殊情况,给出了求解该逆问题的列生成算法,每次迭代时入基向量的选择可以转化为一个新参数下的极大＋和支撑树问题,从而可在多项式时间内确定入基向量的选择．本文最后给出了一个实例说明算法的有效性．     

特定材料构建支撑树问题的近似算法研究

结合最小支撑树问题和装箱问题,该文研究了一类新的组合优化问题:给定权重图G=(V,E;w, c)和一种长度为L的特定材料,要在图G中寻找一颗支撑树,并用给定的材料来构建支撑树的边,支撑树的总构建费用包括材料费用和构建费用两部分,目标是使得总构建费用达到最小。该问题是NP—难的,不存在多项式时间算法,除非P=NP。该文对所提问题设计了一个2—近似算法,并分析了算法的复杂性,证明了算法的近似度。     

网格空间瓶颈斯坦纳树问题快速近似（英文）

指出了瓶颈斯坦纳树问题要求寻找一棵用至多k个斯坦纳点将n个点连接起来使得此斯坦纳树之最长边最短的斯坦纳树,该问题在VLSI、无线通讯网络和生命演化树重建等领域都有应用.Du和Wang证明网格空间瓶颈斯坦纳树问题是NP-Hard,不存在近似性能比低于2的多项式时间解决方案,并且提出一个近似性能比为2的多项式时间近似算法,算法的实际时间复杂度为O(nlog2n+kn+k2).通过引入二叉堆和斐波那契堆使算法的时间复杂度分别改进到了O(nlog2n+klog2n)和摊还时间O(nlog2n+klog2n).该改进可直接应用于欧几里得平面的瓶颈斯坦纳树2-近似算法.     

M-回路网络的中心选址

研究含边不交回路网络的中心选址问题,给出了一个求其最小直径支撑树的破圈算法,由此得到求其中心的O(mn)阶算法,这里m是网络中含回路的个数。     

广义树网络中的多端割

给定一个边赋权图和k个顶点(称为终端)的集合,多端割问题是要找到一个最小 权的边集,该边集使得每一个终端与其他所有的终端分离.对于一般图来说,当k为不小于3的常数时,这一问题是NP-难解的.对于广义树网络给出了这一问题的一个多项式时间精确算法.     

树网络上的最优有向连接问题

有向网络上的最优有向连接问题是寻求从若干起点到若干终点的连接方式,使连接费用为最小。已知此问题是NP一困难问题。目前的一个研究方向是探讨存在多项式时间算法的特殊情形。本文研究了这样的特殊情形：树网络上所有起点处于同一条路上,建立了多项式时间算法。     

双环网络G(N;1,s)等价生成树

提出研究双环网络G(N;1,s)的抽象模型--等价生成树,并对其性质进行了研究,给出了双环网络G(N;1,s)等价生成树的构造方法.提出基于等价生成树G(N;1,s)的直径d(N;1,s)的求解算法,并给出了其显式公式,利用C语言编程对等价生成树的结构模型进行了仿真.结果表明:算法不仅可在有限时间内求出G(N;1,s)的所有直径,而且可方便地得到源结点到所有其他结点的最短路径.算法的复杂度为O(N).     

门槛图中的一些优化问题

门槛图是一类结构比较特殊的图,本文给出了它的一个标准表示形式,并在此基础上建立了一个好的算法来构造它的中心树。利用中心树的结构性质,用多项式时间算法解决了这类图的一些优化问题,包括最大团、最大独立子集问题,染色问题,最小边割集问题和哈密尔顿性问题。     

基于LINGO的最小支撑树问题的模型与解法

研究了图与网络领域中的一类经典问题——最小支撑树问题,分析其现有算法的不足,通过引入0-1变量和辅助变量,根据最小支撑树的本质属性,从两个角度建立了最小支撑树问题的整数规划模型,编写了与模型相对应的LINGO程序.实证分析验证了模型的正确性,比较了两种建模模式的优劣.     

最小支撑树的新算法

从树的等价定义出发,叙述并证明了一种不必考虑圈的求最小支撑树的算法.     

凸多边形最小面积四边形包围盒算法

针对凸多边形的最小面积四边形包围盒问题进行研究,通过数学推导证明,得出了凸多边形的最小面积四边形包围盒的四边都是多共点边,或三边是多共点边而另一边(单共点边)中点与凸多边形的一顶点重合等一系列结论.依据此结论设计了时间复杂度为O(n4)的算法,依据本算法可以构造出凸多边形面积最小的凸四边形包围盒,而且其算法的复杂度仅与凸多边形的边数n相关,是多项式级的复杂度.运算实例表明了算法的正确性和有效性.     

容量型最小费用流逆问题的可行性研究

针对容量型最小费用流逆问题的可行性及相关优化进行研究,证明了判断容量型最小费用流逆问题是否可行可以在多项式时间内完成.如果容量型最小费用流逆问题不可行,即无论怎样修改容量的上界u和下界l,初始流f0都不能变为新网络的最小费用流.给出了两种调整初始流f0的算法,证明了通过最少修改初始流f0,可以使最小费用流逆问题变为可行.     

求解运筹学最小支撑树模型的一种新算法

为了简化对运筹学中最小支撑树模型编写简单计算机程序来实现求解,设计了一种新的简便算法----"节点列表判定法"。该算法是用节点来表述网络图的边,并从节点列表中找到了构成圈的特征结构,以此作为判定条件来确定网络图是否有圈存在。在最小支撑树模型的求解过程中,选择网络图中权数最小的边为支撑树的边。每选择一条边就判定一次,若判定有圈存在则放弃最后选择的边,反复选择边并判断,直到所有已选择的边都不构成圈且总边数等于点数-1,那么新确定的支撑树就是一个最小支撑树。这种新的算法已经Excel-BVA编制求解程序验证了其正确性、实用性和快捷性。     

Hamming距离下瓶颈约束最小支撑树反问题

讨论Hamming距离下瓶颈型约束最小支撑树反问题,给定的一个支撑树,修改给定网络边上的费用,使给定的支撑树成为最小支撑树且支撵树中边费用最大值不超过给定的常数,用瓶颈Ham-ming距离来衡量修改的权值,并给出瓶颈Hamming距离下的约束最小支撑树反问题定理的证明.     

2种限制性指派问题

提出了指派问题的2种推广模型:双限制性指派问题和缺省限制性指派问题,首先设计了双限制性指派问题2种多项式算法,随后设计出了缺省限制性指派问题的1种多项式算法,并且分别对以上算法的正确性和时间复杂性做出了相应的证明.