原文地址: http://blog.csdn.net/gfaiswl/article/details/4749713

1.問題定義

      TSP問題（旅行商問題）是指旅行家要旅行n個(gè)城市，要求各個(gè)城市經(jīng)歷且僅經(jīng)歷一次然后回到出發(fā)城市，并要求所走的路程最短。

      假設(shè)現(xiàn)在有四個(gè)城市，0,1,2,3，他們之間的代價(jià)如圖一，可以存成二維表的形式

                      圖一                                                                                               

        現(xiàn)在要從城市0出發(fā)，最后又回到0，期間1，2，3都必須并且只能經(jīng)過(guò)一次，使代價(jià)最小。

2.動(dòng)態(tài)規(guī)劃可行性

        設(shè)s, s1, s2, …, sp, s是從s出發(fā)的一條路徑長(zhǎng)度最短的簡(jiǎn)單回路，假設(shè)從s到下一個(gè)城市s1已經(jīng)求出，則問題轉(zhuǎn)化為求從s1到s的最短路徑，顯然s1, s2, …, sp, s一定構(gòu)成一條從s1到s的最短路徑，所以TSP問題是構(gòu)成最優(yōu)子結(jié)構(gòu)性質(zhì)的，用動(dòng)態(tài)規(guī)劃來(lái)求解也是合理的。

3.推導(dǎo)動(dòng)態(tài)規(guī)劃方程

        假設(shè)從頂點(diǎn)s出發(fā)，令d(i, V’)表示從頂點(diǎn)i出發(fā)經(jīng)過(guò)V’(是一個(gè)點(diǎn)的集合)中各個(gè)頂點(diǎn)一次且僅一次，最后回到出發(fā)點(diǎn)s的最短路徑長(zhǎng)度。

        推導(dǎo)：(分情況來(lái)討論)

        ①當(dāng)V’為空集，那么d(i, V’)，表示從i不經(jīng)過(guò)任何點(diǎn)就回到s了，如上圖的 城市3->城市0(0為起點(diǎn)城市)。此時(shí)d(i, V’)=Cis(就是 城市i 到 城市s 的距離)、

        ②如果V’不為空，那么就是對(duì)子問題的最優(yōu)求解。你必須在V’這個(gè)城市集合中，嘗試每一個(gè)，并求出最優(yōu)解。

           d(i, V’)=min{Cik +  d(k, V’-{k})}

           注：Cik表示你選擇的城市和城市i的距離，d(k, V’-{k})是一個(gè)子問題。

        綜上所述，TSP問題的動(dòng)態(tài)規(guī)劃方程就出來(lái)了：

4.實(shí)例分析

     現(xiàn)在對(duì)問題定義中的例子來(lái)說(shuō)明TSP的求解過(guò)程。(假設(shè)出發(fā)城市是 0城市)

    ①我們要求的最終結(jié)果是d(0,{1,2,3}),它表示，從城市0開始，經(jīng)過(guò){1,2,3}之中的城市并且只有一次，求出最短路徑.

    ②d(0,{1,2,3})是不能一下子求出來(lái)的，那么他的值是怎么得出的呢？看上圖的第二層，第二層表明了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})同樣也不是一步就能求出來(lái)的，它們的解一樣需要有依賴，就比如說(shuō)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})同樣需要這么求。

    ④按照上面的思路，只有最后一層的，當(dāng)當(dāng)V’為空集時(shí)，Cis的值才可以求，它的值是直接從

這張表里求得的。

     5.編程思路

        將d(i, V’)轉(zhuǎn)換成二維表，d[i][j]

        在程序中模擬填表的過(guò)程，主要要考慮到j(luò)這個(gè)參數(shù)的表示，它要代表一個(gè)集合，可以用二維數(shù)組來(lái)表示。

   6.源代碼

注：由于本人水平有限，并且主要在這里是體現(xiàn)思路，所以程序并不是很完善，代碼質(zhì)量也不高，很地方可以寫得通用一些，所以這里只是提供一個(gè)參考，程序的進(jìn)一步完善，由讀者自由發(fā)揮。

#include 
#include

int IsIncluded(int x,int array[3])//x是否包含在數(shù)組中 
{ 
    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])//實(shí)現(xiàn)V'-{k} 的下標(biāo)檢索 
{ 
    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;  //相當(dāng)于去掉k這個(gè)城市 
    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'為空時(shí)，給賦值， 
        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必須不在集合中，否則就屬于經(jīng)過(guò)兩次，不符合題意 
            { 
                for(k = 0; k < 3; k++)//分別試探集合中的每一點(diǎn)，取最小值 
                { 
                    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++)//分別試探下一步為集合中的任何一點(diǎn)，取最小值 
    { 
        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;   //假設(shè)1000為無(wú)窮大 
    TSP(d,c,V,4); 
    printf("The least road is:%d/n",d[0][7]); 
}