Chinaunix

标题: C语言实现TSP 动态规划 [打印本页]

---

作者: zhlzn    时间: 2008-12-09 00:47
标题: C语言实现TSP 动态规划
/*
  *  平台： Debian 5.0
*  编译器：gcc version 4.3.2 (Debian 4.3.2-1)
*  任何问题联系：goon83@126.com
*/
#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  StateArrayCur.Dis){
                        MinState = StateArrayCur;
                    }               
               
                    StateArrayCur.CurNode = DELETE;       //-1表示从StateCur中删掉   
                }            
            }
            NewStateArray[NewStateCount] = MinState;
            NewStateCount = NewStateCount + 1;
        
        }   
    }            
    for ( k =0; k = 0; i--){
        printf(" %d ", (StateArrayCur[MinIndex].LeftNode + 1));
    }
    printf(" 1 \n");
    return 0;
}


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/63043/showart_1686548.html

---

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)

Powered by Discuz! X3.2