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

发布时间：2025-07-19 01:51

　　组合优化反问题是指通过改变组合优化问题的权函数,使得给定的一个可行解成为最优解并最小化权函数的改变量.部分反问题是反问题的推广,是指给定组合优化问题的一个部分解（包含在某些可行解中）,通过改变权函数,使得存在一个包含部分解的最优解并最小化权函数的改变量.支撑树作为一个经典的组合优化问题,其反问题和部分反问题都得到了广泛的研究.本文主要就最大支撑树的部分反问题（PIMST）进行了研究.本文分为六章.第一章介绍了PIMST的背景、基本概念和记号,并罗列了本文得到的主要结论.第二章主要研究了带容量限制的PIMST问题（CPIMST）最优解的性质,并从基本圈和基本割两方面给出了判定给定权函数是否可行的充要条件.第三章主要研究了l_∞-范数下的CPIMST问题.利用l_∞-范数下CPIMST问题最优解的性质,找出问题最优值的可选范围,结合二分搜索法给出了求解该问题的计算复杂度为O（mnlog n）的精确算法,并将算法推广至赋权l_∞-范数下CPIMST问题.第四章主要研究了部分解只有一条边时的CPIMST问题.通过若干次固定ω′（e

【文章页数】：38 页

【学位级别】：硕士

【文章目录】：
中文摘要
Abstract
第一章 引言
    1.1 背景
    1.2 PIMST问题的形式定义
    1.3 本文的结构与主要结果
第二章 CPIMST问题最优解的性质
第三章 l_∞-范数下CPIMST问题的强多项式时间算法
    3.1 l_∞-范数下CPIMST问题
    3.2 赋权l_∞-范数下CPIMST问题
第四章 部分解为一条边时CPIMST问题
    4.1 预备知识
    4.2 F={e₀=ab}下CPIMST问题
第五章 l_p-范数下CPIMST问题的近似解的算法
    5.1 CPIMST-问题的近似解
    5.2 CPIMST问题的近似解
第六章 总结与展望
    6.1 总结
    6.2 展望
参考文献
致谢



本文编号：4057793