多項式時間逼近規劃

多項式時間近似方案

我們可以為 NP 完全問題，例如 0-1 揹包問題或子集和問題，找到一些多項式時間的解決方案。這些問題在現實世界中非常普遍，因此必定有一些方法可以解決這些問題。

多項式時間近似方案 (PTAS) 是一種針對最佳化問題的演算法近似型別。對於 0-1 揹包問題，存在偽多項式解，但當值很大時，該解不可行。然後我們需要一個 PTAS 解決方案。

一些 NP 完全問題，例如圖著色、K 中心問題等，沒有已知的多項式時間解決方案。PTAS 用於逼近演算法。這些演算法取引數 ε> 0，並且為了逼近，我們將最小化 (1 + ε) 和最大化 (1 - ε)。

示例

例如，如果我們選擇一個最小化問題並取 ε = 0.5，那麼使用 PTAS 的解決方案几乎是 1.5。因此，執行時間一定是關於 n 的多項式，但它可以是關於 ε 的指數。

更新於：2020-06-17

837 次瀏覽

開啟 職業生涯

完成課程後獲得認證

開始
廣告