組合最最佳化方法

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

組合最最佳化方法(combinatorial optimizationmethod )求解組合最最佳化問題的方法一般地，對於不同類的組合最最佳化問題，對應著不同的求解方法.判定一個組合最最佳化方法好壞的主要標準是運算次數.用n表示某一組合最最佳化問題的規模p(n)表示在對方法影響最壞的情況下所需的運算次數.若p(n)是n的多項式函式，則稱該方法是多項式算法.凡能用多項式算法求解的問題都稱為P問題.有一類問題稱為NP完全問題，若這類組合最最佳化問題具有如下特點:

1.它們都未找到多項式算法.

2.如果對其中某一問題存在多項式算法，那么此類中的所有問題也都有多項式算法.

已發現有成千的組合最最佳化問題屬於NP完成問題.為求解該類中的問題，人們往往採用“啟發式”方法.這些方法一般地，不能保證求得問題的最優解，但常能得到較好的近似解.