text: 在計算機科學領域，多項式時間近似演算法的近似演算法。PTAS使用一個大於0的引數 ε，產生一個對於最小化問題能在 1 + ε 倍最優解內的解決方案。例如，對於歐幾里得旅行商問題，現有的最好PTAS 將產生一個長度最多為 (1 + ε) "L" 的解，其中"L"是最短行程的長度。 ε的大小越小，PTAS的近似效能比越靠近1，也即說明這個PTAS的計算結果越接近最優解。對於一個固定大小的ε，PTAS 的執行時間必須是，但對於不同的 ε，可以是不同的。時間複雜度為"O"("n"1/ε) 甚至"O"("n"exp(1/ε)) 的演算法同樣屬於 PTAS。
metadata.dataset: erhwenkuo/wikipedia-zhtw
metadata.title: 多項式時間近似演算法
metadata.url: https://zh.wikipedia.org/wiki?curid=7897304