NP完全問題

今天我們來聊一下關於NP完全問題的相關知識，初看到這個名詞，其實我也是不懂是什麼東西，但是百度百科給出了這樣的解釋：NP完全問題（NP-C問題），是

世界七大數學難題之一。 NP的英文全稱是Non-deterministic Polynomial的問題，即多項式複雜程度的非確定性問題。簡單的寫法是 NP=P？，問題就在這個問號上，到底是NP等於P，還是NP不等於P。是不是看完也不知道在說什麼？那我們就開門見山，NP完全問題的簡單定義是，以難解著稱的問題，如旅行商問題和集合覆蓋問題。很多非常 聰明的人都認為，根本不可能編寫出可快速解決這些問題的演算法。

旅行商問題求解

在旅行商這個問題種，有一位旅行商需要前往5個不同的城市。如下圖所示

旅行城市

如果需要找出前往這5個城市的最短路徑，為此，必須計算每條可能的路徑

路徑規劃

那麼前往5個城市時，可能的路徑有多少條呢？

我們假設現在只有兩個城市（馬林和舊金山），那麼可供我們選擇的路線只有兩條：1、馬林——-舊金山 2、舊金山——-馬林

那麼你可能會有這麼一個疑問？這兩條路線不相同嗎？不一定，如果有個城市是單行的話，那麼就無法按原路返回，就需要找到一個岔路然後回去，因此，這兩條路線不一定相同。

如果我們再增加一個城市伯克利，此時可能的路線會有多少條呢？

應該是有6條，當從伯克利出發時，從伯克利到馬林再到舊金山這是一條路線，從伯克利到舊金山到馬林這是另外一條路線。同理當從馬林出發時又是兩條路線，舊金山出發時又是兩條路線，因此當涉及3個城市時，可能的路線有6條。

路徑規劃

分析完3個城市的路線規劃時，此時再增加一個城市——弗裡蒙特，假設從弗裡蒙特出發，有6條可能的路線，為什麼？其實就是上面的路線規劃中加了起點城市弗裡蒙特，但是我們可以選擇弗裡蒙特作為起點，相對應其他三個城市也可以作為我們的起點城市，同樣會獲得6條路線規劃，這樣算下來就會有4x6=24條路線。

路徑規劃

由此我們可以得出這樣一個規律：每增加一個城市，需要計算的路線數都將增加

規律

當涉及6個城市時，可能的路線就有720條，7個城市就有5040條，8個城市就有40320條，由歸納法可知當有n個城市時，那麼路線就有n！條。因此，一旦涉及的城市多，找出旅行商問題的正確解就顯得尤為困難。；旅行商問題需要計算所有的解，並從中選出最短的那個，屬於NP完全問題。

還記得上次我們學習貪婪演算法中提到的近似求解的概念，那麼對於這麼多路線規劃，我們找到一條相對較短的路線才是解決這個問題的最優解。解決旅行商問題時，我們可以隨便選擇出發城市，然後每次選擇要去的下一個城市，但這個城市都選擇的是下一個沒去過的且最近的城市，假設旅行商從馬林出發：

近似最優解

總旅程為71公里，當然了這條路徑可能不是

最短

的，但也相對短了

如何判斷NP完全問題

元素較少時演算法的執行速度非常快，但隨著元素數量的增加，速度會變得非常慢。

涉及“所有組合”的問題通常是NP完全問題。

不能將問題分成小問題，必須考慮各種可能的情況。這可能是NP完全問題。

如果問題涉及序列（如旅行商問題中的城市序列）且難以解決，它可能就是NP完全問題。

如果問題涉及集合（如廣播臺集合）且難以解決，它可能就是NP完全問題。

如果問題可轉換為集合覆蓋問題或旅行商問題，那它肯定是NP完全問題。