无向图最短路径

-.z.一、问题重述最强大脑中的收官蜂巢迷宫变态级挑战，相信大家都叹为观止！最强大脑收官战打响后，收视率节节攀升，就连蚁后也不时出题难为一下她的子民们。在动物世界中，称得上活地图的，除了蜜蜂，蚂蚁当仁不让。在复杂多变的蚁巢中，蚂蚁总是能以最快、最高效的方式游历在各个储藏间〔存储食物〕。今天，她看完最新一期节目，又发布了一项新任务：小蚁同学，我需要玉米库的玉米，再要配点水果，去帮我找来吧。小蚁正准备出发，蚁后又说：哎呀，回来，我还没说完呢，还有假设干要求如下：1.小蚁同学，你需要尽可能以最少的花费拿到食物〔附件图中路线上的数值表示每两个储物间的花费〕；2.小蚁同学，你最多只能经过9个储藏间拿到食物〔包含起止两个节点，屡次通过同一节点按重复次数计算〕；3.小蚁同学，你必须经过玉米间，水果间〔附件图中标绿色节点〕；4.别忘了，食蚁兽也在路上活动呢，一旦与食蚁兽相遇，性命危矣！不过小蚁微信群公告已经公布了敌人信息〔附件图中标红色路段〕；5.最后，千万别忘了，还有两段路是必须经过的，那里有我准备的神秘礼物等着你呢(附件图中标绿色路段)。这下小蚁犯难了，这和它们平时找食物的集体活动规则不一样嘛,看来这次需要单独行动了。要怎么选路呢？小蚁经过一番苦思冥想，稿纸堆了一摞，啊，终于找到了！亲爱的同学们，你们能否也设计一种通用的路径搜索算法，来应对各种搜索限制条件，找到一条最优路径，顺利完成蚁后布置的任务呢？注：1、蚁巢，有假设干个储藏间〔附件图中圆圈表示〕，储藏间之间有诸多路可以到达(各储藏间拓扑图见附件);2、节点本身通行无花费；3、该图为无向图，可以正反两方向通行，两方向都会计费，并且花费一样；4、起止节点分别为附件图中S点和E点。5、最优路径：即满足限制条件的路径。图1二、模型假设与符号说明2.1模型假设1.因为题目中并未明确给出是否是从起始点开场到达终止点，即从s到e，为防止歧义、方便计算，假设每条路径都是从起点到终点；2.下文中说到的点或点数均代表存储室或存储室数量；3.通过图1各路段关系，可以假设，为得到最优路径，不会再从N1、N2、N3走回起点。2.2符号说明符号含义N最多经过的点的个数x经过的第n个点P第j个集合Pj个点中的第i的数值，即将要走向的下一个点P第j个点所有与其相邻的点的集合APC和第k个点相邻的点的总数i走过的第k个点集合元素的下标，从0到APCi-F走第k条路所需要的总费用f从编号为i的点到编号为j的点的费用，即表3i行j列对应的值表1三、问题分析3.1整体分析题目的总体思路是在各种约束条件下求出一条从起点到终点的最优路径，最优可以说是有两个方面：第一是经过的储藏室即经过的点最好，题目中给定为9个，第二是在途中花费的费用最少。基于以上分析，我们决定建立无向图最优路径模型，从通过的点数和费用进展优化。3.2约束条件分析〔1〕题目中并未明确给出是从起始点到达终点〔即图中给出的s和e〕，为了不产生歧义，以及方便计算，我们在假设中规定该路线是从起始点到达终点〔即图1中给出的s和e〕。〔2〕最多只能经过9个储藏室〔即9个点〕〔3〕必须经过两条绿色的路线，即必须经过N2、N4、N13、N14，并且N2和N3相邻，N13和N14相邻。〔4〕必须经过水果间和玉米间，即必须经过N7和N12。〔5〕不能经过有食蚁兽的红色路段，可以有两种解决方法，第一：即N11和N12不能相邻出现，第二：N11和N12之间没有连线，没有通路。〔6〕所有的路都是可以双向通行的。3.3可行性分析经过约束条件的分析，我们发现，有八个特殊点〔N2、N4、N7、N12、N13、N14、〕必须经过，则按照题目要求，只能再选择一个非特殊点通过以完成该路径，通过图1分析，这显然是无法完成的，经过进一步的分析与计算，我们发现在满足以上约束条件的情况下，最少需要通过11个点才能完成任务〔相关计算与证明在4.3.1中给出〕。四、模型建立与求解4.1模型准备影响实际问题的因素很多，要解决实际问题就要建立适当的模型，既要把所得模型的次要因素忽略，否则所得模型会因为构造复杂而失去可解性同时又不能把与实质相关的因素忽略掉，而造成所得模型不能够正确反映实际情况而失去可靠性。但假设是无法取得实际问题的最优解，只能在牺牲次要因素的条件下获得最优近似解。因此要对实际问题进展简化、确定变量和参数，并用*些"规律〞建起变量与参数间的数学模型。影响路线选择因素很多：经过储藏间数量限制、必经节点与路径、危险路径阻碍、费用最少。对于问题中两种不同决策变量最少节点与最少花费建立两种模型分别求出在侧重点不同情况下的最优解。经过以上的问题分析，针对此问题应该建立一个无线图最优路径模型。4.2模型的建立与求解此模型是要找出从起始点到终点满足约束条件，并且使得经过的点最少、费用最少，因此其核心表达式是一个由一个点指向另一个点的路线。4.2.1确定所有路线表达式x式〔1〕0式〔2〕i∈公式说明：式〔1〕表示从x0到xN-1的所有点，用有向箭头连起来，表示一条经过了N的点的路径，起始点显而易见为x 式〔2〕与式〔1〕对应，Pj[i]对应xn，Pj[i]为xn确实定方法。比方此时走到x2点，则下一个点确实定必然与x2有关，具体由P2集合中的第i〔i从0到APC2-1公式意义： 从x0开场，遍历与它相邻的所有点，并且每个点都尝试走，走到下一个点，同样遍历与其相邻的所有点，重复上述步骤，直到走到第N个点〔即编号为N-1的点〕，便不再继续走，或者没有走到第N个点，而是已经走到了终点即e，也不再继续走。这样可以找到所有走过点数为N或者能到达终点的路径点编号对应符号与其相邻点的总数列举相邻的点01234560P31231P32492P413453P425674P412595P72346910126P735781213147P33688P46714159P5145101110P459111211P39101612P55610131613P66121415161714P468131515P4813141716P41112131717P00表2各节点信息表4.2.2对路径的筛选〔添加程序〕〔1〕限制经过的最多点数为了保证程序能够正常、快速地运行，在第一步寻找路径中其实已经限制了最多经过的点数，走到第N个点〔即编号为N-1的点〕，便不再继续走，或者没有走到第N个点，而是已经走到了终点即e，也不再继续走，这样已经保证了每条路走过的点数都限制在N个以内。〔2〕经过N7和N12 每条路走完之后，遍历一下所有的点，看看其中是否有7和12这两个值，没有的话此路不满足约束条件，否则继续检验其他条件。〔3〕经过两条绿的路线 首先可以确定2、4、13、14必须通过，就是必须有这两个数值，其次，2和4,13和14还必须相邻出现，才能说明通过绿的路段。〔4〕不经过红的的路线，两种解决方案 第一：直接切断N11和N12间的路线，在表2中编号为11的节点中不添加12这个相邻节点，在编号为12的节点中不添加11这个相邻节点，这样所得到的路线绝对不会经过红色路段。第二：每条路走完之后，遍历一下所有的点，寻找N12与N13是否相邻出现过，假设出现过，这说明经过了红色路段，否则，未经过，符合约束条件，继续检验其他条件。 注：本算法用第一种解决方案实现！费用分析经过上述分析与计算，已经求得了满足所有约束条件并且经过的点尽量少的路径，接下来还需要考虑每条路径的费用。〔1〕费用计算设有一条符合条件的路径如下x式〔3〕其费用F式〔4〕〔2〕费用排序将所得到的路径按照计算的费用升序排序，每条路的费用将会一目了然，结合通过的点数、费用选取最优路径。点编号0123456789101112131415161700311000001000000001301010000000000000211012100000000000031010022100000000004012101000100000000500120010031030000060002010120002430007000100101000000000800000021000000130090400130000110000001000000100010120000011000000000110100010120000032000210200101300000040000020122114000000301000010100150000000030000210041600000000000111200117000000000000010410表3费用表算法设计 核心代码如下：voidfindMoreShortPath(intinde*,int*pointCount){inti; //将第一个点编号写入路径信息实例 *(allPath[pathNum].pathPoint+(*pointCount)-1)=inde*; //如果已经到最后一个点或者走过的点数超过POINT_COUNT_MA*，对此路径进展处理 if(*pointCount>=POINT_COUNT_MA*||inde*==END_INDE*) { //如果此时最后一个点的编号为最后一个点的，则继续对此路径进展处理 if(inde*==END_INDE*) //判断此路径是否满足约束条件，是则继续 if(checkPointOfPath()) { //给pathNum先加一，以防止覆盖上一条符合条件的路径pathNum++; //因为不会再从头开场遍历，下一条路的前半局部与上一条路是一样的 //因此将上一条路径的信息赋给下一条路径，分叉之后的路径会在上边被修改 for(i=0;i<POINT_COUNT_MA*;i++) *(allPath[pathNum].pathPoint+i)=*(allPath[pathNum-1].pathPoint+i); } }else //如果不满足以上条件，继续向前走 for(i=0;i<point[inde*].adjoinPointCount;i++) { //走过的点数加1 *pointCount=*pointCount+1; //继续找findMoreShortPath(*(point[inde*].adjoinPoint+i),pointCount); //找完一次，走过的总点数减1 *pointCount=*pointCount-1; }}模型求解使用C语言编写程序求解，设计无向图最短路径算法，其核心是通过递归的思想求解。注：程序运行结果详见4.3对模型的检验！ 1.经过点数最少的路径有两条，费用分别为14和16，路径如下：s->2->4->5->12->6->7->8->14->13->e式〔5〕s->2->4->5->12->6->7->6->14->13->e式〔6〕2、费用最少的路径有两条，第一条经过12个点，第二条经过13个点，费用都为13，路径如下：s->2->4->5->6->7->8->14->13->12->16->e式〔7〕s->2->5->4->2->3->7->8->14->13->12->16->e式〔8〕4.3对模型的检验1.将N置为9或10时，程序运行结果如下：图3当设置N为9或10时均未找到符合条件的路径，说明经过最少点数为9或10时均无法完成此任务，而设置为11及以更多时，会找到符合条件的路径。这些检验结果验证了3.3可行性分析的正确性，按照原题约束条件，此题无解。2.将N置为11时，程序运行结果如下：图4 所以得出节点最少的路径有两条，费用分别为14和16：分别是s->2->4->5->12->6->7->8->14->13->e式〔9〕s->2->4->5->12->6->7->6->14->13->e式〔10〕3.将N置为12时，程序运行结果如下：图5 共找到73条符合条件的路径，其中经过11个点的路径已被标出，费用最少的情况为经过12个点，费用为13，可行路径有一条，为：s->2->4->5->6->7->8->14->13->12->16->e式〔11〕4.将N置为13时，程序运行结果如下：图6共找到1018条符合条件的路径，从结果可以看到，也能找到一条费用最少的路径，为13，路径如下：s->2->5->4->2->3->7->8->14->13->12->16->e式〔12〕4.将N置为14时，程序运行结果如下：图7 由此运行结果分析可知，经过14个点以及14个点以上，不会再有费用最少的路径。五、模型评价5.1模型优缺点5.1.1〔1〕算法中使用递归进展路径的检索，这样可以大大地提高代码的运行速度，即使数据比拟庞大，也能很快求解；〔2〕此模型看似是针对无向图求解最优路径的模型，实际上针对有向图同样适用，并且计算起来更加快速，如何推广位有向图最优路径的模型在5.2模型改良中讲到；〔3〕对此网络的规模增大缩小都是适用的，只需要对矩阵进展扩大，填入新增加的数据，修改少量参数；〔4〕能够列出除最优路径之外的其他很多路径，这为寻找其他适宜的路径提供了方便。5.1.2〔1〕暂时所有的数据都是直接从源代码中陆入进去的，这就需要使用此模型的人非常熟悉这个模型才能保证修改后的矩阵和常量不出问题；〔2〕算法中，对约束条件进过两条绿线的判断比拟繁琐，修改时容易出错；〔3〕模型中参加的影响因比素较少，在投放到实际问题中可能会出比拟大的偏差。5.2模型改良此模型此次计算是针对题目中的无向图来设计与填充数据的，但是只要稍加改动，便可以成为几个无向图最优路径算法。以此题目为例，假设只能从N2走到N4，则要修改的只有两个地方，而且是点的信息矩阵，将N4相邻点的个数减1，相邻点中将2除去，这样便实现的从N2到N4的单方向，其他节点也是一样。完成了对无向图的模型。参考文献[1]姜启源.数学模型.高等教育.2021.[2]ThmoasH.CormenCharlesE.LeisersonRonaldL.RivestCliffordStein著，殷建平，*云，王刚，*晓光，苏朋，邹恒明，王宏志译.算法导论.机械工业，2021.01.附录：源代码如下：#include<stdio.h>//最大允许通过的点数#definePOINT_COUNT_MA* 14//最后一个点的下标#defineEND_INDE* 17#defineBooleanint#defineTRUE 1#defineFALSE 0//节点构造体，包含相邻点的个数adjoinPointCount，以及对应的各个相邻点adjoinPointtypedefstructPOINT{intadjoinPointCount;intadjoinPoint[20];}POINT;//路径构造体，pathPoint用来保存符合条件的路径，以及费用allFaretypedefstructPATH{intpathPoint[POINT_COUNT_MA*];intallFare;}PATH;//在遍历路径时，符合条件的路径编号intpathNum=0;//保存所有的符合条件的路径信息PATHallPath[1000000];//点信息矩阵POINTconstpoint[18]={/*0*/ {3,1,2,3},/*1*/ {3,2,4,9},/*2*/ {4,1,3,4,5},/*3*/ {4,2,5,6,7},/*4*/ {4,1,2,5,9},/*5*/ {7,2,3,4,6,9,10,12},/*6*/ {7,3,5,7,8,12,13,14},/*7*/ {3,3,6,8},/*8*/ {4,6,7,14,15},/*9*/ {5,1,4,5,10,11},/*10*/ {4,5,9,11,12},/*11*/ {3,9,10,16},/*12*/ {5,5,6,10,13,16},/*13*/ {6,6,12,14,15,16,END_INDE*},/*14*/ {4,6,8,13,15},/*15*/ {4,8,13,14,END_INDE*},/*16*/ {4,11,12,13,END_INDE*},/*17*/ {0,0}};//费用矩阵intconstpathFare[18][18]={/* 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17*//*0*/ {0, 3, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},/*1*/ {3, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},/*2*/ {1, 1, 0, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},/*3*/ {1, 0, 1, 0, 0, 2, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},/*4*/ {0, 1, 2, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},/*5*/ {0, 0, 1, 2, 0, 0, 1, 0, 0, 3, 1, 0, 3, 0, 0, 0, 0, 0},/*6*/ {0, 0, 0, 2, 0, 1, 0, 1, 2, 0, 0, 0, 2, 4, 3, 0, 0, 0},/*7*/ {0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},/*8*/ {0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 1, 3, 0, 0},/*9*/ {0, 4, 0, 0, 1, 3, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0},/*10*/ {0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 2, 0, 0, 0, 0, 0},/*11*/ {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0},/*12*/ {0, 0, 0, 0, 0, 3, 2, 0, 0, 0, 2, 0, 0, 2, 0, 0, 1, 0},/*13*/ {0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 2, 0, 1, 2, 2, 1},/*14*/ {0, 0, 0, 0, 0, 0, 3, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0},/*15*/ {0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 2, 1, 0, 0, 4},/*16*/ {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 0, 0, 0, 1},/*17*/ {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 4, 1, 0},};//查找符合条件的路径voidfindMoreShortPath(intinde*,int*pointCount);//检查路径是否符合条件BooleancheckPointOfPath(void);//计算费用voidcaculateFare(void);//通过费用排序voidsortPathByFare(void);//显示路径信息voidshowPath(void);voidshowPath(void){inti,j; if(pathNum!=0) for(i=0;i<pathNum;i++) { for(j=0;j<POINT_COUNT_MA*;j++) if(j==0)printf("第%4d条路线：%2d",i+1,*(allPath[i].pathPoint+j)); elseprintf("->%2d",*(allPath[i].pathPoint+j));printf("总费用为：%d\n",allPath[i].allFare); } elseprintf("未找到符合的路径！\n");}voidsortPathByFare(void){inti,j; PATHtemp; for(i=0;i<pathNum;i++) { for(j=i;j<pathNum;j++) { if(allPath[i].allFare>allPath[j].allFare) { temp=allPath[i];allPath[i]=allPath[j];allPath[j]=temp; } } }}voidcaculateFare(void){inti,j; for(i=0;i<pathNum;i++) { for(j=0;j<POINT_COUNT_MA*-1;j++) { //假设碰到两个值相等的点，说明已经到终点，不再累加费用 if(*(allPath[i].pathPoint+j)!=*(allPath[i].pathPoint+j+1))allPath[i].allFare+=pathFare[*(allPath[i].pathPoint+j)][*(allPath[i].pathPoint+j+1)]; } }}BooleancheckPointOfPath(void){inttemp; Booleancontain24=FALSE,contain7=FALSE,contain12=FALSE,contain1314=FALSE; for(temp=0;temp<POINT_COUNT_MA*;temp++) { //判断是否经过7和12 switch(*(allPath[pathNum].pathPoint+temp)) { case7:contain7=TRUE; break; case12:contain12=TRUE; break; } //判断是否经过两条绿线 if((*(allPath[pathNum].pathPoint+temp)==2) &&(*(allPath[pathNum].pathPoint+temp+1)==4)) contain24=TRUE; if((*(allPath[pathNum].pathPoint+temp)==4) &&(*(allPath[pathNum].pathPoint+temp+1)==2)) contain24=TRUE; if((*(allPath[pathNum].pathPoint+temp)==13) &&(*(allPath[pathNum].pathPoint+temp+1)==14)) contain1314=TRUE; if((*(allPath[pathNum].pathPoint+