在管理科学、计算机科学、分子物理学和生物学以及超大规模集成电路（VLSI）设计、代码设计、图象处理和电子工程等科技领域中，存在着大量组合优化问题。其中许多问题如货郎担问题、图着色问题、设备布局问题以及布线问题等，至今没有找到有效的多项式时间算法。这些问题已被证明是 NP 宪全问题。
用最优算法如线性规划求 NP 完全问题的最优解，需要问题规模的指数阶时间，在问题规模增大时，往往由于计算时间的限制而丧失可行性。用近似算法如贪心法求解 NP 完全问题，在多项式界的时间里，只能给出近似最优解。
本章介绍组合优化问题和计算复杂性理论的基本概念，并结合几个组合优化的 NP 完全问题实例，介绍其近似算法。 最后，在引入邻域结构概念的基础上，介绍一种通用的近似算法——局部搜索算法。
2022-05-04 14:08:50
6.15MB
可扩展并行算法的设计与分析（李晓梅-国防工业出版社-2000）.pdf
2022-04-06 10:40:48
4.48MB
1