跳至內容

精確算法

維基百科,自由的百科全書

計算機科學運籌學領域,精確算法是指可以求出問題準確最佳解的算法,與近似算法相對應。除非能夠對P/NP問題進行論證,否則NP困難問題很難保證在最壞情況下找到多項式時間的算法。不過儘管如此,目前人們已經對底數較小的指數時間精確算法進行了廣泛的研究。[1][2]

另見

參考文獻

  1. ^ Fomin, Fedor V.; Kaski, Petteri, Exact Exponential Algorithms, Communications of the ACM, March 2013, 56 (3): 80–88 [2023-04-13], doi:10.1145/2428556.2428575, (原始內容存檔於2013-03-02) .
  2. ^ Fomin, Fedor V.; Kratsch, Dieter. Exact Exponential Algorithms有限度免費查閱,超限則需付費訂閱. Springer. 2010: 203. ISBN 978-3-642-16532-0.