请教老师们一个用蚁群算法解决TSP问题的程序

来源：互联网   发布日期：2011-09-26 13:55:25   浏览：6371次  

最近在搞一个调度的论文，我把它抽象成了一个TSP的问题，由于本人的VC基础不是太好，只会C语言，从别的参考资料上找到一个程序，语法错误已经全部排出，就是连接成EXE的时候出了问题，程序如下：
#include <time.h>
#include <assert.h>
#define N 20 //城市数
#define Q 100 //影响轨迹更新规则的Q值大小
static const int M=10; //蚂蚁数量 
  //城市坐标
  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;
}
  //经过n个城市的一条路径长度
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);
}
//用矩阵表示的经过n个城市的路径长度
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; //初始城市，当前城市
int ALLOWED[N]; //禁忌表
Tour CURRENT_TOUR; //当前路径
int CURRENT_TOUR_INDEX; //当前路径索引
public:
inline Ant(int start_city)
{
START_CITY=start_city;
}
//蚂蚁转移到下一个城市
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){};
//找出一个城市周围最短的边
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;
}
//沿着找出的最短的边进行搜索
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; //定义参数
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); //在蚁群系统中有些定义
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）选择移动方向；若q>q0,则按概率公式进行选择，将q0设为0，则为蚂蚁系统
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;
}
//按概率选择移动方向
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;
}
//选择移动方向，应用局部更新公式进行激素更新
//以下为蚁群系统的实现过程
/*
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;
}

调试时连接出现的问题：
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
执行 link.exe 时出错.
不懂这句提示是什么意思，请老师们指点，感激不尽！




 









































 

赞助本站