旅行售貨商問題

題目描述

一個國家有 n 個城市，每兩個城市之間都開設(shè)有航班，從城市 i 到城市 j 的航班價格為 cost[i, j] ，而且往、返航班的價格相同。
售貨商要從一個城市出發(fā)，途徑每個城市 1 次（且每個城市只能經(jīng)過 1 次），最終返回出發(fā)地，而且他的交通工具只有航班，請求出他旅行的最小開銷。

關(guān)于輸入

輸入的第 1 行是一個正整數(shù) n （3 <= n <= 15）
然后有 n 行，每行有 n 個正整數(shù)，構(gòu)成一個 n * n 的矩陣，矩陣的第 i 行第 j 列為城市 i 到城市 j 的航班價格。

關(guān)于輸出

輸出數(shù)據(jù)為一個正整數(shù) m，表示旅行售貨商的最小開銷

例子輸入

4
0 4 1 3
4 0 2 1
1 2 0 5
3 1 5 0

例子輸出

7

解題分析

對于這個問題，如果我們直接用遞歸回溯的辦法給n個城市進行全排列（類似于八皇后問題的方法），然后再計算每種排列下我們需要的開銷是多少，可以解決當(dāng)所給數(shù)組n比較小的時候，而這種算法的時間復(fù)雜度是n!，當(dāng)n增大時，算法所需要的時間會急劇增大，所以很容易就timeout了。我們需要想出另外的方法去解決本問題。

注意到，在題干描述之下，問題是對稱的，我們?nèi)我膺x取一個城市作為初始城市，然后去求這個的問題的最小開銷，結(jié)果是一樣的。例如，如果2 ---->0------>1----->3------>2是最小開銷（最短路程），那么，如果我們?nèi)绻x0作為出發(fā)點，0------>1----->3-------2----->0,顯然兩種情況答案一樣，故，我們不妨令城市0為我們的商人的出發(fā)點。

那，我們?nèi)绾味x動態(tài)規(guī)劃的dp數(shù)組呢？我們又如何存儲哪些城市已經(jīng)訪問過了，那些沒有？這里，我們引入一個重要的方法，二進制狀態(tài)壓縮。

我們用一個二進制數(shù)去保存城市訪問的狀態(tài)，例如，如果我們有4個城市，那么，初始的狀態(tài)就是0000，如果我們?nèi)ミ^了0城市，則狀態(tài)為0001，如果我們?nèi)ミ^了0城市和3城市，那狀態(tài)為1001，這樣，我們巧妙地存儲了去過的城市的狀態(tài)，結(jié)合位于算與(&)和或(|)，我們可以進一步的判斷并更新動態(tài)規(guī)劃的方程。

此程序使用深度優(yōu)先搜索（DFS）和動態(tài)歸劃（DP）的方法解決旅行售貨商問題（又稱旅行商問題TSP，traveling salesman problem）。

程序的整體思路是：
1. 從一個城市出發(fā)（設(shè)為0，且在其他城市中只能訪問每個城市一次），通過遍歷所有可能的旅行線路，找到花費最小的深度優(yōu)先搜索線路。
2. 然后在所有可能的旅行線路中選擇花費最小的線路，最終找到總的最小花費線路。

下面逐個詳解程序中的關(guān)鍵部分。

深度優(yōu)先搜索函數(shù)：`dfs(int mark, int pos)`

在這個函數(shù)中，參數(shù)`mark`為訪問過的城市的標(biāo)記，`pos`為當(dāng)前所在城市。
- 若`mark`等于`(1<<n)-1`，表示所有城市都已訪問過，返回`cost[pos][0]`（即從當(dāng)前城市返回出發(fā)城市的花費）。
- 若訪問過的城市路徑`dp[mark][pos]`已被計算過（不等于-1），直接返回已存儲的最小花費。
- 若城市`i`未被訪問過（即`mark & (1<<i)`結(jié)果為0），計算從當(dāng)前城市到城市`i`的花費+從城市`i`開始，訪問剩余未訪問城市的最小花費，其結(jié)果和當(dāng)前最小花費比較取小值，遍歷所有城市后得到`ans`，即從當(dāng)前城市開始最小花費。
- 將計算得到的`ans`存入`dp[mark][pos]`并返回。

主函數(shù)`main(void)`部分則是將旅行售貨商問題的初始條件接收（城市數(shù)，各城市間的花費），并初始化動態(tài)規(guī)劃矩陣`dp`，然后使用深度優(yōu)先搜索找到最低花費，最后輸出最低花費。

這個程序主要通過深度優(yōu)先搜索去遍歷每一種可能的線路，并通過動態(tài)規(guī)劃記憶已經(jīng)搜索過的線路，以此剪枝，降低復(fù)雜度。

在這個問題中，動態(tài)規(guī)劃數(shù)組dp用于存儲已經(jīng)計算過的結(jié)果，以減少重復(fù)計算。動態(tài)規(guī)劃在旅行售貨商問題中的任務(wù)是記憶化搜索的工具。

每一行的索引mark用于表示已經(jīng)訪問過的城市。具體來說，將mark按二進制翻譯后，如果某一位為1，表示對應(yīng)索引的城市已經(jīng)被訪問過；如果為0，表示還未訪問過。

每一列的索引pos表示當(dāng)前所在的城市。

dp[mark][pos]存放已經(jīng)訪問過標(biāo)記為mark的城市，并且當(dāng)前所在城市為pos的情況下，回到出發(fā)城市的最小開銷。這里的最小開銷包括了從當(dāng)前城市直接返回到出發(fā)城市的費用和未來會訪問到的其他所有城市的費用。

例如，令?n = 4，如果我們在第二個城市，已經(jīng)訪問過第二個和第三個城市（我們假設(shè)城市的索引從0開始），那么mark將為0110，轉(zhuǎn)換為十進制則為?6。這時dp[6][1]就表示從第二個城市出發(fā)，訪問除出發(fā)城市和已訪問過的城市（這里是城市1和城市2）以外的所有城市（這里是城市0和城市3），并最終回到出發(fā)城市的最小花費。

在運行的過程中，如果dp[mark][pos] 等于-1，表示這個值還沒有計算過，需要通過深度優(yōu)先搜索計算得出。如果dp[mark][pos]不等于-1，表示這個值已經(jīng)計算過，無需重新計算，直接用這個值即可，這是記憶化搜索的一種策略。

這個程序主要使用了兩種位運算：位與（&）和位或（|），來記錄和標(biāo)記已經(jīng)訪問過的城市。這是一種常用于處理狀態(tài)壓縮動態(tài)規(guī)劃的手段。

位與運算（&）：

位運算中的與運算主要用來判斷一個數(shù)的某一位是否為1。在程序中，mark & (1<<i)主要用來判斷第i個城市是否被訪問過。

給一個簡單例子，假設(shè)n = 4，已經(jīng)訪問過的城市是城市1和城市2，那么mark就是0110。我們想要知道城市3（從0開始計數(shù)）是否被訪問過，就可以用mark & (1<<3)進行計算：

0110 //mark
1000 //(1<<3)
---- 
0000 //結(jié)果，第3位為0，表示沒有訪問過

因此我們知道城市3沒有被訪問過。按照這種方法，我們就可以循環(huán)檢測是否visited每個城市。

位或運算（|）：

位運算的或運算主要用來將一個數(shù)的某一位設(shè)置為1。在程序中，(mark | (1<<i))用來標(biāo)記城市i已經(jīng)被訪問過。

給一個簡單例子，現(xiàn)在要標(biāo)記城市3已經(jīng)被訪問，那么就可以?(mark | (1<<3))進行計算，結(jié)果用來更新mark。

這個問題中，因為售貨商需要遍歷每一個城市并返回起點，所以我們需要對每個城市進行狀態(tài)的記錄，記錄哪些城市已經(jīng)遍歷過，哪些城市還未遍歷，這個就是我們的狀態(tài)。狀態(tài)的轉(zhuǎn)移則是從已經(jīng)訪問某些城市的情況下，轉(zhuǎn)移到訪問了更多城市的情況。

定義動態(tài)規(guī)劃的狀態(tài)dp[mark][pos]，表示已經(jīng)訪問過標(biāo)記為mark的城市，并且當(dāng)前所在城市為pos的情況下，回到出發(fā)城市（城市0）的最小花費。

那么，我們的動態(tài)規(guī)劃轉(zhuǎn)移方程就可以設(shè)計為如下形式：

dp[mark][pos] = min(dp[mark][pos], cost[pos][i] + dp[mark | (1<<i)][i])，當(dāng)i不在mark中。

解釋一下這個方程：

1. 對于狀態(tài)dp[mark][pos]，表示已經(jīng)訪問過mark表示的城市，并且當(dāng)前在pos城市的情況下，返回起始城市的最小費用。

2. 為了找到這個最小費用，我們需要遍歷所有未訪問過的城市i（i不在mark中）?？紤]從當(dāng)前城市pos走到未訪問過的城市i，然后的費用應(yīng)當(dāng)為cost[pos][i] + dp[mark | (1<<i)][i]。在這個式子中，cost[pos][i]表示從城市pos到城市i的費用，dp[mark | (1<<i)][i]表示訪問了城市i以及當(dāng)前mark所表示的所有城市，并且最后到達城市i后，返回起始城市的最小費用。

3. 在遍歷了所有的可能城市i后，就可以找到dp[mark][pos]的最小值，也就是說在已經(jīng)訪問過mark表示的城市，并且目前在pos城市的情況下，返回起始城市的最小費用。

這樣就得到了這個問題的動態(tài)規(guī)劃方程，只需要使用深度優(yōu)先搜索來遍歷所有的可能狀態(tài)，并用記憶化搜索來記錄中間結(jié)果，就可以找到問題的最優(yōu)解。

代碼實現(xiàn)

#include <stdio.h>
#define min(x,y) x<y?x:y
#define MAXN 16

int INF=1e9;
int n;
int dp[1<<MAXN][MAXN],cost[MAXN][MAXN];

int dfs(int mark,int pos){
    if(mark==(1<<n)-1){
        return cost[pos][0];
    }
    if(dp[mark][pos]!=-1){
        return dp[mark][pos];
    }
    int ans=INF;
    for(int i=0;i<n;i++){
        if((mark & (1<<i))==0){
            ans=min(ans,cost[pos][i]+dfs((mark | (1<<i)),i));
        }
    }
    return dp[mark][pos]=ans;
}

int main(void) { 
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            scanf(" %d",&cost[i][j]);
        }
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<n;j++){
            dp[i][j]=-1;
        }
    int result=dfs(1,0);
    printf("%d\n",result);
	return 0;
}

（c++版本）文章來源地址http://www.zghlxwxcb.cn/news/detail-821123.html

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 16;
const int INF = 1e9;
int n;
int dp[1<<MAXN][MAXN], cost[MAXN][MAXN];

int tsp(int mask, int pos) {
    if(mask==(1<<n)-1)
        return cost[pos][0];
    if(dp[mask][pos]!=-1)
        return dp[mask][pos];

    int ans = INF;
    for(int i=0; i<n; i++) {
        if((mask&(1<<i))==0)
            ans = min(ans, cost[pos][i] + tsp(mask|(1<<i), i));
    }
    return dp[mask][pos] = ans;
}

int main() {
    cin>>n;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            cin>>cost[i][j];
        }
    }
    for(int i=0; i<(1<<n); i++) {
        for(int j=0; j<n; j++) {
            dp[i][j] = -1;
        }
    }
    cout<<tsp(1, 0)<<endl;  // start from city 0
    return 0;
}

到了這里，關(guān)于[動態(tài)規(guī)劃,二進制狀態(tài)壓縮] 旅行商問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！