C语言实现TSP 动态规划

/*
  *  平台： Debian 5.0
 *  编译器：gcc version 4.3.2 (Debian 4.3.2-1)
 *  任何问题联系：[e-mail]
 */

#include

#define MAXN        6
#define MAXSTATE 120        //在迭代过程中的最多的状态数量(5 * 4 * 3 * 2 * 1)
#define TRUE         1
#define FALSE        0
#define DELETE      1000     //设置一个足够大的数来表示删除当前结点

struct StateStruct{
    int CurNode;                   //当前的结点
    int LeftNode[MAXN -1];   //最多有 (MAXN -1)个未访问的结点
    int LeftNodeCount;          //记录LeftNode数组的长度
    int Dis;                           //从该结点回到目标节点的距离
};

typedef struct StateStruct State;

//最多有MAXSTATE个状态。
State   StateArrayCur[MAXSTATE];
State   StateArrayOld[MAXSTATE];


int Dis[MAXN][MAXN] ={
    0, 10, 20, 30, 40, 50,
        12, 0 ,18, 30, 25, 21,
        23, 19, 0, 5,  10, 15,
        34, 32, 4, 0,  8,  16,
        45, 27, 11,10, 0,  18,
        56, 22, 16,20, 12,  0
};

/*
 *比较两个状态TempState, TargetState是否一致
 *返回： TRUE  两个状态一致,可以合并
 *           FALSE 两个状态不一致， 不可以合并
 */
int CompareState(State TempState, State TargetState){
    int i;
   
    if (TempState.CurNode != TargetState.CurNode){
        return FALSE;
    }
   

    for (i = 0; i < TempState.LeftNodeCount; i ++){
        if((Contain(TargetState, TempState.LeftNode[i]) == FALSE)){
            return FALSE;
        }       
    }

    return TRUE;
   
}

/*
 *判断当前状态 TempState是否包含结点 j
 *返回： TRUE  状态包含 j
 *           FALSE 状态不包含 j
 */
int Contain(State TempState, int j){
    int i;
    if (TempState.CurNode == j){
        return TRUE;
    }

    for (i = 0; i < TempState.LeftNodeCount; i++){
        if (TempState.LeftNode[i] == j){
            return TRUE;
        }   
    }

    return FALSE;
}
/*
 *合并在当前阶段中可以合并的状态，
 *      在该阶段中状态的初始的个数为Index，
 *      合并后剩下的状态数量为NewStateCount
 */
int Combine(int Index){
    int      left, k;
    State NewStateArray[MAXSTATE];                    //临时用来记录合并后的状态
    int     NewStateCount;                                     //合并后状态的数量
    State MinState;
    NewStateCount = 0;

   
    for (left = 0; left < Index; left++){                 //从左到右发现一个新的状态
        if (StateArrayCur[left].CurNode != DELETE){
            MinState = StateArrayCur[left];
            StateArrayCur[left].CurNode = DELETE;   //-1表示从StateCur中删掉
       
       
            int i;
            for (i = left+1; i < Index; i++){ // 合并相同的状态
                if (CompareState(MinState, StateArrayCur[i]) == TRUE){
                    if (MinState.Dis > StateArrayCur[i].Dis){
                        MinState = StateArrayCur[i];
                    }               
               
                    StateArrayCur[i].CurNode = DELETE;       //-1表示从StateCur中删掉   
                }           
            }
            NewStateArray[NewStateCount] = MinState;
            NewStateCount = NewStateCount + 1;
       
        }   
    }           


    for ( k =0; k < NewStateCount; k++){
        StateArrayCur[k] = NewStateArray[k];   
    }
   
    return NewStateCount;
}

int  main(int argc, char *argv[]){
    int i, MinLength, MinIndex, TempLength;
    int p, NewStateCount;
   
    //每个节点回到起始点的距离
    for( i= 1;  i < MAXN  ; i ++){               
        StateArrayCur[i-1].CurNode = i;
        StateArrayCur[i-1].LeftNodeCount = 0;
        StateArrayCur[i-1].Dis   = Dis[i][0];
    }

    NewStateCount = MAXN - 1;
    //开始迭代MAXN－2次
    for (i = 1; i <=(MAXN - 2); i++){
        for (p = 0; p < NewStateCount;  p++ ){
            StateArrayOld[p] = StateArrayCur[p];
            //if ( NewStateCount == 20)
            //    printf("%d \n", StateArrayOld[p].Dis);   
        }

        int index , j;
        index = 0;

        for(  j = 1; j < MAXN; j++){
            int r, k;
            for(k = 0 ; k < NewStateCount; k++){
                if ((Contain(StateArrayOld[k], j) == FALSE)){     //如果原状态中不包括 j . 则增加一个新状态包含（j, 原状态）
                    StateArrayCur[index] = StateArrayOld[k];
                    StateArrayCur[index].LeftNode[ StateArrayOld[k].LeftNodeCount] = StateArrayOld[k].CurNode;
                    StateArrayCur[index].LeftNodeCount =StateArrayOld[k].LeftNodeCount + 1;
                    StateArrayCur[index].Dis  = StateArrayOld[k].Dis + Dis[j][StateArrayOld[k].CurNode];
                    StateArrayCur[index].CurNode = j;

                    index = index + 1;
                }
            }
        }


        if (i != 1){       
            NewStateCount = Combine(index);                //选择相同状态中最小的记录下来       
        }else{
            NewStateCount = index;                                               //第一次的迭代不用合并
        }

    }
   

    MinLength  = StateArrayCur[0].Dis + Dis[0][StateArrayCur[0].CurNode];
    MinIndex = 0;

    for(i = 1 ; i < MAXN - 1; i++){
        TempLength =StateArrayCur[i].Dis + Dis[0][StateArrayCur[i].CurNode];
        if (TempLength < MinLength){
            MinIndex  = i;
            MinLength = TempLength;
        }
    }
   
    printf("Shortest distance: %d \n", MinLength);
    printf("Path : ",MinIndex);
    printf(" 1 ");
    printf(" %d ", StateArrayCur[MinIndex].CurNode + 1);
    for (i = MAXN - 3; i >= 0; i--){
        printf(" %d ", (StateArrayCur[MinIndex].LeftNode[i] + 1));
    }
    printf(" 1 \n");
    return 0;
}