抄一段《算法導論》的文字你看:
許多具有實際意義的問題都是NP完全問題,但都非常重要,所以不能僅因為獲得其最優解的過程是難以駕馭的而放棄它們。如果一個問題是NP完全的,就不太可能找到一個能給出其準確解的多項式時間算法,但這並不意味著沒有希望了。解決NP完全問題至少有三種方法:第一,如果實際輸入的規模比較小,則用具有指數運行時間的算法來解決問題就很理想了;第二,或許能將一些重要的、多項式時間可解的特殊情況隔離出來;第三,仍有可能在多項式時間裏找到(最壞情況或平均情況)近似最優解(near-optimal solution)。在實踐中,近似最優解常常就足夠好了。能返回近似最優解的算法稱為近似算法(approximation algorithm)。