最短Hamilton路徑與旅行商問題

• 前言
• 最短Hamilton路徑
• 旅行商問題

前言

發現很多篇博客都是要么直接貼代碼，要么就對dp式子進行解釋，沒有說為什么得到這個式子就很讓人感到無語，這可能就是為什么c站

最短Hamilton路徑

題目轉送門
題目意思是從0號點出發到n-1點的最短Hamilton路徑 ，我們利用集合的角度來對其進行分析

那么這個轉態的轉移需要滿足哪些條件呢

在當前的路徑的狀態中，i對應的位置需要為1，也就是當起的終點需要出現在路徑上。

對于中間節點k而言，由每一個點只能出現一次，因此我們去掉i之后對應的路徑的集合需要有節點k。

上面條件都滿足的話就可以有轉移式子：
$dp[i][j]=min(dp[i][j],dp[i?(1<<j)][k]+w[k][j]$

我們就以當外層循環都最后，也就是state轉態表示所以的點都經過一次后，第二層循環為n-1也就是題目所問的終點的時候，我們在枚舉k的時候也就是我們在考慮從哪一個點到終點比較好，如果我們選了一個點，那么這個點又會有同樣的子問題。

代碼：

#include<iostream> #include<stdio.h> #include<cstring> using namespace std;const int N = 20 ,M = 1<<20; int f[M][N] ,weight[N][N]; int n;int main(){scanf("%d",&n);for(int i=0;i<n;++i)for(int j = 0;j<n;++j)scanf("%d",&weight[i][j]);memset(f,0x3f,sizeof f);f[1][0] = 0;for(int i=0;i< 1<<n;++i)for(int j=0;j<n;++j)if(i>>j &1) // 集合中有jfor(int k = 0;k<n;++k)if(i-(1<<j)>>k & 1 ) //集合中有k，但沒有jf[i][j] = min(f[i][j],f[i-(1<<j)][k] + weight[k][j]);//i-(1<<j) 已經在if證明該位置存在了printf("%d\n",f[(1<<n)-1][n-1]);return 0; }

旅行商問題

為甚么我要將旅行商問題與Hamilton路徑寫在一起呢，旅行商問題抽象來就是一個起點任意而終點是自己的Hamilton路徑。
我們回想一下Hamilton路徑中，$dp[i][j]$數組的含義是：從0出現到終點j，且每一個點只走一次的集合i的最短路徑，那么我們在計算完Hamilton路徑后，我們只需要在原來的基礎上加上一條從終點到0的路徑，那么我們就可以構成了這個起點任意的旅行商問題了。
那么問題來了，可能有人會問為什么是連到0呢不可以是別的點嘛，
首先我們知道如果我們在起點任意選擇的話那么因為么每一個點最能走一次，那么終點肯定不是這個點，那么我們就可以指定最后的點是0(最后加上0到出發點的距離)因為起點的第一個點是任意的，最終我們得到的還是在任意可能中的一個最小值。

那么我們對于這個思路翻過來想，我們可以讓指向出發點的點任意，那么出發點指向的第一個點就不會是任意的(可以回想一下概率論中學到的)，因此我們即可以將出發點的第一個點定會0，我們那么這一部分我們就可以轉化為Hamilton路徑了。以下是代碼

代碼：

#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 16, M = 1 << N, INF = 0x3f3f3f3f; int n, m, g[N][N]; int f[M][N] ;int main() {cin >> n >> m;memset(g, 0x3f, sizeof g );memset(f, 0x3f, sizeof f);while (m--) {int a, b, c;cin >> a >> b >> c;g[a][b] = c;}for (int i = 0 ; i < n ; ++i)g[i][i] = 0;f[1][0] = 0;for (int i = 0 ; i < 1 << n ; ++i)for (int j = 0 ; j < n ; ++j)if (i >> j & 1) {for (int k = 0 ; k < n ; ++k)if ((i - (1 << j)) >> k & 1)f[i][j] = min(f[i][j], f[i - (1 << j)][k] + g[k][j]);}int res = INF;for (int i = 0 ; i < n ; ++i)res = min(res, f[(1 << n) - 1][i] + g[i][0]);if (res == INF)cout << -1 << endl;elsecout << res << endl;return 0; }

總結

以上是生活随笔為你收集整理的最短Hamilton路径与旅行商问题联系与解决的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。