清华大学出版社 TSINGHUA UNIVERSITY PRESS 第9章近似算法 迄今为止,所有的NP完全问题都还没有多 项式时间算法。对于这类问题,通常可采取以 下几种解题策略。 (1)只对问题的特殊实例求解 (2)用动态规划法或分支限界法求解 3)用概率算法求解 (4)只求近似解 (5)用启发式方法求解 本章主要讨论解NP完全问题的近似算法。 22 第9章 近似算法 迄今为止，所有的NP完全问题都还没有多 项式时间算法。对于这类问题，通常可采取以 下几种解题策略。 (1)只对问题的特殊实例求解 (2)用动态规划法或分支限界法求解 (3)用概率算法求解 (4)只求近似解 (5)用启发式方法求解 本章主要讨论解NP完全问题的近似算法