平面连通网络构建及相关问题

来源 :云南大学 | 被引量 : 0次 | 上传用户:astanaZH
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文主要研究平面连通网络构建问题,k-Steiner树问题和限制性平面连通网络构建问题,三个问题的描述分别如下。给定一个设施集合F={f1,f2,,fl},一个客户端集合C={c1,c2,,cm},F中设施fi的开放费用为w(fi),设施的容量没有限制,任何两个设施之间没有直接的连接渠道,从设施fi到客户端cj的连接费用为dij,客户端cj到客户端ck之间的连接费用为djk。平面连通网络构建问题的描述是:选择一些设施进行开放,满足每个客户端可以直接或间接的连接到一个开放设施,其目标是使得网络构建费用达到最小,这里费用包含设施开放费用。限制性平面连通网络构建问题在平面连通网络构建问题的基础上增加限制条件,即每个设施开放费用都为w(f0),并要求设施开放总费用不超过b,这里b≥w(f0)。k-Steiner树问题则是在图上Steiner树问题的基础上,对选取Steiner点数量进行限制。本论文得到以下四个结果。(1)证明了平面连通网络构建问题可以转化为Steiner树问题,在权重不受三角不等式性质约束时,可以用IRGH((?))算法求得该问题的任何一个实例的1.598近似结果。(2)对于k-Steiner树问题,利用向终端点最小支撑树中以三元素集迭代的方式加入Steiner点,然后用贪婪的方式得到Steiner树,最后再对Steiner点进行限制,从而得到解决k-Steiner树问题的KSteiner算法,并证明该算法近似比为2,时间复杂度为O(n~4),同时也给出基于枚举思想的指数时间算法(称为ESteiner算法),时间复杂度为O(lkn~2),这里n指图G顶点的数量,l指图G中Steiner点的数量,k指对Steiner点限制的数量。(3)对于限制性平面连通网络构建问题,证明该问题可以转化到k-Steiner树问题,并对限制性平面连通网络构建问题的一个实例进行分析。(4)利用Python编写程序,实现KSteiner算法和ESteiner算法,并且通过模拟实验发现KSteiner算法执行效果很好。
其他文献
在当今大数据时代下,迁移学习方法作为在新业务标注数据不足时,利用旧有数据提高新业务模型的主流技术,在许多应用中发挥了重要作用。传统统计模型的理论和实证研究通常是在训练集与测试集分布相同的假设下进行的,即要求训练集与测试集的边际分布和条件分布相同,这在我们利用旧业务样本解决新业务问题时是很难满足的。例如在商业银行在小微企业贷款问题中,旧有业务是风险更小的抵押贷款,新业务为小微企业的信用贷款,往往新旧
学位
学位
学位
学位
学位
学位
学位
学位
学位
学位