赛题为:

最强大脑中的收官蜂巢迷宫变态级挑战,相信大家都叹为观止!最强大脑收官战打响后,收视率节节攀升,就连蚁后也不时出题难为一下她的子民们。在动物世界中,称得上活地图的,除了蜜蜂,蚂蚁当仁不让。在复杂多变的蚁巢中, 蚂蚁总是能以最快、最高效的方式游历在各个储藏间(存储食物)。今天,她看完最新一期节目,又发布了一项新任务:小蚁同学,我需要玉米库的玉米,再要配点水果,去帮我找来吧。小蚁正准备出发,蚁后又说:哎呀,回来,我还没说完呢,还有若干要求如下:

1.小蚁同学,你需要尽可能以最少的花费拿到食物(附件图中路线上的数值表示每两个储物间的花费);

2.小蚁同学,你最多只能经过9个储藏间拿到食物(包含起止两个节点,多次通过同一节点按重复次数计算);

3.小蚁同学,你必须经过玉米间,水果间(附件图中标绿色节点);

4.别忘了,食蚁兽也在路上活动呢,一旦与食蚁兽相遇,性命危矣!不过小蚁微信群公告已经公布了敌人信息(附件图中标红色路段);

5.最后,千万别忘了,还有两段路是必须经过的,那里有我准备的神秘礼物等着你呢(附件图中标绿色路段)。

这下小蚁犯难了,这和它们平时找食物的集体活动规则不一样嘛,看来这次需要单独行动了。要怎么选路呢?小蚁经过一番苦思冥想,稿纸堆了一摞,啊,终于找到了!亲爱的同学们,你们能否也设计一种通用的路径搜索算法,来应对各种搜索限制条件,找到一条最优路径,顺利完成蚁后布置的任务呢?

photoshop培训,电脑培训,电脑维修培训,移动软件开发培训,网站设计培训,网站建设培训

注:

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。

 

http://www.cnblogs.com/jhmu0613/p/6930146.html