Open codershenghai opened 5 years ago
http://www.zhangshenghai.com/posts/63466/
目前，所有的NP完全问题都没有能够在多项式时间内求解的算法，我们通常可以采用以下几种解题策略： 只对问题的特殊实例求解 用动态规划法或分支限界法求解 用概率算法求解 只求近似解 用启发式方法求解 本节主要讨论的是解NP完全问题的近似算法。 近似算法的性能若一个最优化问题的最优值为$C^{OPT}$，求解该问题的一个近似算法的一个近似最优解相应的目标函数值为$C$，则将近似算法的性能比定义为：
http://www.zhangshenghai.com/posts/63466/
目前，所有的NP完全问题都没有能够在多项式时间内求解的算法，我们通常可以采用以下几种解题策略： 只对问题的特殊实例求解 用动态规划法或分支限界法求解 用概率算法求解 只求近似解 用启发式方法求解 本节主要讨论的是解NP完全问题的近似算法。 近似算法的性能若一个最优化问题的最优值为$C^{OPT}$，求解该问题的一个近似算法的一个近似最优解相应的目标函数值为$C$，则将近似算法的性能比定义为：