若干情形下最大支撑树部分反问题的研究

摘要

组合优化反问题是指通过改变组合优化问题的权函数，使得给定的一个可行解成为最优解并最小化权函数的改变量. 部分反问题是反问题的推广，是指给定组合优化问题的一个部分解(包含在某些可行解中)，通过改变权函数，使得存在一个包含部分解的最优解并最小化权函数的改变量. 支撑树作为一个经典的组合优化问题，其反问题和部分反问题都得到了广泛的研究. 本文主要就最大支撑树的部分反问题(PIMST)进行了研究. 本文分为六章. 第一章介绍了PIMST的背景、基本概念和记号，并罗列了本文得到的主要结论. 第二章主要研究了带容量限制的PIMST问题（CPIMST）最优解的性质，并从基本圈和基本割两方面给出了判定给定权函数是否可行的充要条件. 第三章主要研究了l∞-范数下的CPIMST问题. 利用l∞-范数下CPIMST问题最优解的性质，找出问题最优值的可选范围，结合二分搜索法给出了求解该问题的计算复杂度为O(mnlog n)的精确算法，并将算法推广至赋权l∞-范数下CPIMST问题. 第四章主要研究了部分解只有一条边时的CPIMST问题. 通过若干次固定ω′(e0)的取值，将问题转化为若干个CPIMST?问题并找出每个问题的最优解. 进一步，在这些解中选取最优的一个作为CPIMST问题的近似解; 最后，根据范数的连续性得到了近似解误差上界为(m?p/??)p/1?(σ?ω(e0))，其中σ是e0的取值上界，??为转化的CPIMST?问题的个数. 第五章主要研究了部分解包含k条边时的CPIMST?问题. 首先，将问题分解为若干个部分解只包含一条边的CPIMST?子问题; 然后，利用已有的算法得到每个子问题的最优解; 最后，通过这些最优解得到了原问题的可行解，并证明了近似比的上界为kp/1.进一步，将得到的结果推广至CPIMST问题. 第六章总结了本文的主要结果并展望了后续的研究工作.

目录

第一个书签之前