資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學證明哈密頓路徑問題在理論計算機科學（TOC）中是NP完全的
哈密頓環是一個沿著圖G的n條邊的環路路徑，它訪問每個頂點一次並返回到其起始頂點。
示例
下面是一個哈密頓環路路徑的示例：
哈密頓環路路徑：1,2,8,7,6,5,4,3,1
旅行商問題是NP完全的
旅行商問題(TSP)有一個銷售員和一組城市。銷售員需要從某個城市出發，訪問每個城市一次，然後返回到同一個城市，即回到起始位置。這個問題的挑戰在於，旅行商希望最小化總行程長度。
證明
為了證明TSP是NP完全的，首先嚐試證明TSP屬於非確定性多項式(NP)類。
在TSP中，我們必須找到一個巡迴路線，並檢查該巡迴路線是否包含每個頂點一次。
然後，我們計算巡迴路線的邊的總成本。最後，我們檢查成本是否最小。這可以在多項式時間內完成。
因此，TSP屬於NP類。
接下來，我們必須證明TSP是NP難的。
為了證明這一點，一種方法是證明哈密頓圈問題 ≤p TSP（因為我們知道哈密頓圈問題是NP完全的）。
假設G = (V, E)是哈密頓圈問題的一個例項。
因此，構造了一個TSP例項。我們可以建立一個完全圖G' = (V, E')，其中
E′={(i,j):i,j∈Vandi≠j
Thus, the cost function is defined as follows:
t(i,j)= 0 if (i,j) ∈ E
=1 otherwise現在，假設在G中存在哈密頓圈H。G'中H的每條邊的成本為0，因為每條邊都屬於E。因此，H在G'中的成本為0。因此，如果圖G具有哈密頓圈，則圖G'具有成本為0的巡迴路線。
現在讓我們假設G'具有成本最多為0的巡迴路線H'。根據定義，E'中邊的成本為0和1。因此，由於H'的成本為0，每條邊的成本必須為0。我們最終得出結論，H'只包含E中的邊。
最終證明了：當且僅當G'具有成本最多為0的巡迴路線時，G才具有哈密頓圈。因此，TSP是NP完全的。
更新於：2021年6月14日
5K+ 次瀏覽
廣告