《复杂性理论》第8章.pdf

《计算复杂性理论》 近似算法 2013-12 陈卫东 chenwd@scnu.edu.cn 华南师范大学计算机学院 2013/12/6 NP-hard问题的求解技术  如何对付NP-hard 问题？  许多问题一般无需求最优解，求近似最优解即可  NP-hard 问题性质：集中研究某些典型NP-hard 问题好算法  人类社会的丰富经验可以借鉴  大自然中的一些现象可以借鉴 W.D.Chen South China Normal University 1 NP-hard问题的求解技术  典型求解技术  精确求解技术（Exact Algorithms ）  近似求解技术（Approximate Algorithms ）  启发式求解技术（Heuristics ） W.D.Chen South China Normal University 2 NP-hard问题的求解技术  精确求解技术（Exact Algorithms ） 分治法、动态规划、分枝限界、回溯法等各种有哪些信誉好的足球投注网站算 法…… 精确求解但速度慢，适合于解决中小规模的问题实例 如何评价这类算法？ W.D.Chen South China Normal University 3 NP-hard问题的求解技术  近似求解技术（Approximate Algorithms ） 组合方法、随机方法、松弛方法… 多项式时间运行、近似求解，能快速得到质量有保障的解. 如何评价这类算法？ 性能的理论分析一般需要较高技巧！ W.D.Chen South China Normal University 4 NP-hard问题的求解技术  启发式求解技术（Heuristics ） 面向问题的启发式算法（problem-specific heuristics ）： 贪心算法、拟人拟物算法、…… 通用启发式算法（meta-heuristics ）： 演化算法、遗传算法、模拟退火、禁忌有哪些信誉好的足球投注网站、…… 快但不够精确。可求解较大规模问题实例，所得解常可满足于实 际应用需要。 如何评价这类算法？ W.D.Chen South China Normal University 5 提纲  近似算法的相关概念  近似度的度量  近似问题相关的问题复杂类  典型问题的近似算法举例  Vertex-Cover 问题  Bin Packing问题  欧几里德TSP 问题  Max-3-SAT问题  两机调度问题  Knapsack问题  TSP 问题 W.D.Chen South China Normal University 6 提纲  证明问题难近似的技术  间隙技术（Gap Technique ）  设计近似算法的方法  组合方法  随机方法  松弛方法 W.D.Chen South China Normal University 7 近似算法的相关概念  近似度的度量 1．几个概念 (1) 最优化问题（目标函数、约束条件）