计算机算法设计与分析第3版王晓东__.ppt

1 第 9 章 NP 完全性理论与近似算法 2 ? 学习要点 ? 理解 RAM RASP 和图灵机计算模型 ? 理解非确定性图灵机的概念 ? 理解 P 类与 NP 类语言的概念 ? 理解 NP 完全问题的概念 ? 理解近似算法的性能比及多项式时间近似格式的概念 ? 通过范例学习 NP 完全问题的近似算法 ? 1 顶点覆盖问题 ? 2 旅行售货员问题 ? 3 集合覆盖问题 ? 4 子集和问题 3 9