最小连通顶点覆盖问题的降阶回溯算法

本文从最小连通顶点覆盖问题的求解算法出发,提出一种基于该问题本身的数学性质的降阶回溯算法来求解。通过基于问题的数学性质来设计精确算法,不仅能够克服使用启发式算法求解该问题在一般情形下都无法求得最优解的缺点,也改善了该问题使用传统精确算法时最坏时间复杂度高的缺点。本文首先研究该问题的数学性质,部分数学性质可成批确定某些顶点在或不在最小连通顶点覆盖集中,从而降低该问题的规模,提高精确算法的求解速度。其次,在数学性质的基础上,设计出上下界子算法、降阶子算法、回溯子算法来求解该问题的最优解。最后,时间复杂度分析以及无线网络设计的实例分析表明,该算法不仅能求得该问题的最优解,且相对一般精确算法,本文算法的时间复杂度更低。     

最小权点覆盖问题的一个近似算法

在点、边赋权的简单图中,关于最小权点覆盖问题,以经典的最短路算法-Dijkstra算法为基础,提出了一个求解该问题的近似算法.首先,在给定的赋权图中任选一点作为初始点,并给出允许集及相关定义.然后,利用经典的最短路算法-Dijkstra算法,求出初始点到允许集中各顶点的最短路径,并按照一定的原则选择近似最小权点覆盖集.最后,通过算例阐释了算法的实现过程的合理性及有效性.     

三种新变形的全一问题

该文研究三种新变形的全一问题及最小全一问题. 原始的全一问题可被形象的称为顶点点亮顶点问题, 而这三类新问题则分别被称为顶点点亮边问题,边点亮顶点问题,边点亮边问题. 顶点点亮顶点问题已经得到了广泛的研究. 比如,解的存在性问题和求解的有效算法已经被解决,一般图上的最小顶点点亮顶点问题已经被证明是NP- 完备的,树、单圈图和双圈图上的最小顶点点亮顶点问题的线性时间最优算法也已被给出等. 该文对于顶点点亮边问题,证明一个图有解当且仅当它是二部图,因此只可能有两组解和最优解. 对于边点亮顶点问题,证明一个图有解当且仅当它包含偶数个顶点,并通过将其最优问题多项式变换成最小权的完美匹配问题,得出一般图上的最小边点亮顶点问题可在多项式时间内求解. 边点亮边问题可归约成线图上的顶点点亮顶点问题.     

最小顶点覆盖问题的加权分治算法

最小顶点覆盖问题是组合优化中经典NP-Hard问题之一,其在实际问题中有着广泛的应用。加权分治技术是算法设计和复杂性分析中的新技术,该技术主要用于对分支降阶的递归算法进行复杂性分析,其核心思想可以理解为依据问题不同的特征设置一组相应的权值,以求降低该算法最坏情况下的时间复杂度。本文依据加权分治技术设计出一个分支降阶递归算法来求解最小顶点覆盖问题,并通过加权分治技术分析得出该算法的时间复杂度为O(1.255ⁿ),优于常规分析下的时间复杂度O(1.325ⁿ) 。本文中的结果表明运用上述方法降低算法的时间复杂度是非常有效的。     

一种基于边交换的贪心算法求解md-MST问题

通过对最小度限制最小生成树(md-MST)问题性质进行分析,提出了一种基于边交换的贪心算法.算法先用贪心算法生成一棵生成树ST,然后对生成树ST经过边交换调整,得到满足问题约束条件的可行解,再对生成树ST进行进一步边交换优化,得到md-MST问题的最优解或接近最优解的近似解.实验证明,算法能在短对间内求出大规模顶点随机图的md-MST,是一种非常实用的求解md-MST问题的精确算法.     

一类树图的最短路的算法

本文研究了边点赋权图、顶点关于图的运输量及质心,利用比较两个相邻顶点的运输量的方法,得到了一个连通树图的顶点是质心的充要条件及质心个数不大于2的结果.同时给出了求质心及最小运输量的算法,其算法的时间复杂度为O(n2),有利于可建立树图模型的优化问题的求解.     

区间图上可带负权的2-中位选址问题

本文研究了区间图上可带负权的2-中位选址问题.根据目标函数的不同,可带负权的$p-$中位选址问题($p\geq 2$)可分为两类：即 MWD 和 WMD 模型;前者是所有顶点与服务该顶点的设施之间的最小权重距离之和,后者是所有顶点与相应设施之间的权重最小距离之和.在本篇论文中,我们讨论了区间图上可带负权2-中位选址问题的两类模型,并分别设计时间复杂度为$O(n^2)$的多项式时间算法.     

区间图上可带负权的2-中位选址问题（英文）

Abstract本文研究了区间图上可带负权的2-中位选址问题.根据目标函数的不同,可带负权的p-中位选址问题（p≥2）可分为两类：即MWD和WMD模型;前者是所有顶点与服务该顶点的设施之间的最小权重距离之和,后者是所有顶点与相应设施之间的权重最小距离之和.在本篇论文中,我们讨论了区间图上可带负权2-中位选址问题的两类模型,并分别设计时间复杂度为O（n~2）的多项式时间算法.     

求解最小点覆盖问题实例的计算成本的一种度量方法

最小点覆盖问题是NP难问题,传统的计算复杂性理论认为,当规模n较大时,问题是难计算的,但大量的实例表明,即使规模相同的实例,由于其结构的不同,求最优解时也会花费不同的计算时间,所以建立一种度量具体实例求解难度的方法是必要的.介绍了一种度量最小点覆盖问题任一实例求解所需计算成本的方法,度量方法是以计算时间复杂度为O~*(2.314~(k-vc~*)(G))的参数算法为参照的,参数算法可用来求解点覆盖问题的判定问题,在参数算法中,当参数k为常数时,点覆盖问题可在多项式时间内求解,当k表现为n的函数时,点覆盖问题的难解性就表现出来了,结合最小点覆盖问题的近似算法—线性规划松弛来估计每个实例对应的参数k的取值范围,可在多项式时间内实现对最小点覆盖问题实例的计算成本的预测.对于平面点覆盖问题,则以EPTAS算法为工具实现更精确的度量.     

最大顶点覆盖问题的一种近似算法

给出了求解最大顶点覆盖问题的一种近似算法,讨论了它的性能保证,利用P ipage技术,为最大顶点覆盖问题设计出了0.75-近似算法.     

关于图的最小覆盖算法

本文就数学建模课的教学过程中 ,在“图的方法建模”一章中 ,关于图的最小覆盖法提出启发式算法 .用书中所给方法推出一个反例 ,分析了其产生错误的原因 ;通过对图的最小覆盖的概念的理解、结合分析图的关联矩阵的特点 ,给出了图的最小覆盖的启发式算法 .     

一个求外平面图最小顶点赋权反馈点集的线性时间算法

若从一个图中去掉某些顶点后得到的导出子图是无圈图,则所去的那些顶点组成的集合就是原图的反馈点集.本文主要考虑外平面图中的反馈点集并给出了一个求外平面图最小顶点赋权反馈点集的线性时间算法.     

欧拉图的hyper-Wiener指标

ε_n表示n个顶点欧拉图的集合.通过对欧拉图hyper-Wiener指标性质的研究,刻画了ε_n中具有最小和最大hyper-Wiener指标的极图.     

指定根的最小树形图的一个算法

文[1]给出了求有向图的最小树形图的算法,[2]中给出了求有指定根的最小树形图的算法.本文采用了[1]和[2]中的收缩回路的方法,给出了求有指定根的最小树形图的一个算法.设有向图G=(X,U),其中X={x_1,x_2,…,x_n}是顶点的集合,     

最小加权费用树问题

本文在赋顶点权θ的无向网络中,建立了最小加权费用树问题的网络模型,对问题的复杂性给出了证明并给出了求解该问题的算法。     

正多边形顶点集上的斯坦纳最小树

众所周知,覆盖一给定点集A的最小树T是所谓的斯坦纳最小树,简记为SMT.T中的顶点集记为V(T),V(?)A,而S=V-T中的点即为斯坦纳点。SMT的构作及其基本性质可见文献[1]及[2]。1977年Garey和其他人证明了离散的斯坦纳问题是属NP-complete类,从而很少有希望找到SMT的有效算法了。故斯坦纳问题研究中的另一方     

基于模拟退火算法的最小一乘回归新算法

最小一乘准则由于其稳健性较好而在工程中得到广泛的应用,但求解最小一乘回归模型系数的算法往往过于复杂或只能用于样本和变量个数较少的情形.本文根据最小一乘的性质,把最小一乘问题变为组合优化问题,将模拟退火算法用在最小一乘模型的求解上,在后面的数值实验中取得了较好的效果。     

网络最小覆盖流问题

网络流理论中最基本的模型是最大流及最小费用流问题. 为研 究堵塞现象, 文献中出现了最小饱和流问题, 但它是NP-难的. 研究类似的最小覆盖流问题, 即求一流, 使每一条弧的流量达到一定的额定量, 而流的值为最小. 主要结果是给出多项式时间算法, 并应用于最小饱和流问题.     

网络的分区连接问题

本研究了最小支撑树问题的一个变形——分区连接问题，即对给定的赋权图及其中若干个顶点，求赋权图的权最小支撑森林，使得它的每一个分支恰包含唯一的指定顶点。本给出了该问题的一个时间复杂性为O(|V|^2）的算法。此外，还研究了与该问题的相关的另外三个问题。     

带区间数据的最小风险斯坦纳树问题

考虑了在带区间数据的不确定网络中, 最小风险和模型以及最小最大风险模型下的斯坦纳树问题. 它们推广了相应模型下的最短路问题和最小支撑树问题, 在网络设计中具有更加广泛的应用.我们分别给出了这两个模型下斯坦纳树问题的近似算法, 并对算法性能做了理论分析和证明. 结果显示我们的算法具有优良的常数逼近的性质, 能在多项式时间内算出令人满意的解.