论文部分内容阅读
网络构建问题是组合最优化领域中新出现的研究热点，它在网络设计、资源分配、工业管理及信息传播等问题中有着非常广泛的应用。在网络构建问题中，假定所有特定图的结构中的弧（边）都由具有给定长度L的材料连接而成，目标是使得连接特定图的结构中的弧（边）所使用的材料的总根数达到最小。 将网络构建问题与近年来发展起来的合作博弈结合在一起，就是本博士论文讨论的修正支撑树网络的合作博弈和修正的最短路合作博弈，本文分别给出了两类合作博弈的一个核心分配。最后讨论了限制性的带核元的划分问题。 全文分为六章内容: 第一章介绍了一些优化问题的研究背景、网络构建问题和合作博弈的研究现状以及本论文得到的主要研究成果。 第二章介绍了关于运筹学、组合最优化、图论、博弈论和相关优化问题及算法方面的一些相关预备知识。 第三章中介绍了两类网络的构建问题，推广了网络构建问题，研究了使用特殊材料的有向路构建问题和强连通支撑子图构建问题，得到了两个主要结论:(1)对有向路构建问题，设计了2-近似算法和渐进7/4-近似算法;(2)对强连通支撑子图构建问题，对任意的实数ε＞0，证明了有向路构建问题问题没有（2-ε）-近似算法，除非P=NP，随后设计了4-近似算法和渐进7/2-近似算法来解决这类问题。 第四章中介绍了修正支撑树网络的合作博弈问题，在构建网络的思想基础上，研究了支撑树的构建问题，并在此基础上引入合作博弈问题，将支撑树网络的构建问题看做合作博弈的费用分担问题，得到了三个结论:(1)为构建修正支撑树网络设计了一个2-近似算法;(2)证明了在所设计的算法MCMST的支持下，修正支撑树网络的合作博弈是单调的，核心非空;(3)为修正支撑树网络的合作博弈找到了一个核心分配。 第五章中介绍了修正的最短路合作博弈，从构建网络的思想出发，利用解决装箱问题的思路来考虑支撑树的构建问题，引入合作博弈思想，将最短路网络的构建问题看做合作博弈的费用分担问题，得到了三个结论:(1)为构建修正的最短路设计了一个2-近似算法;(2)证明了在所设计的算法SCMP的支持下，修正的最短路合作博弈是单调的，核心非空;(3)为修正的最短路合作博弈找到了一个核心分配。 第六章中介绍了限制的带核元划分问题，即将一个整数集合划分为两个子集，使得两个核元分别在不同的子集里且每个子集至多包含k个元素，目标使两个子集中元素之和的最小者达尽可能大。对一般的正整数k，给出了一个全多项式时间近似方案。当k=n+1时，给出了线性时间内的多项式时间近似方案和全多项式时间近似方案。 最后总结了上述工作，并对未来工作进行了展望。