首页> 正文

若干NP-困难的组合最优化问题的近似算法

2020-11-29阅读(640)

若干NP-困难的组合最优化问题的近似算法

论文摘要

最优化理论是运筹学的经典内容之一,也是研究理论计算机科学尤其是计算复杂性理论的知识基础之一.简单说来,最优化就是寻求解决问题的一个最优方案,这个最优方案称为问题的最优解,当然,它首先应是问题的一个可行解.问题的所有可行解构成其可行域.因此,最优化也就是要从问题的可行域中找到一个最优解.组合最优化问题指的是可行域为有限集的离散最优化问题,其解法称为算法.在计算复杂性理论的框架下,通常认为,一个“好”算法的运行时间（称为其时间复杂性或计算复杂性）应是以关于问题的实例的输入规模的多项式函数为上界的,这样的算法称为多项式时间算法,也称为有效算法.根据输出的解是否精确,多项式时间算法又可分为精确算法和近似算法.人们发现,许多组合最优化问题是有多项式时间算法的,称之为P类问题,而把其余相当多的至今尚且无法确定是否存在多项式时间算法的组合最优化问题称为NP类问题.在NP类问题中有一类NP-困难问题,它们不存在多项式时间精确算法,除非P=NP.绝大多数组合最优化问题都是NP-困难的.于是,人们转而去设计近似算法以得到问题的近似解（非最优解的可行解）.近似算法的性能是用近似比来衡量的.以最小化问题为例,其近似算法的近似比定义为该算法输出的近似解的目标函数值与问题的最优值在最坏情形下的比.显然,近似比越小,近似算法越好.本文研究了一些NP-困难的组合最优化问题,并给出了其近似算法.下面,我们来简略地介绍一下这些问题,并给出我们的主要结果和创新点.论文的第一章介绍了研究的缘起和背景.我们对这些问题的关注和研究是源于它们在设施选址、网络设计和生物信息学等领域的重要应用.第二章和第三章是第一大块,给出了一种推广的设施选址问题的近似算法,并给出了与设施选址问题密切相关的费用分配问题的近似算法;第四章至第六章是第二大块,给出了若干Steiner网络设计问题的近似算法;第七章作为一个独立的块,给出了断点median问题的一个近似算法.作为运筹学中一个经典的组合最优化问题,设施选址问题要求我们选择地址来建造某种设施以便为客户提供服务.当然,在不同地址处建造设施的费用不同,不同设施为不同客户服务的费用也不同.那么,我们应如何为待建设的设施来选择地址,并指定已建设施与客户之间的服务关系,才能使每一客户都可由某一设施来提供服务,且建造费用和服务费用之和最小?这就是设施选址问题的主要研究内容.设施选址问题形式多样,其中最为简单的一种叫做度量的无容量的设施选址问题（UFLP）,它对同一设施服务的客户的数目不加限制,且要求服务费用满足三角形不等式.UFLP是NP-困难的,其目前已知的最好的近似算法的近似比为1.52.在第二章,我们研究了一种推广的设施选址问题（GFLP）,它不要求每一客户都必须由某一设施来提供服务,但对未由任一设施来提供服务的客户施加惩罚,并以“惩罚费用”的形式体现在目标函数中.根据问题的实际背景,惩罚费用以一个子模函数来表述.给定UFLP的一个基于线性规划技术的α-近似算法,我们给出了GFLP的一个（1+α）-近似算法.一旦设施选址问题得到了解决,那么,我们就会很自然地提出另一个问题:这一为给客户提供服务所需花费的总费用（建造费用与服务费用之和）应如何公平地由各客户来分摊呢?这就是我们在第三章所研究的费用分配问题,我们利用原始-对偶规划方法给出了其一个基于UFLP的算法的近似算法.网络设计问题是运筹学中的另一个经典问题,它意在从网络（边赋权的图）中找出一个满足某种条件的子图.Steiner树问题是最主要的Steiner网络设计问题之一,它是图论中著名的最小费用支撑树（MST）问题的拓展,它要求从网络中找出一个包含某一特定顶点子集（其中的顶点称为终端点）的最小费用子树.这一问题在超大规模集成电路（VLSI）设计、分布式数据库设计、光纤通信网络设计等方面有着重要的应用.Steiner树问题是NP-困难的,其目前已知的最好的近似算法的近似比为1.55.在第四章,我们主要研究了Steiner树-星问题,并给出了其一个3.582-近似算法.这里,Steiner树-星指的是仅以某些指定的顶点（称为Steiner点）为非叶顶点的Steiner树.此外,我们还研究了其它情形的一些Steiner问题,包括κ-MST问题、prize-collecting Steiner树问题和κ-Steiner树问题,并在问题转化的基础上给出了其近似算法.在第五章,我们研究了瓶颈Steiner网络设计问题,它要求从网络中找出一个满足某种瓶颈条件的Steiner树.针对有根和无根两种情形下的瓶颈Steiner网络设计问题,我们分别给出了其近似算法.在第六章,我们研究了Steiner树问题的两种推广的形式:分组Steiner问题和覆盖Steiner问题.这两个问题都要求从网络中找出一个Steiner树,但前者要求Steiner树要含有一系列“组”的至少指定数目的顶点,而后者则要求Steiner树要含有组的至少一个顶点.我们通过在不同图上的问题的转化给出了分组Steiner问题和覆盖Steiner问题的近似算法.特别地,我们研究了两个问题的一些特殊情形及其它相关问题,并给出了其近似算法.最后,在第七章,我们研究了来自于计算生物学领域的断点median问题,并就环形基因组和线形基因组两种情形分别给出了近似算法.

论文目录

  • 中文部分
  • 中文摘要
  • 英文摘要
  • 符号说明
  • 第一章 绪论
  • §1.1 动机与背景
  • §1.2 算法的基本概念
  • §1.3 论文概要
  • 第二章 推广的设施选址问题
  • §2.1 引言
  • §2.2 问题的陈述
  • §2.3 整数规划模型
  • §2.4 辅助的设施选址问题
  • §2.5 算法的设计与分析
  • §2.6 结束语
  • 第三章 费用分配问题
  • §3.1 引言
  • §3.2 线性规划模型
  • §3.3 算法
  • §3.4 结束语
  • 第四章 推广的Steiner树-星问题
  • §4.1 引言
  • §4.2 基于CFLP的算法
  • §4.2.1 度量的无容量的设施选址问题
  • §4.2.2 连通的设施选址问题
  • §4.3 基于UFLP的算法
  • §4.4 算法的分析
  • §4.5 其它相关的Steiner问题
  • §4.5.1 k-MST问题
  • §4.5.2 Prize-collecting Steiner树问题
  • §4.5.3 k-Steiner树问题
  • §4.6 结束语
  • 第五章 瓶颈Steiner网络设计问题
  • §5.1 引言
  • §5.1.1 问题的陈述
  • §5.1.2 背景
  • §5.2 基于GSP的算法
  • §5.3 算法
  • §5.3.1 预备知识
  • §5.3.2 有根情形的BSNDP的算法
  • §5.3.3 无根情形的BSNDP的算法
  • §5.4 结束语
  • 第六章 分组和覆盖Steiner问题
  • §6.1 引言
  • §6.1.1 问题的陈述
  • §6.1.2 假设
  • §6.2 从一般图到树
  • §6.3 从一般图到平面图
  • §6.4 USP与CSP的转化
  • §6.5 含退化组的GSP
  • §6.6 小组数的CSP
  • §6.7 一个相关问题
  • §6.8 结束语
  • 第七章 断点Median问题
  • §7.1 引言
  • §7.2 基因组的图论描述
  • §7.3 TSP的近似算法
  • §7.4 环形基因组情形的BMP
  • §7.4.1 将BMP转化为TSP
  • §7.4.2 近似算法
  • §7.5 线形基因组情形的BMP
  • §7.6 结束语
  • 参考文献
  • 致谢
  • 作者简介
  • 学位论文评阅及答辩情况表
  • 英文部分
  • 中文摘要
  • Abstract
  • Notation Index
  • Chapter 1.Introduction
  • §1.1 Motivation and background
  • §1.2 Some key concepts of algorithm
  • §1.3 Thesis outline
  • Chapter 2.Generalized Facility Location Problem
  • §2.1 Introduction
  • §2.2 Problem statement
  • §2.3 Integer program formulation
  • §2.4 Auxiliary facility location problem
  • §2.5 Algorithmic design and analysis
  • §2.6 Conclusion
  • Chapter 3.The Cost Allocation Problem
  • §3.1 Introduction
  • §3.2 Linear program formulation
  • §3.3 Algorithm
  • §3.4 Conclusion
  • Chapter 4.Generalized Steiner Tree-star Problem
  • §4.1 Introduction
  • §4.2 CFLP-based algorithm
  • §4.2.1 The metric uncapacitated facility location problem
  • §4.2.2 The connected facility location problem
  • §4.3 UFLP-based algorithm
  • §4.4 Algorithmic analysis
  • §4.5 Other related Steiner problems
  • §4.5.1 k-MST problem
  • §4.5.2 Prize-collecting Steiner tree problem
  • §4.5.3 k-Steiner tree problem
  • §4.6 Conclusion
  • Chapter 5.The Bottleneck Steiner Network Design Problem
  • §5.1 Introduction
  • §5.1.1 Problem statement
  • §5.1.2 Backgroud
  • §5.2 GSP-based algorithm
  • §5.3 Algorithm
  • §5.3.1 Preliminaries
  • §5.3.2 Algorithm for the rooted case of BSNDP
  • §5.3.3 Algorithm for the unrooted case of BSNDP
  • §5.4 Conclusion
  • Chapter 6.The Group and Covering Steiner Problems
  • §6.1 Introduction
  • §6.1.1 Problem statement
  • §6.1.2 Assumptions
  • §6.2 From general graphs to trees
  • §6.3 From general graphs to planar graphs
  • §6.4 Transformation between GSP and CSP
  • §6.5 GSP with degenerate groups
  • §6.6 CSP with small number of groups
  • §6.7 A related problem
  • §6.8 Conclusion
  • Chapter 7.The Breakpoint Median Problem
  • §7.1 Introduction
  • §7.2 Graph-theoretic representation of genomes
  • §7.3 Approximation algorithms for TSP
  • §7.4 BMP for the circular genomes
  • §7.4.1 Reduce BMP to TSP
  • §7.4.2 Approximation algorithm
  • §7.5 BMP for the linear genomes
  • §7.6 Conclusion
  • Bibliography
  • Acknowledgements
  • Curriculum Vitae
  • 学位论文评阅及答辩情况表

    • 相关论文文献

    • [1].重组人血管内皮抑制素联合NP化疗治疗中晚期非小细胞肺癌的临床效果[J]. 河南医学研究 2020(01)
    • [2].“吃+NP”动宾惯用语作为语用策略的适应性考察[J]. 昭通学院学报 2020(01)
    • [3].新型硝化抑制剂NP对黑土无机氮转化的影响[J]. 河北农业科学 2016(05)
    • [4].沙利度胺与NP方案联合治疗晚期非小细胞肺癌的疗效及对炎症因子和VEGF的影响[J]. 中国高等医学教育 2017(07)
    • [5].试析动后NP为数量宾语的把字句[J]. 外文研究 2015(02)
    • [6].维吾尔语名词短语(NP)结构[J]. 语文学刊 2013(24)
    • [7].经PICC泵入恩度联合NP方案治疗非小细胞肺癌的观察及护理[J]. 临床医药文献电子杂志 2016(38)
    • [8].香菇多糖联合NP方案对中晚期非小细胞肺癌患者的疗效及免疫功能的影响[J]. 中国生化药物杂志 2014(08)
    • [9].猪伪狂犬病病毒NP株的分离鉴定[J]. 动物医学进展 2015(03)
    • [10].NP完全问题研究及前景剖析[J]. 武汉工程大学学报 2015(10)
    • [11].乳腺癌术后辅助NP方案化疗的可行性分析[J]. 数理医药学杂志 2020(11)
    • [12].甘露聚糖肽注射液联合NP方案治疗中晚期非小细胞肺癌的疗效观察[J]. 中国医药导刊 2014(03)
    • [13].鸦胆子油乳注射液联合NP方案治疗中晚期肺癌的临床观察[J]. 当代医学 2014(02)
    • [14].谈一种特殊的“这/那不是NP嘛”结构反问句[J]. 学术交流 2013(02)
    • [15].“V_单+NP”语块的衍生途径及其制约因素[J]. 语言教学与研究 2012(04)
    • [16].艾迪注射液联合NP方案治疗非小细胞肺癌的临床观察[J]. 中国社区医师(医学专业) 2012(29)
    • [17].康艾注射液联合NP方案治疗非小细胞肺癌50例疗效观察[J]. 西部中医药 2012(09)
    • [18].NP方案序贯易瑞沙治疗晚期肺腺癌的临床观察[J]. 中国医药指南 2012(25)
    • [19].艾迪注射液联合NP方案治疗非小细胞肺癌的临床观察[J]. 中国社区医师(医学专业) 2012(32)
    • [20].NP方案加放疗治疗上腔静脉综合征80例临床分析[J]. 中国社区医师(医学专业) 2011(05)
    • [21].消癌平注射液联合NP方案治疗晚期NSCLC的临床观察[J]. 中国医药导报 2011(08)
    • [22].NP方案联合三维适形放疗治疗局部晚期非小细胞肺癌的疗效及安全性观察[J]. 中国当代医药 2011(13)
    • [23].精元康胶囊对NP方案化疗治疗非小细胞肺癌减毒作用的观察[J]. 中医学报 2010(03)
    • [24].NP方案序贯、同步放疗治疗中晚期非小细胞肺癌疗效的对比研究[J]. 中国社区医师(医学专业) 2010(35)
    • [25].氯尼达明联合NP方案治疗30例晚期非小细胞肺癌[J]. 中国肿瘤临床 2010(13)
    • [26].NP方案同步放疗治疗Ⅲ～Ⅳ期非小细胞肺癌[J]. 实用医技杂志 2009(01)
    • [27].消癌平注射液联合NP方案治疗晚期肺癌56例近期疗效观察[J]. 肿瘤基础与临床 2009(01)
    • [28].扶正解毒法配合NP化疗方案治疗晚期非小细胞肺癌临床研究[J]. 中国中医急症 2009(05)
    • [29].急性心肌梗死患者MMP-9、PⅢNP变化的临床分析[J]. 亚太传统医药 2009(06)
    • [30].华蟾素注射液联合NP方案治疗非小细胞肺癌的临床研究[J]. 医学理论与实践 2009(08)

    标签：;  ;  ;  ;  ;  ;  ;  ;  ;  

    若干NP-困难的组合最优化问题的近似算法
    下载Doc文档

    猜你喜欢

    © 2024 毕速过 版权所有 鄂ICP备12018319号-5