組合最優化方法

組合最優化方法是求解組合最優化問題的方法。一般不同類的組合最優化問題對應着不同的求解方法。判定一個組合最優化方法好壞的主要標準是運算次數。用n表示某一組合最優化問題的規模。（PU）表示在對方法影響最壞的情況下所需的運算次數。若（PU）是n的多項式函數，則稱該方法是多項式算法。凡能用多項式算法求解的問題都稱為P完全問題，若這類組合最優化問題具有如下特點：（1）它們都未找到多項式算法；（2）如果對其中某一問題存在多項式算法，那麼此類中的所有問題也都有多項式算法。已發現有成千的組合最優化問題屬於NP完全問題。為求解該類中的問題，人們往往採用“啓發式”方法。這些方法一般地不能保證求得問題的最優解，但常能得到較好的近似解。 ^[1]