最小度生成树的一种近似算法

最小度生成树问题是一个NP难问题.本文给出了求最小度生成树的一种近似算法,这种算法得到的生成树的度数比最优解至多大1.     

三种新变形的全一问题

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

(m,n,k)指派问题的最小费用流模型及其算法

构造(m,n,k)指派问题的最小费用流模型,并将基于对偶原理的最小费用流的允许边算法求解该模型,提出求解(m,n,k)指派问题的一种算法.算法直接在其对应的网络中保持互补松弛条件不变,通过调整节点势以扩大允许网络从而寻求增广链并进行流量增广,直至在网络中得到流量为k的最小费用流,此时非O流边对应(m,n,k)指派问题的最优解.给出了(m,n,k)指派问题的最优解及多重最优解的重要性质,数值试验表明算法有效可行.     

基于模拟植物生长算法构造Steiner最优树问题研究

Steiner最优树问题是指对于给定区域内的点集,通过引入Steiner点集将区域中的点连接并保证连通的网络达到最小.该问题已成为经典的优化组合问题之一.提出一种基于模拟植物生长算法生成Steiner最优树的连通算法来实现网络连通.通过对实例的实验及结果分析,结果表明本算法不仅可获得最优解,精度和性能也有提高,明显优于其它方法.     

求解无线传感器网络路由问题的蚁群最优化算法及其收敛性

首先将无线传感器网络的路由问题转化成求解最小Steiner树问题,然后给出了求解无线传感器网络路由的蚁群优化算法,并对算法的收敛性进行了证明．最后对找到最优解后信息素值的变化进行了分析．即在限制信息素取值的条件下,当迭代次数充分大时,该算法能以任意接近于1的概率找到最优解,并且当最优解找到后,最优树边上的信息素单调增加,而最优解以外边上的信息素在有限步达到最小值．     

时变挥发率条件下求解Steiner树蚁群优化算法的收敛性

蚁群优化算法是最近提出的求解复杂组合优化问题的启发式算法.在蚁群优化算法中,信息素的更新规则直接影响着算法性能,固定挥发率条件下,虽然也能得到求解Steinei树蚁群优化算法的收敛性结果,但算法的探优能力差,易于陷入局部最优.本文在设计求解最小Steiner树蚁群优化算法时,采用了动态更新信息索挥发率的方法,并给出了时变挥发率条件下算法的收敛性证明.具体的,在时变挥发率条件下,当迭代次数充分大时,该算法能以概率1找到最优解.另外,在动态更新信息素下界的条件下,也能得到类似的收敛性结果.     

求解最小Steiner树的蚁群优化算法及其收敛性

最小Steiner树问题是NP难问题,它在通信网络等许多实际问题中有着广泛的应用．蚁群优化算法是最近提出的求解复杂组合优化问题的启发式算法．本文以无线传感器网络中的核心问题之一,路由问题为例,给出了求解最小Steiner树的蚁群优化算法的框架．把算法的迭代过程看作是离散时间的马尔科夫过程,证明了在一定的条件下,该算法所产生的解能以任意接近于1的概率收敛到路由问题的最优解．     

邮政运输网络中的邮路规划和邮车调度

根据不同情况的要求,采用多种算法来确定邮路规划.1)按照邮车不超载的要求,提出改进型贪心算法,得到符合条件的邮路规划,并结合实际,进一步提出改进方案.2)依据最小生成树理论,提出对各支局进行初步分组方法.同时,基于Floyd算法,提出了改进型TSP算法,并建立求解最小路径的模型,进而得到最经济的邮路规划.3)根据最佳Hamilton圈的理论,判断支局应归人的邮路,从而达到减少成本的目的.4)利用最短路覆盖中心算法,确定最合适的县局地址,使邮路总成本最小化.     

一种基于Split-findmin和Set-maxima的最小支撑树灵敏度分析方法

本文首先根据最小支撑树的截性质和圈性质给出了灵敏度分析的基本公式,然后基于现代图论算法中经典的Split—findmian数据结构介绍了树上边的灵敏度分析算法,最后将非树边的灵敏度分析转化为已有成熟的算法的Set—maxima问题进行处理.     

最小费用k度限制树对策

本在Glover—Klingman算法及最小费用支撑树对策的基础上，讨论了最小费用k度限制树对策问题．利用威胁、旁支付理论制订了两种规则，并利用优超、策略等价理论分别给出了在这两种规则下最小费用k度限制树对策核心中的解，从而证明了在这两种规则下其核心非空．