📄 antprogram.txt
字号:
把以下6个文件存在同一目录下，然后对anttsp.cpp编译即可。
文件1：anttsp.h
算法源码如下：
anttsp.h
/* C++源程序
* 本文件是求解旅行售货员（TSP）问题的蚂蚁算法的头文件
* 算法的几个主要参数：
* arfa——轨迹的相对重要性（arfa>=0）
* beta——能见度的相对重要性（beta>=0）
* rou ——轨迹的持久性（0<=rou<1），可将1-rou理解为迹衰减度
*/
#ifndef AntTspH
#define AntTspH
class AntTsp{
private:
//double *p;
//int *allow;
matrix d;
int n;
int randchoice(double *pp,int lengthp);
void antk_path(double *t,double *y,double r,double b,double Q,
int *path1,double *z,double *dt);
public:
double arfa,beta,c,rou;
int m,nc;
AntTsp(void){arfa=1;beta=1;c=0.01;rou=0.8;m=0;nc=0;};
~AntTsp(){};
double Ant(int *pathmin);
};
#endif //AntTspH
文件2：anttsp.cpp
#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include"anttsp.h"
#include"matrix.cpp"
double AntTsp::rand0(void){
return (rand()%1000)/1000.0;
}
int AntTsp::randchoice(double *p,int lengthp)
{
double *t,b;
int high=lengthp,low=0,mid,i;
t=(double *)malloc((lengthp+1)*sizeof(double));
if(t==NULL) { printf("assign fail!\n"); exit(0); }
t[0]=0.0;
for(i=1;i<=lengthp;i++)
t[i]=p[i-1];
for(i=2;i<=lengthp;i++)
t[i]+=t[i-1];
b=rand0()*t[lengthp];
while(high-low>=2)
{
mid=floor((high+low)/2.0);
if(b>t[mid]) low=mid;
else high=mid;
}
free(t);
return(low);
}
void AntTsp::antk_path(double *t,double *y,double rr,double bb,double Q,
int *path1,double *z,double *dt)
{
double a;
int sup,i,i0,ii,allowlength;
*z=0;
sup=0;
allowlength=n-1;
a=floor((double)(rand()%1000)/1000.0*n);
path1[0]=(int)a;
for(i=0;i<=path1[0]-1;i++)
allow[i]=i;
for(i=path1[0];i<=n-2;i++)
allow[i]=i+1;
while(sup<=n-2)
{
ii=path1[sup];
for(i=0;i<=allowlength-1;i++)
p[i]=pow(t[n*ii+allow[i]],rr)*pow(y[n*ii+allow[i]],bb);
i0=randchoice(p,allowlength);
path1[sup+1]=allow[i0];
(*z)+=d(ii,allow[i0]);
for(i=i0+1;i<=allowlength-1;i++)
allow[i-1]=allow[i];
allowlength--;
sup++;
}
(*z)+=d(path1[n-1],path1[0]);
for(i=0;i<=n-2;i++)
dt[n*path1[i]+path1[i+1]]+=Q/(*z);
dt[n*path1[n-1]+path1[0]]+=Q/(*z);
}
double AntTsp::Ant(int *pathmin)
{
p=new double[n];
allow=new int[n];
double tspmin;
double *t,*t1,*y,*dt,z,Q,Qmin=1.0e+300,Qmax=0.0;
int *path1;
int i,j,ii;
t=new double[n*n];
if(!t){ printf("assign fail \n"); exit(0); }
t1=new double[n*n];
y=new double[n*n];
if(y==NULL){ printf("assign fail \n"); exit(0); }
dt=new double[n*n];
if(dt==NULL){ printf("assign fail\n"); exit(0); }
path1=new int[n];
if(path1==NULL){ printf("asign fail\n"); exit(0); }
for(i=0;i<=n-1;i++)
{
t[n*i+i]=c;
y[n*i+i]=0.0;
for(j=i+1;j<=n-1;j++)
{
t[n*i+j]=t[n*j+i]=c;
y[n*i+j]=y[n*j+i]=1.0/d(i,j);
}
}
for(i=0;i<=n-1;i++)
for(j=i+1;j<=n-1;j++)
{
if(Qmax<d(i,j)) Qmax=d(i,j);
if(Qmin>d(i,j)) Qmin=d(i,j);
}
Q=c*n*(Qmin+Qmax)/2.0;
tspmin=1.0e+300;
ii=0;
for(i=0;i<=n-1;i++)
for(j=i+1;j<=n-1;j++)
dt[n*i+j]=dt[n*j+i]=0.0;
for(i=0;i<=n-1;i++)
dt[n*i+i]=0.0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
t1[n*i+j]=t[n*i+j];
while(ii<=nc-1){
for(j=0;j<=m-1;j++){
antk_path(t,y,r,b,Q,path1,&z,dt);
if(tspmin>z){
tspmin=z;
for(i=0;i<=n-1;i++)
pathmin[i]=path1[i]+1;
}
for(int i1=0;i1<=n-1;i1++)
for(int j1=0;j1<=n-1;j1++)
t1[n*i1+j1]=pp*t1[n*i1+j1]+dt[n*i1+j1];
}
for(i=0;i<=n-1;i++)
for(j=0;j<=n-1;j++)
t[n*i+j]=t1[n*i+j];
ii++;
}
delete []t;
delete []t1;
delete []y;
delete []dt;
delete []path1;
delete []p;
delete []allow;
return tspmin;
}
void main(void)
{
int i,j;
int *pathmin;
/* double dd[36]={100.0,5.0 ,4.0, 5.0, 10.0, 2.5,
5.0, 100.0,3.0, 4.0, 5.0, 3.5,
4.0, 3.0, 100.0,7.0, 4.5, 5.0,
5.0, 4.0, 7.0, 100.0,2.5, 4.0,
10.0, 5.0, 4.5, 2.5, 100.0,5.5,
2.5, 3.5, 5.0, 4.0, 5.5, 100.0
},
*/
double *dd;
double tspmin;
int n=60;
dd=new double[n*n];
for(i=0;i<n;i++){
for(j=i+1;j<n;j++)
dd[n*i+j]=dd[n*j+i]=(double)(rand()%1000)/1000.0;
dd[n*i+i]=1.0e+200;
}
pathmin=new int[n];
matrix d(dd,n,n);
AntTsp tt;
tt.d=d;
tt.n=n;
tt.m=50;
tt.nc=1;
tt.r=0.06;
tt.b=1.2;
tt.pp=0.9;
tt.c=1.0;
while(tt.nc>0){
tspmin=tt.Ant(pathmin);
printf("tspmin=%lf\n",tspmin);
printf("pathmin:\n ");
for(i=0;i<=n-1;i++)
printf("%d-->",pathmin[i]);
printf("%d\n",pathmin[0]);
cout<<"Input nc: ";
cin>>tt.nc;
}
delete []pathmin;
delete [] dd;
}
文件3：matrix.cpp
#ifndef MATRIX_CPP
#define MATRIX_CPP
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <fstream.h>
// 本程序实现matrix类
// 对matrix类的定义
#include "matrix.h"
matrix::matrix(buffer * b): // 缺省构造函数，产生0行0列空矩阵
rownum(0),colnum(0),istrans(0),isneg(0),issym(0)
{
if(b){ // 如用户给出b，则使用b作为数据缓存
buf=b;
buf->alloc(0);
}
else // 否则，产生一个新的缓存，类别是当前缺省的缓存类
buf = getnewbuffer(0);
}
matrix::matrix(size_t n, buffer * b): // 产生n阶单位方阵
rownum(n),colnum(1),istrans(0),isneg(0),issym(0)
{
if(b){ // 如用户给出b，则使用b作为数据缓存
buf=b;
buf->alloc(n);
}
else // 否则，产生一个新的缓存，类别是当前缺省的缓存类
buf = getnewbuffer(n);
}
matrix unit(size_t n)
{
if(n==0) throw TMESSAGE("n must larger than 0\n");
matrix m(n,n);
for(size_t i=0; i<n; i++)
for(size_t j=0; j<n; j++)
if(i==j) m.set(i,j,1.0);
else m.set(i,j,0.0);
m.issym = 1;
return m;
}
matrix::matrix(size_t r, size_t c, buffer * b):
rownum(r),colnum(c),istrans(0),isneg(0),issym(0)
{
if(b){ // 如用户给出b，则使用b作为数据缓存
buf=b;
buf->alloc(r*c);
}
else // 否则，产生一个新的缓存，类别是当前缺省的缓存类
buf = getnewbuffer(r*c);
}
matrix::matrix(matrix& m) // 拷贝构造函数
{
rownum = m.rownum; // 拷贝行数与列数
colnum = m.colnum;
istrans = m.istrans; // 拷贝转置标记
isneg = m.isneg; // 拷贝负值标记
issym = m.issym; // 拷贝对称标记
buf = m.buf; // 设置指向相同缓存的指针
buf->refnum++; // 缓存的引用数增1
}
matrix::matrix(const char * filename, buffer * b): // 从数据文件构造矩阵
istrans(0), isneg(0), issym(0){
buf=b;
loadfile(filename);
}
matrix::matrix(void * data, size_t r, size_t c, buffer * b):
rownum(r),colnum(c),istrans(0),isneg(0),issym(0) // 数据构造函数
{
if(b){
buf=b;
buf->alloc(r*c);
}
else
buf = getnewbuffer(r*c);
DOUBLE * d = (DOUBLE *)data;
for(size_t i=0; i<r*c; i++) // 这里进行数据拷贝，因此原数据的内存是可以释放的
buf->set(i,d[i]);
checksym(); // 检查是否为对称阵
}
void matrix::loadfile(const char * filename){// 从数据文件构造矩阵
size_t rownum1,colnum1;
int g;
istrans=0;
isneg=0;
issym=0;
char label[10];
ifstream fin(filename); // 打开文件流
fin>>g; // 读取数据文件格式数
fin >> label; // 文件开始必须有matrix关键词
if(strcmp(label, "matrix")!=0) throw -1;
fin >> rownum1 >> colnum1; // 读取行数和列数
if(!fin.good()) throw TMESSAGE("read file error!");
if(buf){
if((rownum1*colnum1)!=(rownum*colnum)){
buf->alloc(rownum1*colnum1);
rownum=rownum1;
colnum=colnum1;
}
else{
rownum=rownum1;
colnum=colnum1;
}
}
else{
buf = getnewbuffer(rownum1*colnum1);
rownum=rownum1;
colnum=colnum1;
}
if(g==2){
size_t line;
for(size_t i=0; i<rownum; i++) { // 依次按行读取
fin >> line; // 读行号
if(line != i+1) throw -1;
fin.width(sizeof(label));
fin >> label; // 行号后跟冒号
if(label[0] != ':') throw TMESSAGE("format error!");
DOUBLE a;
for(size_t j=0; j<colnum; j++) { // 读取一行数据
fin >> a;
set(i,j,a);
}
if(!fin.good()) throw TMESSAGE("read file error!");
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -