理解原因为什么我们不能总是为 NP 难问题找到精确解？+↗为 NP 难优化问题寻找精确解需要指数时间，如 O(2n)O(2^n)O(2n) 或 O(n!)O(n!)O(n!)，这对于大型输入在计算上是不可行的。适用条件：问题是 NP 难优化问题；寻求精确解YouTube近似算法0:36 – 0:49原站看这一段 ↗为 NP 难优化问题寻找精确解需要指数时间，如 O(2n)O(2^n)O(2n) 或 O(n!)O(n!)O(n!)，这对于大型输入在计算上是不可行的。适用条件：问题是 NP 难优化问题；寻求精确解阅读完整解释 →观看这一段 →YouTube近似算法0:36 – 0:49原站看这一段 ↗
理解原因为什么贪心匹配算法能保证顶点覆盖问题的 2-近似？+↗该算法选择了一组不相交的边 M。最优覆盖必须为 M 中的每条边包含至少一个顶点，因此最优成本 >= |M|。适用条件：算法选择任意边并添加两个端点，直到没有边剩余YouTube近似算法5:48 – 6:31原站看这一段 ↗该算法选择了一组不相交的边 M。最优覆盖必须为 M 中的每条边包含至少一个顶点，因此最优成本 >= |M|。适用条件：算法选择任意边并添加两个端点，直到没有边剩余阅读完整解释 →观看这一段 →YouTube近似算法5:48 – 6:31原站看这一段 ↗