【問題描述】

一銷售商從n個城市中的某一城市出發(fā)，不重復(fù)地走完其余n—1個城市并回到原出發(fā)點(diǎn)，在所有可能的路徑中求出路徑長度最短的一條。本題假定該旅行商從第1個城市出發(fā)。

輸入

對每個測試?yán)?行有兩個整數(shù)：n(4≤n≤10)和m(4≤m≤20 ) ，n是結(jié)點(diǎn)數(shù)，m是邊數(shù)。

接下來m行，描述邊的關(guān)系，每行3個整數(shù)：(i，j)，length，表示結(jié)點(diǎn)i到結(jié)點(diǎn)j的長度是length。

當(dāng)n＝0時，表示輸入結(jié)束。

輸出

對每個測試?yán)?，輸出最短路徑長度所經(jīng)歷的結(jié)點(diǎn)，最短的長度。

輸入樣例

4 6

1 2 20

1 4 4

1 3 6

2 3 5

2 4 10

3 4 15

0

輸出樣例

1 3 2 4

25

【算法分析】

旅行商問題的解空間是一棵排列樹。 開始時，x＝｛1，2，…，n｝，相應(yīng)的排列樹由x的全排列構(gòu)成。

TSP問題(Traveling Salesman Problem)通常稱為旅行商問題，也稱為旅行售貨員問題、貨擔(dān)郎問題等，是組合優(yōu)化中的著名難題，也是計(jì)算復(fù)雜性理論、圖論、運(yùn)籌學(xué)、最優(yōu)化理論等領(lǐng)域中的一個經(jīng)典問題，具有廣泛的應(yīng)用背景。

問題的一般描述為：旅行商從n個城市中的某一城市出發(fā)，經(jīng)過每個城市僅有一次，最后回到原出發(fā)點(diǎn)，在所有可能的路徑中求出路徑長度最短的一條。

設(shè)G=(V, E)是一個帶權(quán)圖，其每一條邊(u, v)∈E的費(fèi)用（權(quán)）為正數(shù)w(u, v)。目的是要找出G的一條經(jīng)過每個頂點(diǎn)一次且僅經(jīng)過一次的回路，即漢密爾頓（Hamilton）回路v1，v2 ，…，vn ，使回路的總權(quán)值最小：

?文章來源地址http://www.zghlxwxcb.cn/news/detail-481171.html

【代碼部分】?

//旅行商問題回溯算法的數(shù)據(jù)結(jié)構(gòu)

#define NUM 100
int n;				//圖G的頂點(diǎn)數(shù)量
int m;				//圖G的邊數(shù)
int a[NUM][NUM];		//圖G的鄰接矩陣
int x[NUM];			//當(dāng)前解
int bestx[NUM];		//當(dāng)前最優(yōu)解向量
int cc;				//當(dāng)前費(fèi)用
int bestc;			//當(dāng)前最優(yōu)值
int NoEdge = -1;		//無邊標(biāo)記

//在構(gòu)造鄰接矩陣a時，其初始值應(yīng)為NoEdge：
for (i=0; i<NUM; i++)
　　for (j=1; j<NUM; j++)
　　　　a[i][j] = NoEdge;

//最優(yōu)值和向量x的初始化數(shù)值如下：
bestc = NoEdge;
for(i=1; i<=n; i++)
　　x[i] = i;

//旅行商問題回溯算法的實(shí)現(xiàn)
//形參t是回溯的深度，從2開始
void Backtrack(int t)
{
　　//到達(dá)葉子結(jié)點(diǎn)的父結(jié)點(diǎn)
　　if(t==n)
　　{
　　　　if(a[x[n-1]][x[n]]!= NoEdge && a[x[n]][1]!= NoEdge && 
　　　　　　(cc + a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc== NoEdge))
　　　　{
　　　　　　for(int i=1; i<=n; i++)
　　　　　　　　bestx[i] = x[i];
　　　　　　bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1];
　　　　}
　　　　return;
　　}
else 
　　{
　　　　for(int i=t; i<=n; i++)
　　　　{
　　　　　　if(a[x[t-1]][x[i]]!= NoEdge &&
　　　　　　　　(cc + a[x[t-1]][x[i]]< bestc||bestc == NoEdge))
　　　　　　{
　　　　　　　　swap(x[t],x[i]);
　　　　　　　　cc += a[x[t-1]][x[t]];
　　　　　　　　Backtrack(t+1);
　　　　　　　　cc -= a[x[t-1]][x[t]];
　　　　　　　　swap(x[t],x[i]);
　　　　　　}
　　　　}
　　}
}

//完整實(shí)現(xiàn)
#include <iostream>
using namespace std;

#define NUM 100
int n;
int m;
int a[NUM][NUM];
int x[NUM];
int bestx[NUM];
int cc;
int bestc;
int NoEdge = -1;

void Backtrack(int t)
{
	if(t==n)
	{
		if(a[x[n-1]][x[n]]!= NoEdge && a[x[n]][1]!= NoEdge && 
			(cc + a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc== NoEdge))
		{
			for(int i=1; i<=n; i++)
				bestx[i] = x[i];
			bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1];
		}
		return;
	}
	else 
	{
		for(int i=t; i<=n; i++)
		{
			if(a[x[t-1]][x[i]]!= NoEdge &&
				(cc + a[x[t-1]][x[i]]< bestc||bestc == NoEdge)) 
			{
				swap(x[t],x[i]);
				cc += a[x[t-1]][x[t]];
				Backtrack(t+1);
				cc -= a[x[t-1]][x[t]];
				swap(x[t],x[i]);
			}
		}
	}
}

int main() 
{
	int i, j;
	int from, to, length;
	while (scanf("%d%d", &n, &m) && n) 
	{
		for (i=0; i<NUM; i++)
			for (j=1; j<NUM; j++)
				a[i][j] = NoEdge;
		for (i=0; i<m; i++)
		{
			scanf("%d%d%d", &from, &to, &length);
			a[from][to] = length;
			a[to][from] = length;
		}
		bestc = NoEdge;
		for(i=1; i<=n; i++)
			x[i] = i;
		Backtrack(2);
		for(j=1; j<=n; j++)
			printf("%d ", bestx[j]);
		printf("\n%d\n", bestc);
	}	
	return 0;
}

到了這里，關(guān)于【回溯算法】旅行商問題--TSP問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！