中兴捧⽉算法精英挑战赛-迪杰斯特拉派
赛题为：
最强⼤脑中的收官蜂巢迷宫变态级挑战，相信⼤家都叹为观⽌！最强⼤脑收官战打响后，收视率节节攀升，就连蚁后也不时出题难为⼀下她的⼦民们。在动物世界中，称得上活地图的，除了蜜蜂，蚂蚁当仁不让。在复杂多变的蚁巢中，蚂蚁总是能以最快、最⾼效的⽅式游历在各个储藏间（存储⾷物）。今天，她看完最新⼀期节⽬，⼜发布了⼀项新任务：⼩蚁同学，我需要⽟⽶库的⽟⽶，再要配点⽔果，去帮我来吧。⼩蚁正准备出发，蚁后⼜说：哎呀，回来，我还没说完呢，还有若⼲要求如下：
1.⼩蚁同学，你需要尽可能以最少的花费拿到⾷物（附件图中路线上的数值表⽰每两个储物间的花费）；
2.⼩蚁同学，你最多只能经过9个储藏间拿到⾷物（包含起⽌两个节点，多次通过同⼀节点按重复次数计算）；
3.⼩蚁同学，你必须经过⽟⽶间，⽔果间（附件图中标绿⾊节点）；
4.别忘了，⾷蚁兽也在路上活动呢，⼀旦与⾷蚁兽相遇，性命危矣！不过⼩蚁公告已经公布了敌⼈信息（附件图中标红⾊路段）；
5.最后，千万别忘了，还有两段路是必须经过的，那⾥有我准备的神秘礼物等着你呢(附件图中标绿⾊路段)。
这下⼩蚁犯难了，这和它们平时⾷物的集体活动规则不⼀样嘛，看来这次需要单独⾏动了。要怎么选路呢？⼩蚁经过⼀番苦思冥想，稿纸堆了⼀摞，啊，终于到了！亲爱的同学们，你们能否也设计⼀种通⽤的路径搜索算法，来应对各种搜索限制条件，到⼀条最优路径，顺利完成蚁后布置的任务呢？
注：
1、蚁巢，有若⼲个储藏间（附件图中圆圈表⽰），储藏间之间有诸多路可以到达(各储藏间拓扑图见附件);
2、节点本⾝通⾏⽆花费；
3、该图为⽆向图，可以正反两⽅向通⾏，两⽅向都会计费，并且花费相同；
4、起⽌节点分别为附件图中S点和E点。
5、最优路径：即满⾜限制条件的路径。
⼀、算法思路：
我们把题⽬看成旅⾏商问题，然后⽤遗传算法求出最优解或者次优解。
⼆、模型建⽴
本题属于单源单点间附加必经点、必经边的问题，为将本题转化为旅⾏商问题，加上还需⼀条从源点S到终点T的附加边，该边的花费为源点到终点的花费，然后将该边当做⼀条必经边来处理。对于必经边，
采⽤将必经边也处理成⼀个特殊的必经点的⽅法，该特殊必经点包含起点和终点。在染⾊体中只出现必经边u-v上的⼀点，如果是u则代表从必经边的u点进⼊，从v点出去；如果是v则代表从必经边的v点进⼊，从u点出去，然后本题就可以转化为存在⼀定数量必经点的旅⾏商问题。
初始化：⽣成SUM个初始解，初始解1为贪⼼解，其余SUM-1个解均为随机⽣成。贪⼼解的思想是，离源点S越近的必经点或必经边，越先放进解中，如例图，离远点最近的是属于必经边2-4的点2，所以将必经点2放进初始解（隐含了2-4这条边），接下来是点7，将其放进解中，然后是属于必经边（13-14）的点14，将点14放进初始解中（隐含了14-13这条边），然后是点12，最后把终点T到源点S的边放进去，⽣成第⼀个贪⼼的初始解，为2(4)-7-14(13)-12-17(0)；其余SUM-1个初始解均为随机⽣成必经点必在解中，必经边中的⼀个点u在解中，隐含了u-v这条边，例如：上节随机初始化的另⼀组解4 13 12 7 17，其中点4代表路径4-2,13代表路径13-14，17代表路径17-0。
个体评价：以贪⼼⽣成的解2(4)-7-14(13)-12-17(0)为例：染⾊体中第⼀个基因是点2，属于必经边，现加上边2-4的权值，然后加上4到下⼀个结点7的权值；结点7不是必经边，直接加上结点7到下⼀个点14的权值；结点14属于必经边，先加上14-13的权值，再加上结点13-12的权值；结点12不是必经边，直接加上结点12到下⼀结点17（即终点）的权值；结点17属于必经边，先加上结点17到结点0（即源点）的权值，然后加上结点0到2的权值；然后最后减去源点到起点的权值，即为此路径的花费，上述贪⼼解的花费为13。
对于该染⾊体经历的结点数量使⽤的⽅法是提前通过弗洛伊德算法得到的最短路径信息得到所有必经点之间两两的最⼩花费经历结点数，然后对某⼀必经点组合，只需要遍历⼀遍所有节点然后加起来，就可以得到改染⾊体所经历的结点数；
选择运算：因为通过交叉得到的⼦代总是⼩于等于⽗代，所以这⾥直接选择交叉变异产⽣的⼦代。
记录最优：有两个记录最优的⽅⾯，⼀⽅⾯是记录满⾜结点数满⾜最少结点要求的最优解，⼀个室结点数不满⾜最少节点数的次优解；
交叉运算：选择两个参加交叉的染⾊体作为⽗代，例如：
A=2(4)-7-14(13)-12-17(0)
B=12-7-13(14)-4(2)-17(0)
染⾊体A的cost为13，染⾊体B的cost为19；⾸先⽐较结点4与7的权值为3，12与7之间的权值也为3；就以2(4)为头结点，将初始解右转动为(染⾊体B中没有特殊节点2(4)，但是因为2与4均属于必经边2-4，在此将染⾊体B中的4(2)替换成2(4)代表从2点进⼊，然后从4点出)：
A=2(4)-7-14(13)-12-17(0)
B=2(4)-17(0)-12-7-13(14)
然后⽐较4与7的权值为3，4与17的权值为4，所以就有：
A=*-7-14(13)-12-17(0)
B=*-7-13(14)-17(0)-12
由此规则计算可得：
O=2(4)-7-14(13)-12-17(0)
我们本来是2个不同的解，现在得到了⼀个⽐两个解都优的解，总不能让原来的两个解都等于现在的这个局部最优解吧，这样不利于下次交叉，我们可以⽤随机旋转的⽅法改变另外⼀个解的路径：Rotate(q.info, NUMmustp, rand() % NUMmustp);
：只需要在⼀个解中随机的选择两个基因，然后交换它们即可。
三、算法实现结果分析
读图（邻接表），将⾷蚁兽所在的路径花费设为0x3f3f3f，既不经过此路径（剪枝）。
1.弗洛伊德算法求取加权图中多源点之间最短路径
因为后期需要⼤量计算最短路径，选择迪杰斯特拉只能求取单源单汇之间的最短路径，多次调⽤的话时间消耗太⼤。所以这⾥使⽤弗洛伊德算法⼀次求取，后⾯直接调⽤。迪杰斯特拉算法复杂度为主要依赖于最⼩优先队列的实现，使⽤简单数组算法复杂度为O（V^2），使⽤⼆叉堆可以优化到O(ElgV)，使⽤斐波那契堆可以优化到O(VlgV+E)；⽽弗洛伊德时间复杂度为O(N^3)，空间复杂度为O(N^2)。当图的规模⽐较⼤，并且必经点、必经边⽐较多的话，使⽤弗洛伊德算法可以⼤规模减少时间。
2.初始化初始种
第⼀个解为贪⼼求得，其余SUM个解为随机⽣成；因为例图⾥⾯的点⽐较少，所以使⽤贪⼼求取的路径已经是局部最优了。
3.遗传全局优化
因为图⽐较⼩，通过贪⼼就直接获得最优了，所以这⾥我统计了每⼀代所有染⾊体的权值和的平均，种规模SUM为10000，制成图。从上图可以看出来通过遗传可以很快收敛到最优附近，然后利⽤遗传的全局寻优能⼒寻最优解。
4.输出
针对题中所给⽤例，通过我们的解题算法，在满⾜所有要求的情况下并未搜索⼀条最优的路径，经统计每⼀代最终的平均花费是逐渐变⼩并最终稳定在13，最终输出⼀组次优路径，路径为：0->2->4->5->6->7->8->14->13->12->16->17，经过12个点，花费为13。
我的算法问题还很⼤，有很多东西没考虑，求⼤佬不⿊；
#include<stdio.h>
#include <stdlib.h>
#include <memory.h>
#define MAXN 10000
#define INF 0x3f3f3f
#define SUM 10 //总共的染⾊体数量
#define MAXloop 10000 //最⼤循环次数
#define error 0.01 //若两次最优值之差⼩于此数则认为结果没有改变
#define crossp 0.7 //交叉概率
#define mp 0.1 //变异概率
int numnode = 0;
int dis[MAXN][MAXN];
int pathmatirx[MAXN][MAXN];
int numofnodepath[MAXN][MAXN];
int S ; //起点
int T ; //终点
int mustp[MAXN];
int nummustp = 0; //必经点的个数，必经边算两个必经点
int NUMmustp = 0; //个体中的染⾊体个数
int ret[1000];
int ptri = 0;
struct gen //定义染⾊体结构
{
int info[MAXN]; //染⾊体结构，表⽰从0开始经过这个染⾊体结构之后，到达T
int cost; //次染⾊体所对应的适应度函数值，在本题中为表达式的值
int numofnode;
};
struct gen gen_group[SUM];//定义⼀个含有20个染⾊体的组
struct gen gen_result; //记录次优的染⾊体
struct gen gen_result2; //记录最优的染⾊体
int result_unchange_time; //记录在error前提下最优值为改变的循环次数
struct mustedge{
bool flag;
int u;
int v;
}ismustedge[MAXN];
//**************************************普通函数声明*****************************//
void reading(); //读图
void floyd(); //弗洛伊德求最短路径
void init(); //初始化
int randsign(float p); //按照概率p产⽣随机数0、1，其值为1的概率为p
int randbit(int i,int j); //产⽣⼀个在i，j两个数之间的随机整数
void findway( int a , int b );
int numofnode( int i , int j );
//**************************************遗传函数声明*****************************//
void gen_swap(gen *a,gen *b); //结构体交换
void gen_quicksort(gen *number,int left,int right); //种排序
void initiate(); //初始化函数，主要负责产⽣初始化种
void evaluation(int flag); //评估种中各染⾊体的适应度，并据此进⾏排序
void Cross_group( gen &p, gen &q); //交叉函数
void selection(); //选择函数
int record(); //记录每次循环产⽣的最优解并判断是否终⽌循环
void Varation_group(gen group[]); //变异函数
int Search_son( int path[], int len, int city);
int Search_son1( int path[], int len, int city);
void Rotate(int path[],int len, int m);
void evaluation(int flag)
{
int i , j , node1 , node2 ;
struct gen *genp;
genp = gen_group;
for(i = 0 ; i < SUM ; i++)//计算各染⾊体对应的表达式值
{
genp[i].cost = 0;
int cost = 0;
int num = 0;
for( j = 0 ; j < NUMmustp - 1 ; ++j ){
if( !ismustedge[genp[i].info[j]].flag ){
node1 = genp[i].info[j];
node2 = genp[i].info[j + 1];
cost += dis[node1][node2];
num += numofnodepath[node1][node2];
}
else{
node1 = genp[i].info[j];
node2 = ismustedge[genp[i].info[j]].v;
cost += dis[node1][node2];
node1 = genp[i].info[j + 1];
cost += dis[node2][node1];
num += 1;
num += numofnodepath[node2][node1];
}
}
if( !ismustedge[genp[i].info[NUMmustp - 1]].flag ){
node1 = genp[i].info[NUMmustp - 1];
node2 = genp[i].info[0];
cost += dis[node1][node2];
num += numofnodepath[node1][node2];
}
else{
node1 = genp[i].info[NUMmustp - 1];
node2 = ismustedge[genp[i].info[NUMmustp - 1]].v;
cost += dis[node1][node2];
node1 = genp[i].info[0];
cost += dis[node2][node1];
num += 1;
num += numofnodepath[node2][node1];
}
cost -= dis[T][S];
genp[i].cost = cost;
genp[i].numofnode = num;
}
gen_quicksort(genp ,0 ,SUM-1 ); //对种进⾏重新排序
}
void calnodenum(){
int i , j;
for(i = 0 ; i < nummustp ; i++) {
for(j = 0 ; j < nummustp; j++ ) {
if(mustp[i] == mustp[j]){
numofnodepath[mustp[i]][mustp[j]] = 0;
}
else{
numofnodepath[mustp[i]][mustp[j]] = numofnode(mustp[i] , mustp[j]); }
怎么用printf输出bool函数值/*if(i == j){
numofnodepath[i][j] = 0;
}
else{
numofnodepath[i][j] = numofnode(i , j);
}*/
}
}
}
int main(){
int i , j;
reading();
floyd();
calnodenum();
result_unchange_time = 0;
st = INF;
st = INF;
initiate();
evaluation( 0 ); //对初始化种进⾏评估、排序
for( i = 0 ; i < MAXloop && result_unchange_time < 10 ; i++ )
{
printf("第%d次迭代：",i);
for(int ii = 0 ; ii < SUM ; ++ii ){
printf("染⾊体%d: ",ii);
for(j = 0 ; j < NUMmustp; ++j ){
printf("%d ",gen_group[ii].info[j]);
}
printf(" 花费为：%d，结点数为：%d\n",gen_group[ii].cost,gen_group[ii].numofnode); }printf("\n");
float temp = 0;
for (j = 0; j < SUM; j+= 1)
{
temp += gen_group[j].cost;
}
printf("本代平均花费为：%f\n",temp/SUM);
printf("\n\n\n\n");
if (gen_group[0].cost < st)
{
result_unchange_time = 0;
memcpy(&gen_result, &gen_group[0], sizeof(gen));
}
else{
result_unchange_time++;
}
for( j = 0; j < SUM ; ++j){
if(gen_group[j].numofnode <= 9 && gen_group[j].cost < st){
result_unchange_time = 0;
memcpy(&gen_result2, &gen_group[0], sizeof(gen));
}
}
for (j = 0; j < SUM / 2; j+= 1)
{
Cross_group(gen_group[j], gen_group[ SUM - j -1]);
}
evaluation( 0 );
Varation_group(gen_group);
evaluation( 0 );
}
if(st != INF){
printf("有最优解：\n");
memcpy(&gen_result, &gen_result2, sizeof(gen));
}
else{
printf("⽆最优解，输出次优解：\n");
}
for(int ii=0;ii<NUMmustp - 1;ii++)
{
i = gen_result.info[ii];
j = gen_result.info[ii+1];
if(ismustedge[i].flag){
//printf(",V%d,",i);
ret[ptri++] = i;
findway(ismustedge[i].v , j);
}
else
findway(i , j);
}
i = gen_result.info[NUMmustp-1];
j = gen_result.info[0];
if(ismustedge[i].flag){
//printf(",V%d,",i);
ret[ptri++] = i;
findway(ismustedge[i].v , j);
}
else
findway(i , j);
//printf("\n");printf("\n");
int pos1 = Search_son1( ret, ptri, S);
Rotate(ret, ptri, pos1);
for( i = 0 ; i < ptri ; ++i){
printf("%d->",ret[i]);
}
printf("\n");
system("pause");
return0;
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论