在管理科学、计算机科学、分子物理学和生物学以及超大规模集成电路(VLSI)设计、代码设计、图象处理和电子工程等科技领域中,存在着大量组合优化问题。其中许多问题如货郎担问题、图着色问题、设备布局问题以及布线问题等,至今没有找到有效的多项式时间算法。这些问题已被证明是 NP 宪全问题。
用最优算法如线性规划求 NP 完全问题的最优解,需要问题规模的指数阶时间,在问题规模增大时,往往由于计算时间的限制而丧失可行性。用近似算法如贪心法求解 NP 完全问题,在多项式界的时间里,只能给出近似最优解。
本章介绍组合优化问题和计算复杂性理论的基本概念,并结合几个组合优化的 NP 完全问题实例,介绍其近似算法。 最后,在引入邻域结构概念的基础上,介绍一种通用的近似算法——局部搜索算法。