几类网络改进问题的算法研究

发布时间：2017-07-06 13:04

  本文关键词：几类网络改进问题的算法研究

  更多相关文章： 网络改进问题 1-maxian问题 最小支撑树问题 Hamming距离 多项式时间算法

【摘要】：网络改进问题是最优化领域的一个热门课题,近年来受到人们的广泛关注。网络改进问题是一种广义的逆最优化问题。逆最优化问题主要研究如何改变原问题中的参数,使得给定的可行解在新的参数下成为最优解,且总的改造费用尽可能少。人们根据不同的应用背景,分别研究了最短路的改进问题、逆最小费用流问题、逆最大流问题等,并在网络选址、运输流量均衡等众多领域取得了一些重要的理论和应用成果。网络选址问题是最优化领域的一类经典问题。网络选址问题主要研究如何在网络中将设施安排在最优的位置。但在实际网络中,公共设施可能已经存在,但由于区域环境的发展变化,未必仍满足位置最优的要求,而公共设施不能迁移或公共设施的迁移费用可能远远大于网络连接的改进费用,这时需要对网络进行改进,这就出现了网络选址问题的逆问题。本文从以下几个方面分别对l1模下和Hamming距离下特殊圈上的1-maxian逆问题以及只允许权重减小或权重增加的逆最小支撑树问题等进行了研究:第一,研究了l1模下特殊圈上的1-maxian逆问题。该问题主要研究如何在一定的预算下修改网络中边的长度,使得其他所有顶点到预先给定顶点的距离之和尽可能的大。首先我们对费用一致且边长及边长增量的上界均为1的特殊4-圈进行了研究,得到了该问题在任意预算下的最优解。然后将问题推广到特殊n-圈的情形,并得到其最优解的一般形式。第二,研究了Hamming距离下特殊圈上的1-maxian逆问题。首先,我们研究了费用一致且边长及边长增量的上界均为1时Hamming距离下4-圈的情形,得到了任意预算和距离之间关系的分段函数。然后将问题推广到特殊n-圈的情形,并得到其最优解的一般形式。第三,研究了只允许权重减小的逆最小支撑树问题。该问题研究如何尽可能少的减小图G中边的权重,使得在新的权重下预先给定的支撑树T成为图G的最小支撑树并且T中边的权重不能超过给定的界。我们得到了求解该问题的多项式时间算法,并通过实例验证了该算法的有效性。同时对只允许权重增加的逆最小支撑树问题也进行了研究,并得到了该问题的多项式时间算法。
【关键词】：网络改进问题 1-maxian问题 最小支撑树问题 Hamming距离 多项式时间算法
【学位授予单位】：中国计量学院
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 致谢5-6
• 摘要6-7
• Abstract7-12
• 1 绪论12-16
• 1.1 研究背景及意义12-13
• 1.2 国内外研究现状13-15
• 1.3 基本概念和术语15
• 1.4 本文内容和结构15-16
• 2 l_1模下特殊圈上的 1-maxian逆问题16-22
• 2.1 引言16
• 2.2 l_1模下特殊 4-圈上的 1-maxian逆问题16-18
• 2.2.1 问题描述16-17
• 2.2.2 问题求解17-18
• 2.3 l_1模下特殊n-圈情形的推广18-20
• 2.4 本章小结20-22
• 3 Hamming距离下特殊圈上的 1-maxian逆问题22-26
• 3.1 引言22
• 3.2 Hamming距离下特殊 4-圈上的 1-maxian逆问题22-24
• 3.2.1 问题描述22-23
• 3.2.2 问题求解23-24
• 3.3 Hamming距离下特殊n-圈情形的推广24
• 3.4 本章小结24-26
• 4 权重减小的逆最小支撑树问题26-32
• 4.1 引言26
• 4.2 问题描述26-27
• 4.3 权重减小的逆最小支撑树问题的算法及其分析27-29
• 4.3.1 问题的算法27
• 4.3.2 算法复杂性分析27-28
• 4.3.3 问题的实例28-29
• 4.4 权重增加的逆最小支撑树问题及算法29-31
• 4.4.1 问题的算法30
• 4.4.2 问题的实例30-31
• 4.5 本章小结31-32
• 5 结论与展望32-34
• 5.1 研究总结32
• 5.2 进一步需要开展的工作32-34
• 参考文献34-36
• 作者简历36

【相似文献】

中国期刊全文数据库 前10条

1 周丽,黄哲浩,王博,贺北方;求最小支撑树的方法探讨[J];郑州工业大学学报;2001年03期

2 李帮义,姚恩瑜;严格第k最小支撑树问题[J];系统工程理论与实践;2002年01期

3 连海峰,雷雪萍;最小支撑树的新算法[J];淮阴师范学院学报(自然科学版);2004年01期

4 王泽磊,张同全,李建平;关于K棵支撑树的2个问题[J];云南大学学报(自然科学版);2004年S1期

5 付铅生,李帮义;Pendants-median支撑树及其一个相关问题:复杂性和算法[J];高等学校计算数学学报;2004年02期

6 李淑君;唐恒永;;约束最小支撑树问题[J];沈阳师范大学学报(自然科学版);2006年01期

7 许进;;几类图的支撑树的计数公式[J];西北大学学报(自然科学版);1989年04期

8 周德镇;;最小支撑树简算法及其应用[J];管理现代化;1993年02期

9 朱娟萍;吴旭亭;杨子兰;;网络中支撑树的边扩容问题[J];云南大学学报(自然科学版);2013年05期

10 左霞;关秀翠;;一类特殊的极大+和支撑树在调整和权值下的逆问题[J];南京大学学报(数学半年刊);2013年02期

中国硕士学位论文全文数据库 前8条

1 王芳;网络中的均匀度问题和比值问题[D];国防科学技术大学;2004年

2 杨晓凌;最短路及最小支撑树的灵敏度分析[D];国防科学技术大学;2007年

3 徐何花;K_(1,5)-free图中的支撑树[D];华中师范大学;2012年

4 潘阳;关于图的最小线性布局的一些问题与结果[D];福州大学;2011年

5 王小燕;基于最小费用支撑树的合作对策问题[D];国防科学技术大学;2005年

6 朱芳;几类网络改进问题的算法研究[D];中国计量学院;2015年

7 张春明;图论在聚类分析中的应用[D];山东师范大学;2004年

8 王妍;图的在支撑树上作限制的L（p，1）-点标号及L（p，q）-边标号问题[D];山东师范大学;2012年

，

本文编号：526286