請(qǐng)教老師們一個(gè)用蟻群算法解決TSP問題的程序

來源：互聯(lián)網(wǎng)   發(fā)布日期：2011-09-26 13:55:25   瀏覽：6636次  

最近在搞一個(gè)調(diào)度的論文，我把它抽象成了一個(gè)TSP的問題，由于本人的VC基礎(chǔ)不是太好，只會(huì)C語言，從別的參考資料上找到一個(gè)程序，語法錯(cuò)誤已經(jīng)全部排出，就是連接成EXE的時(shí)候出了問題，程序如下：
#include <time.h>
#include <assert.h>
#define N 20 //城市數(shù)
#define Q 100 //影響軌跡更新規(guī)則的Q值大小
static const int M=10; //螞蟻數(shù)量 
  //城市坐標(biāo)
  double C[N][2]={{5.924,1.558},{4.286,3.622},{4.179,2.744},{4.185,2.230},{0.195,3.821},{4.771,6.041},{1.524,2.871},
{3.477,2.111},{3.718,3.665},{2.649,2.556},{4.399,1.94},{4.660,2.949},{1.232,6.440},{5.036,0.244},{2.710,3.140},{1.072,3.454},
{5.855,6.203},{0.194,1.862},{1.7962,2.693},{2.682,6.097}};
typedef int Tour[N][2];
  typedef double doubleMatrix[N][N];
  doubleMatrix D;
//兩城市之間的幾何距離
double dist(int i,int j)
  {
return sqrt(pow((C[i][0]-C[j][0]),2.0)+pow((C[i][1]-C[j][1]),2.0));
  }
//由矩陣表示的城市之間的距離長度
void calc_dist()
{
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
D[i][j]=dist(i,j);
}
//兩城市之間的最大距離
double max_dist()
{
double max_dist=0.0;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if(dist(i,j)>max_dist)
max_dist=dist(i,j);
return max_dist;
}
  //經(jīng)過n個(gè)城市的一條路徑長度
double calc_length(Tour*tour)
{
double l=0.0;
for(int n=0;n<N;n++)
{
int i=(*tour)[n][0];
int j=(*tour)[n][1];
l+=D[i][j];
}
return (l);
}
//用矩陣表示的經(jīng)過n個(gè)城市的路徑長度
int sum_sequence(int array[],int count)
{
int sum=0;
for(int i=0;i<count;i++)
sum+=array[i];
return (sum);
}
/***************************************************************/
class Ant
{
protected:
int START_CITY,CURRENT_CITY; //初始城市，當(dāng)前城市
int ALLOWED[N]; //禁忌表
Tour CURRENT_TOUR; //當(dāng)前路徑
int CURRENT_TOUR_INDEX; //當(dāng)前路徑索引
public:
inline Ant(int start_city)
{
START_CITY=start_city;
}
//螞蟻轉(zhuǎn)移到下一個(gè)城市
inline void moveTO(int to_city)
{
ALLOWED[to_city]=0;
CURRENT_TOUR[CURRENT_TOUR_INDEX][0]=CURRENT_CITY;
CURRENT_TOUR[CURRENT_TOUR_INDEX][1]=to_city;
CURRENT_TOUR_INDEX++;
CURRENT_CITY=to_city;
}
};
class NNAnt:Ant
{
public:
inline NNAnt(int start_city):Ant(start_city){};
//找出一個(gè)城市周圍最短的邊
inline int choose()
{
double best_length=(double)N*max_dist();
int best_choose=-1;
for(int j=0;j<N;j++)
{
if((ALLOWED[j]==1)&&(D[CURRENT_CITY][j]<best_length))
{
best_choose=j;
best_length=D[CURRENT_CITY][j];
}
}
return best_choose;
}
//沿著找出的最短的邊進(jìn)行搜索
inline Tour*search()
{
CURRENT_CITY=START_CITY;
CURRENT_TOUR_INDEX=0;
for(int i=0;i<N;i++)
ALLOWED[i]=1;
ALLOWED[CURRENT_CITY]=0;
while(sum_sequence(ALLOWED,N)>0)
moveTO(choose());
ALLOWED[START_CITY]=1;
moveTO(START_CITY);
return &CURRENT_TOUR;
}
};
class AntColonySystem;
class ACSAnt:Ant
{
private:
AntColonySystem*ACS;
public:
ACSAnt(AntColonySystem*acs,int start_city):Ant(start_city)
{
ACS=acs;
}
inline int choose();
inline Tour*search();
};
class AntColonySystem
{
private:
double ALPHA,BETA,RHO,TAU0,ALPHA1; //定義參數(shù)
doubleMatrix TAU,dTAU;
ACSAnt*ANTS[M];
public:
double Q0;
AntColonySystem(double alpha,double beta,double rho,double q0,double alpha1);
inline double calc_tau0();
inline void init_tau_by_value(double value);
inline void init_tau_by_matrix(doubleMatrix matrix);
inline void init_uniform();
inline void init_random();
inline void init_randomMOAPC();
inline double ETA(int i,int j);
inline double transition(int i,int j);
inline double sum_transition(int i,int allowed[]);
inline void local_update_rule(int i,int j); //在蟻群系統(tǒng)中有些定義
inline void clear_global_update();
inline void add_global_update(Tour*tour,double length);
inline void global_update_rule();
inline doubleMatrix*get_tau();
inline Tour*search(int T);
};
//若q<q0,則按公式（3-7）選擇移動(dòng)方向；若q>q0,則按概率公式進(jìn)行選擇，將q0設(shè)為0，則為螞蟻系統(tǒng)
inline int ACSAnt::choose()
{
double q=rand()/(double)RAND_MAX;
if(q<=ACS->Q0)
{
double best_value=-1.0;
int best_choose=-1;
for(int j=0;j<N;j++)
{
if((ALLOWED[j]==1)&&(ACS->transition(CURRENT_CITY,j)>best_value))
{
best_choose=j;
best_value=ACS->transition(CURRENT_CITY,j);
}
}
return best_choose;
}
//按概率選擇移動(dòng)方向
double sum=ACS->sum_transition(CURRENT_CITY,ALLOWED);
double p=rand()/(double)RAND_MAX;
double p_j=0.0;
for(int j=0;j<N;j++)
{
if(ALLOWED[j]==1)p_j+=ACS->transition(CURRENT_CITY,j)/sum;
if((p<p_j)&&(ALLOWED[j]==1))
return j;
}
return -1;
}
//選擇移動(dòng)方向，應(yīng)用局部更新公式進(jìn)行激素更新
//以下為蟻群系統(tǒng)的實(shí)現(xiàn)過程
/*
inline Tour*ACSAnt::search()
{
CURRENT_CITY=START_CITY;
int tocity;
CURRENT_TOUR_INDEX=0;
for(int i=0;i<N;i++)
ALLOWED[i]=1;
ALLOWED[CURRENT_CITY]=0;
int LAST_CITY; 
while(1)
{
LAST_CITY=CURRENT_CITY;
tocity=choose();
if(tocity==-1)
{
break;
}
moveTO(tocity);
ACS->local_update_rule(CURRENT_CITY,START_CITY);
moveTO(START_CITY);
return &CURRENT_TOUR;
}

調(diào)試時(shí)連接出現(xiàn)的問題：
Linking...
ant.obj : error LNK2001: unresolved external symbol "public: int (* __thiscall ACSAnt::search(void))[20][2]" (?search@ACSAnt@@QAEPAY1BE@1HXZ)
Debug/ant.exe : fatal error LNK1120: 1 unresolved externals
執(zhí)行 link.exe 時(shí)出錯(cuò).
不懂這句提示是什么意思，請(qǐng)老師們指點(diǎn)，感激不盡！




 









































 

贊助本站