資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究證明旅行商問題是NP難的
旅行商問題（TSP）是一種解決方案，其中一名銷售人員必須從一個地方出發，依次訪問所有其他城市，然後返回其出發地。TSP 的目標是找到最短路徑。多項式時間難度稱為 NP 難，它定義了一類問題的特性。子集和問題是 NP 難問題的簡單示例。
NP-難 - 無法在多項式時間內解決的問題類別稱為 NP-難。
讓我們以五個城市為例，瞭解銷售人員如何以最短距離訪問每個城市。
在圖中的這兩個可能性中，我們更傾向於哪一個？
在這兩張圖中，圖 II 表示最短/最小距離路徑。在圖 I 中，當銷售人員從 Chennai（點 1）前往 Hyderabad（點 5）時，需要花費大量時間才能返回其出發地，並且總行程距離很長，即 (1 -> 2 -> 3 -> 4 -> 5 -> 1)，但在圖 II 的情況下，銷售人員直接到達點 3（孟買），這節省了時間，並且覆蓋了總的最小距離，即 (1 -> 3 -> 5 -> 1)。
我們能否找到 32 個城市問題的可能性？
可能性由(n-1)!/2 解決方案給出。
在 4 個城市問題的情況下，
我們有 (4-1)!/2 = 3!/2
因此，總共有 3 種覆蓋距離的可能性。
讓我們看看圖片，瞭解 4 個城市的可能性。
在 3 個城市問題的情況下，只有一種覆蓋距離的可能性。
現在，讓我們考慮 41 個城市的問題，從中我們可以理解 NP-難問題。
在 41 個城市的情況下，銷售人員訪問每個城市將有 40!/2 種解決方案。
如果銷售人員到達每個城市並找到最佳路線，則需要
40! / (2*106) 秒
或 40! / (2*106*24*60*60) 天
或 40! / 365*(2*106*24*60*60) 年 = 6.8 * 1013 倍，這超過了地球的壽命。因此，不可能找到所有可能的路線並獲得最優解，而這類問題稱為 NP-難。
結論
我們探討了 NP 難的旅行商問題的概念。我們看到了許多圖，這些圖簡單地給出了最小距離的含義並找到了最佳路線，但是當我們瞭解 NP 難問題時，我們觀察到這類問題無法在多項式時間內解決。所以，這就是 NP 難。
4K+ 閱讀量
