原文地址: http://blog.csdn.net/gfaiswl/article/details/4749713
1.問題定義
TSP問題（旅行商問題）是指旅行家要旅行n個城市，要求各個城市經歷且僅經歷一次然后回到出發城市，并要求所走的路程最短。
假設現在有四個城市，0,1,2,3，他們之間的代價如圖一，可以存成二維表的形式
圖一
現在要從城市0出發，最后又回到0，期間1，2，3都必須并且只能經過一次，使代價最小。
2.動態規劃可行性
設s, s1, s2, …, sp, s是從s出發的一條路徑長度最短的簡單回路，假設從s到下一個城市s1已經求出，則問題轉化為求從s1到s的最短路徑，顯然s1, s2, …, sp, s一定構成一條從s1到s的最短路徑，所以TSP問題是構成最優子結構性質的，用動態規劃來求解也是合理的。
3.推導動態規劃方程
假設從頂點s出發，令d(i, V’)表示從頂點i出發經過V’(是一個點的集合)中各個頂點一次且僅一次，最后回到出發點s的最短路徑長度。
推導：(分情況來討論)
①當V’為空集，那么d(i, V’)，表示從i不經過任何點就回到s了，如上圖的 城市3->城市0(0為起點城市)。此時d(i, V’)=Cis(就是 城市i 到 城市s 的距離)、
②如果V’不為空，那么就是對子問題的最優求解。你必須在V’這個城市集合中，嘗試每一個，并求出最優解。
d(i, V’)=min{Cik + d(k, V’-{k})}
注：Cik表示你選擇的城市和城市i的距離，d(k, V’-{k})是一個子問題。
綜上所述，TSP問題的動態規劃方程就出來了：
4.實例分析
現在對問題定義中的例子來說明TSP的求解過程。(假設出發城市是 0城市)
①我們要求的最終結果是d(0,{1,2,3}),它表示，從城市0開始，經過{1,2,3}之中的城市并且只有一次，求出最短路徑.
②d(0,{1,2,3})是不能一下子求出來的，那么他的值是怎么得出的呢？看上圖的第二層，第二層表明了d(0,{1,2,3})所需依賴的值。那么得出：
d(0,{1,2,3})=min {
C01+d(1,{2,3})
C02+d{2,{1,3}}
C03+d{3,{1,2}}
}
③d(1,{2,3})，d(2,{1,3})，d(3,{1,2})同樣也不是一步就能求出來的，它們的解一樣需要有依賴，就比如說d(1,{2,3})
d(1,{2,3})=min{
C12+d(2,{3})
C13+d(3,{2})
}
d(2,{1,3})，d(3,{1,2})同樣需要這么求。
④按照上面的思路，只有最后一層的，當當V’為空集時，Cis的值才可以求，它的值是直接從
這張表里求得的。
5.編程思路
將d(i, V’)轉換成二維表，d[i][j]
在程序中模擬填表的過程，主要要考慮到j這個參數的表示，它要代表一個集合，可以用二維數組來表示。
6.源代碼
注：由于本人水平有限，并且主要在這里是體現思路，所以程序并不是很完善，代碼質量也不高，很地方可以寫得通用一些，所以這里只是提供一個參考，程序的進一步完善，由讀者自由發揮。
#include
#include
int IsIncluded(int x,int array[3])//x是否包含在數組中
{
if((array[0] != x) && (array[1] != x) && (array[2] != x))
return 0;
return 1;
}
int Left(int k,int array[3],int V[8][3])//實現V'-{k} 的下標檢索
{
int i = 0,index = 0,array_0_count = 0,array_1_count = 0,array_2_count = 0,array_3_count = 0;
int V_0_count = 0,V_1_count = 0,V_2_count = 0,V_3_count = 0;
int temp[3];
for(i = 0; i < 3; i++)
temp[i] = array[i];
for(i = 0; i < 3; i++)
if(temp[i] == k)
temp[i] = 0; //相當于去掉k這個城市
for(i = 0; i < 3; i++)
{
if(temp[i] == 0)
array_0_count++;
else if(temp[i] == 1)
array_1_count++;
else if(temp[i] == 2)
array_2_count++;
else
array_3_count++;
}
for(index = 0; index < 8; index++)
{
for(i=0; i < 3; i++)
{
if(V[index][i] == 0)
V_0_count++;
else if(V[index][i] == 1)
V_1_count++;
else if(V[index][i] == 2)
V_2_count++;
else
V_3_count++;
}
if((array_0_count == V_0_count) && (array_1_count == V_1_count)
&& (array_2_count == V_2_count) && (array_3_count == V_3_count))
return index;
V_0_count = 0;
V_1_count = 0;
V_2_count = 0;
V_3_count = 0;
}
return 0;
}
void TSP(int d[4][8],int c[4][4],int V[8][3],int n)
{
int i = 0,j = 0,k = 0;
for(i = 1; i < n; i++)//V'為空時，給賦值，
d[i][0] = c[i][0];
for(j = 1; j < 7; j++)//按列遍歷不同集合，{1},{2},{3},{1,2},{1,3}.....
{
for(i = 1; i < n; i++)//遍歷城市1，2，3
{
if( !IsIncluded(i,V[j]) )//i必須不在集合中，否則就屬于經過兩次，不符合題意
{
for(k = 0; k < 3; k++)//分別試探集合中的每一點，取最小值
{
if((V[j][k] != 0) && ((c[i][V[j][k]] + d[V[j][k]][Left(V[j][k],V[j],V)]) < d[i][j]))
d[i][j] = c[i][V[j][k]] + d[V[j][k]][Left(V[j][k],V[j],V)];
}
}
}//end of for(i = 1; i < n; i++)//遍歷城市1，2，3
}//end of for(j = 1; j < ((int)pow(2,n)-1); j++)
for(k = 0; k < 3; k++)//分別試探下一步為集合中的任何一點，取最小值
{
if((V[7][k] != 0) && (c[0][V[7][k]] + d[V[7][k]][Left(V[7][k],V[7],V)]) < d[0][7])
d[0][7] = c[0][V[7][k]] + d[V[7][k]][Left(V[7][k],V[7],V)];
}
}
void main()
{
int V[8][3]=
{
0,0,0,
0,0,1,
0,0,2,
0,0,3,
0,1,2,
0,1,3,
0,2,3,
1,2,3
};
int c[4][4]=
{
0,3,6,7,
5,0,2,3,
6,4,0,2,
3,7,5,0
};
int d[4][8]={0},i=0,j=0;
for(i=0; i<4; i++)
for(j=0; j<8; j++)
d[i][j]=1000; //假設1000為無窮大
TSP(d,c,V,4);
printf("The least road is:%d/n",d[0][7]);
}
posted on 2013-03-31 05:26
luis 閱讀(18778)
評論(0) 編輯 收藏 引用 所屬分類:
動態規劃