关于K棵支撑树的2个问题

给定一个(有向)连通图G=(V，E)，寻找k棵支撑树(边可以重复)，满足树中的边在k棵树中出现的次数不超过其容量，考虑2个问题：①k棵支撑树的费用之和尽可能小；②k棵支撑树中费用最大的尽可能小,给出了问题①的一个最优算法，同时应用该算法，问题②是是近似的。     

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

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

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

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

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

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

最小度生成树的最大度算法

最小度生成树问题是一个NP难问题.给出了求最小度生成树的一个直观近似算法:找到图G的最大度,从其所在的基本圈上删掉1条与其关联的边,如此循环,直到图G的最大度不在任何基本圈上,如还有其它基本圈,删掉圈上的1条边,得到1棵生成树.这种算法得到的生成树的最大度数比最优解的度数至多大1.     

交通网络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的边数和顶点数。最后通过算例给出了算法的具体执行过程,同时验证了其可行性。     

一类度约束最小生成树问题的Dijkstra算法

度约束最小生成树问题是网络设计和优化中的一个NP难题。结合该问题的特征,基于Dijkstra算法的基本思想,提出了一种求解网络G关于指定节点的最大度最小生成树的新算法。该算法在保证指定节点最大度的前提下,每次通过选取剩余边中权最小的边加入当前网络,最终得到网络G关于指定节点的最大度最小生成树。同时对算法的复杂度进行了分析。最后通过与其他算法的仿真比较和算例,表明了新算法的有效性。     

奖励收集顶点覆盖问题的一个2-近似算法

给定图G、点赋权函数c和边惩罚费用w,对于图中任一顶点子集FV,F的权重可定义为其包含的顶点权重之和加上图G中未被其覆盖的边的费用之和。如何寻找一个权重最小的顶点子集F是近年来研究者广泛关注的问题之一。这一问题被称作奖励收集顶点覆盖问题。本文采用迭代松弛方法给出了这一问题的一个近似算法,并证明了该算法的近似度为2。     

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

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

网络中支撑树的边扩容问题

受多种网络改进模型的启发,作者研究了网络中支撑树的边扩容问题(GECAT).证明了GECAT问题和限制性最小支撑树问题是多项式等价的,从而说明GECAT是NP-难的.由GECAT问题到限制性最小支撑树问题的等价归约构造方式,得到一个多项式时间近似方法(PTAS).接下来,对GECAT问题的2种特殊形式做了研究并分别给出了强多项式时间算法:支撑树上需扩容边的数目最少问题和最小支撑树所需的扩容费用最少问题.对于前者,采用了T-交换算法,而后者则采用了字典序法.     

定向天线无线网络中的路由与信道分配方法

拓扑控制是采用定向天线的无线网络中的关键问题,定向天线无线网络中的拓扑控制、路由和信道分配是NP难问题。为了解决这个问题,提出了一个称为Ant-TRACE的高效蚂蚁算法。给定一个无线网络的信号可达图,Ant-TRACE可找到一个平衡的度约束最小生成树,有效地解决了拓扑和路由问题,基于已有的拓扑可有效地选择信道分配策略以最小化相邻链路干扰。基于NS3的仿真结果显示,Ant-TRACE在丢包率、时延和吞吐量上表现良好。     

求解软时间窗车辆路径问题的一种新方法

车辆路径问题属于组合优化领域中的NP–Hard问题.针对带软时间窗的车辆路径问题,提出了一种区域划分—路径优化的数学模型.首先结合最小支撑树算法能产生全局最优解的优点,将客户划分为若干个子区域.然后再结合贪婪算法简单迅速的特点,对每个子区域中的路径进行优化.实验结果表明,该算法收敛速度快、搜索成功率高.     

易腐农产品配送中心选址问题

如何将农产品新鲜、快速、低成本地有效配送,一直是配送中心选址需要关注的核心问题。结合易腐农产品特点,将总配送成本分解为运输成本及产品腐败成本两部分,运用G1法和熵值法,构建了包括各需求点的人口、社会、经济及建造成本4个因素在内的以总配送成本最小为目标的选址模型。借鉴经典NP问题中的Steiner点问题,将之前构建的以配送成本最小为目标的选址模型转化成配送中心到各个需求点总距离之和最小的问题。由于此问题属于典型的NP问题,所以文中选用模拟植物生长算法对此问题进行求解,为了使初始生长点更加合理的分布,引入了谢尔宾斯基地毯的原理对算法进行改进,有效地提高了算法的效率。最后以江苏宜兴市为例进行了实证分析,为相关部门决策提供借鉴。     

平行机上一种带拒绝费用的排序问题研究

主要研究了一种平行机上的排序问题。目标函数是使总完工时间最小但不能超过总拒绝费用的阀值。提出了该问题是NP一难的证明。针对该排序问题给出了伪多项式时间的动态规划算法且设计出了FPTAS。     

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

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

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

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

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

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

CLSP问题的分枝定价算法

提出了一种新的算法 分枝定价(Branch and Price)算法解经典CLSP,带有能力约束的单级多项动态批量问题(Thecapacitatedsingle level,multi item,dynamiclot sizingproblem)·CLSP问题有广泛工业背景,而且已被证明为NP Hard问题,它的目标是最小化总的装设(set up)费用和库存费用之和在所考虑的时间范围(horizon)内,并且满足给定约束条件·分枝定价算法是一种广义分枝定界(branch and bound)算法,它允许应用列生成(columngeneration)过程于整个分枝定界树·详细描述了该算法的实现,...     

树的费用全染色的近似算法

给定无向简单图G=(V,E)与颜色集C，并且对C中的每一种颜色c设定一个费用值w(c)∈R⁺.全染色是给出图的一个可行染色使得相关联的边和点、相邻的点或边都染不同的颜色.定义了费用全染色问题，即求解最优的全染色f，使得染色费用和最小，对于树图T，给出了一个2-近似算法，该算法的运行时间为O(nΔ²).     

基于基因次序的基因组问距离的计算

给出了计算两个具有相同内容、不同次序的基因组之间距离的算法.给定一组内容相同、次序不同的基因组,构造一个完全图,寻找一个基因组使得它与给定的各个基因组之间距离的累加和达到最小,这个问题可以转化为偈P问题.利用最小生成树方法找到一个中心基因组,接下来构造断点图,最后利用断点图来计算集合中的每一个基因组和中心基因组之间的距离.