📄 marklink.cpp
字号:
{
adjlist[0][m] = line_length(start,middle[m].vertex);
adjlist[m][0] = adjlist[0][m];
}
if(m==11)
{
adjlist[num_middle_node][m]=line_length(end,middle[m].vertex);
adjlist[m][num_middle_node]=adjlist[num_middle_node][m];
}
}
for (m = 1 ; m< num_middle_node; m++ )
{
POINT x[2];
x[0] = middle[m].vertex;
for(n =1; n< m; n++) //因为此图为无向图，其i->j与j->i的距离是相等的
{
x[1] = middle[n].vertex;
if(intersect_closures(x) && neighbor(x))
{
adjlist[m][n]=line_length(x[0],x[1]);
adjlist[n][m]=adjlist[m][n];
}
else
{
adjlist[m][n]=infinite;
adjlist[n][m]=infinite;
}
}//end for n
adjlist[m][n]=0; //此时 m == n
adjlist[n][m]=0;
}// end for m
for (m = 0 ; m<= num_middle_node; m++)
{
path[m] = 0; //初始时各顶点均为0
d[m] = adjlist[0][m];
visited[m] = false;
}
d[0] =0;
visited[0] = true;
for (i =1; i<= num_middle_node; i++)
{
min = infinite;
for(m = 0 ; m<= num_middle_node; m++)
if (!visited[m] && ( d[m]< min))
{
n=m; min= d[m];
}
visited[n] = true;
for(m = 0 ; m<= num_middle_node; m++)
{
if (!visited[m] && (min+adjlist[n][m]< d[m]))
{
d[m] = min + adjlist[n][m];
path[m] = n;
}
}
}
int k;
k = num_middle_node;
num_dijkstra_path_node = 0;
cout<<"由dijkstra算法求得的最短路径的中间节点是";
while(k)
{
dijkstra_node[num_dijkstra_path_node++] = k; //存储从终点到起点经过的路径
cout << k<<",";
k = path[k];
}
dijkstra_node[num_dijkstra_path_node] =k;
cout <<k<<endl;
for (k=0;k<= num_dijkstra_path_node; k++)
{
vertex[k][0] = barrier[middle[dijkstra_node[num_dijkstra_path_node-k]].id1].vertex;
vertex[k][1] = barrier[middle[dijkstra_node[num_dijkstra_path_node-k]].id2].vertex;
}
cout << " 对应的最短路径是"<<d[num_middle_node]<<endl<<endl;
length_best_path = d[num_middle_node];
num_path_node = num_dijkstra_path_node;
}
double acs_improve()
{
double t[MAX][num_sections+1]; // 存储节点上的信息量
int path[num_ants][MAX]; //存储第k个蚂蚁在第n个节点的上的选择区域
bool path1[num_ants][MAX][num_sections+1]; //当第k个蚂蚁经过第n个节点的第m个区域时为true
double probability[MAX][num_sections+1]; //蚂蚁经过第n个节点的第m个区域的概率
double length_total[num_ants]; //存储每只蚂蚁所走相应路径的长度
bool best_path[MAX][num_sections+1];
double d[MAX][num_sections+1]; //能见度
bool flag; //标记此次循环中是否找到了更优解
double currentbest; //记录每次循环中的路径最优值
double deviation[num_cycle]; //记录每次循环中的最优值与全局最优值的差值
int p,q,w;
for( p =0;p< 2*(num_path_node-1);p++) //初始化各节点上的信息量
for ( w =0;w<= num_sections;w++) //num_path_node 用floyd算法求出的最短路径上的顶点数（包括起点和终点，且是从0开始计数）
{ //但是用蚁群算法只要调节除起点和终点以外的点，这些点的总数是num_path_node+1-2
t[p][w]=c; //在记录路径时，只考虑之间需要调节的路径点,他们在middle中相应的下标为此时的下标＋1
if (w ==5)
best_path[p][w] = true;
else
best_path[p][w] = false;
}
for( p =0;p<num_ants;p++)
for (q = 0; q< 2*(num_path_node-1);q++)
for ( w =0;w<=num_sections;w++)
path1[p][q][w]=false;
for( p =0;p<num_ants;p++) //初始化各蚂蚁的初始路径，均为0.5
for ( q =0;q< 2*(num_path_node-1);q++)
{
path[p][q] = 5;
path1[p][q][5]=true;
}
int y[MAX]; //初始t参数
for ( q =0;q< 2*(num_path_node-1);q++)
y[q]=5;
int i,j,k,m;
for (i = 0; i < num_cycle ; i++)
{
flag= false;
// length_best_path = infinite;
currentbest = infinite;
for(k = 0; k< num_ants ; k++)
{
length_total[k] = 0;
POINT front,current; //current定义当前调节的节点，front定义当前节点的前一节点
front = start;
int n;
double high;
for (j = 0; j< 2*(num_path_node-1) ; j++)
{
n=0;
high=0;
for (m = 0; m <= num_sections ; m++) //计算各个区间的能见度
{
d[j][m] = ( num_sections- abs(m-y[j]) )/(num_sections+1.0); //能见度
probability[j][m]= pow(t[j][m],f)*pow(d[j][m],v); //各个顶点的信息量（信息激素＋能见度）
if (high < probability[j][m])
{
high = probability[j][m];
n=m; //n是最大值对应的num_section
}
if (m) probability[j][m]=probability[j][m]+probability[j][m-1];
} //end of m (0～11)
if (rand()%100 > 20)
{
double wheel_pos = probability[j][num_sections] * (rand()%100)/100;
n=0;
while (probability[j][n]<wheel_pos) n++;
}
path[k][j]=n; //第j个节点上，第k只蚂蚁选择第0.n处
path1[k][j][n] = true;
if ((j+1)%2 == 0)
{
double xishu;
xishu =0.1*path[k][j-1]+0.01*path[k][j];
current.x = vertex[(j+1)/2][0].x + (vertex[(j+1)/2][1].x - vertex[(j+1)/2][0].x)*xishu; //在当前路径点的调节中，蚂蚁选择的路径点
current.y = vertex[(j+1)/2][0].y + (vertex[(j+1)/2][1].y - vertex[(j+1)/2][0].y)*xishu;
// xishu = 0.1*path[k][j-2]+0.01*path[k][j-1]+0.001*path[k][j];
// current.x = vertex[(j+1)/3][0].x + (vertex[(j+1)/3][1].x - vertex[(j+1)/3][0].x)*xishu; //在当前路径点的调节中，蚂蚁选择的路径点
// current.y = vertex[(j+1)/3][0].y + (vertex[(j+1)/3][1].y - vertex[(j+1)/3][0].y)*xishu;
length_total[k] = length_total[k] + line_length(front,current); //计算第k只蚂蚁走过的总路径
front = current;
}
} //end of j（0～num 需要调整的节点数）
length_total[k] = length_total[k] + line_length(front,end); //计算第k只蚂蚁走过的总路径
// cout << "第"<<i<<"次循环 第"<<k<<"只蚂蚁所走的路径是"<<length_total[k]<<endl;
if (length_total[k] < length_best_path)
{
//更新路径节点＋路径长度；
flag = true;
for (j = 0; j< 2*(num_path_node-1) ; j++)
{
y[j]=path[k][j];
for (m = 0; m <= num_sections ; m++)
{
best_path[j][m] =path1[k][j][m];
}
}
length_best_path = length_total[k];
}
w= rand()%(num_path_node-1);
double xs;
POINT before,now;
before.x=start.x;
before.y=start.y;
double length=0;
for (q=0;q<num_path_node-1;q++)
{
if (q!=w)
{
xs=0;
for (int cy=0;cy<2;cy++)
xs=xs + y[2*q+cy]/pow(10,(cy+1));
}
else xs= rand()%100/100.0;
now.x = vertex[q+1][0].x+(vertex[q+1][1].x-vertex[q+1][0].x)*xs;
now.y = vertex[q+1][0].y+(vertex[q+1][1].y-vertex[q+1][0].y)*xs;
length = length+line_length(before,now);
before = now;
}// end for q
length = length+line_length(before,end);
if ( length < length_best_path)
{
for (int cx=0;cx<2;cx++)
{
xs=xs*10;
y[2*q+cx]=xs;
}
length_best_path = length;
length_total[k] = length;
}//end if
/*
w= rand()%(num_path_node-1)*3;
// p= rand()%(num_sections+1);
// for (w=0; w<num_path_node-1;w++)
// {
for(p =0;p<=num_sections;p++)
{
if (p!=y[w])
{
POINT before,now;
before.x=start.x;
before.y=start.y;
double length=0;
for (q=0;q<num_path_node-1;q++)
{
double xs=0;
for (int cy=0;cy<3;cy++)
{
if (3*q+cy == w)
xs=xs + y[p]/pow(10,(cy+1));
else
xs=xs + y[3*q+cy]/pow(10,(cy+1));
}
now.x = vertex[q+1][0].x+(vertex[q+1][1].x-vertex[q+1][0].x)*xs;
now.y = vertex[q+1][0].y+(vertex[q+1][1].y-vertex[q+1][0].y)*xs;
length = length+line_length(before,now);
before = now;
}// end for q
length = length+line_length(before,end);
if ( length < length_best_path)
{
y[w]=p;
length_best_path = length;
length_total[k] = length;
}//end if
}//end if
}//end for p
// }//end for w
*/
/* if(currentbest > length_total[k])
{
currentbest = length_total[k];
}
*/
/* for( p =0;p<num_path_node-1;p++) //更新各点的信息数
for ( w =0;w<= num_sections;w++)
t[p][w]=t[p][w]*s+0.1*c;
*/
} //end of k（蚂蚁的数量）
/* for (j = 0; j< num_path_node-1 ; j++)
for (m = 0; m <= num_sections ; m++)
{
if (best_path[j][m]) y[j]=m;
}
*/
// deviation[i]=currentbest-length_best_path;
for(p =0;p<2*(num_path_node-1);p++) //更新各点的信息数
{
for (w =0;w<= num_sections;w++)
{
t[p][w]=t[p][w]*s+0.1*c;
}
}
/*
for(int p =0;p<num_path_node-1;p++) //更新各点的信息数
{
for (int w =0;w<= num_sections;w++)
{
t[p][w]=t[p][w]*s+0.1*c;
if (best_path[p][w])
t[p][w]=t[p][w]+e*Q/length_best_path; //e是一常量
for (k = 0; k<num_ants; k++)
{
if (path1[k][p][w])
t[p][w]=t[p][w]+Q/length_total[k]; //Q是一常量
}//end for k
}//end for w
}//end for p
*/
if(flag)
{
for(p =0;p<num_path_node-1;p++) //更新各点的信息数
{
t[p][y[p]]=t[p][y[p]]+e*Q/length_best_path; //e是一常量
}
}
// cout <<length_best_path<<" ";
cout << "第"<<i<<"次循环中的最短路径是 "<<length_best_path<<" "<<y[0]<<" "<<y[1]<<" "<<y[2]<<" "<<y[3]<<" "<<y[4]<<" "<<y[5]<<" "<<y[6]<<" "<<y[7]<<" "<<y[8]<<" "<<y[9]<<" "<<y[10]<<" "<<y[11]<<endl;
}//end of i (循环的次数)
/*
cout <<endl;
for(i=0; i<=num_cycle; i++)
{
cout << deviation[i] <<" ";
}
*/
return(length_best_path);
}
double acs()
{
double t[MAX][num_sections+1]; // 存储节点上的信息量
int path[num_ants][MAX]; //存储第k个蚂蚁在第n个节点的上的选择区域
bool path1[num_ants][MAX][num_sections+1]; //当第k个蚂蚁经过第n个节点的第m个区域时为true
double probability[MAX][num_sections+1]; //蚂蚁经过第n个节点的第m个区域的概率
double length_total[num_ants]; //存储每只蚂蚁所走相应路径的长度
bool best_path[MAX][num_sections+1];
double d[MAX][num_sections+1]; //能见度
bool flag; //标记此次循环中是否找到了更优解
double currentbest; //记录每次循环中的路径最优值
double deviation[num_cycle]; //标准偏差
double mean[num_cycle]; //记录每次循环平均值
int p,q,w;
for( p =0;p< num_path_node-1;p++) //初始化各节点上的信息量
for ( w =0;w<= num_sections;w++) //num_path_node 用floyd算法求出的最短路径上的顶点数（包括起点和终点，且是从0开始计数）
{ //但是用蚁群算法只要调节除起点和终点以外的点，这些点的总数是num_path_node+1-2
t[p][w]=c; //在记录路径时，只考虑之间需要调节的路径点,他们在middle中相应的下标为此时的下标＋1
if (w ==5)
best_path[p][w] = true;
else
best_path[p][w] = false;
}
for( p =0;p<num_ants;p++)
for (q = 0; q< num_path_node-1;q++)
for ( w =0;w<=num_sections;w++)
path1[p][q][w]=false;
for( p =0;p<num_ants;p++) //初始化各蚂蚁的初始路径，均为0.5
for ( q =0;q< num_path_node-1;q++)
{
path[p][q] = 5;
path1[p][q][5]=true;
}
int y[MAX]; //初始t参数
for ( q =0;q< num_path_node-1;q++)
y[q]=num_sections/2;
int i,j,k,m;
for (i = 0; i < num_cycle ; i++)
{
flag= false;
length_best_path = infinite;
currentbest = infinite;
mean[i]=0;
deviation[i]=0;
for(k = 0; k< num_ants ; k++)
{
length_total[k] = 0;
POINT front,current; //current定义当前调节的节点，front定义当前节点的前一节点
front = start;
int n;
double high=0;
for (j = 0; j< num_path_node-1 ; j++ )
{
n=0;
for (m = 0; m <= num_sections ; m++) //计算各个区间的能见度
{
d[j][m] = ( num_sections- abs(m-y[j]) )/(num_sections+1.0); //能见度
probability[j][m]= pow(t[j][m],f)*pow(d[j][m],v); //各个顶点的信息量（信息激素＋能见度）
if (high < probability[j][m])
{
high = probability[j][m];
n=m; //n是最大值对应的num_section
}
if (m) probability[j][m]=probability[j][m]+probability[j][m-1];
} //end of m (0～11)
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -