AStar算法解决野人渡河问题

《AStar算法解决野人渡河问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、江南大学物联网工程学院实验报告课程名称人工种能实验名称A*算法解决8数码问题实验日期2018320班级计科1501姓名周启航学号1030415127一、实验目的:问题描述：设有3个传教士和3个野人来到河边，打算乘一只船从左岸渡到右岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡河过去？试采用A*算法编一程序实现这一搜索过程。二、算法描述：1.状态描述以河岸左边传教士的数目M,野人的数目C,船是否在B作为一个三元组作为一个状态即(M,C,B)o2.启发函数设计以现在的状态到FI的

2、状态所需的最少步数作为启发函数，即为h()二M+C-2*B。3・规则的判断条件岸边传教丄不能少于野人个数，即M＞二C,或者船在左岸时B=l。4.算法流程图5.核心代码操作算子：voidAstar(){while(!Q.empty())Q.popO;PathNodexlear();memset(st,-1,sizeof(st));PathNode.push_back(Node(M,C,B,0,-1));Q.push(AstarNode(0,PathNode[0]));st[M][C][B]=0;intm,c,b,flag,id;while(!Q.empty())

3、{AstarNodeas=Q.topO;Q.popO;//printf(n——%d%d%d%d%d——fas.f,as.g,as.node.m,as.node.c,as.node.b);if(as.node.m==0&&as.node.c==0){printf(u渡河方案如下:n);printf(M(M,C,B)n);printPath(as.node.id);printf(”可以安全渡河，来回最少需%d次便可!n,as.g);Safe=true;return;}if(as.node.b==I)flag=-1;elseflag=1;b=1-a

4、s.node.b;id=PathNode.size()-1;for(inti=0;i<5;++i){m=as.node.m+flag*add[i][0];c=as.node.c+flag*add[i][l];if(OK(m,c,b)){++id;st[m][c][b]=as.g+1;PathNode.push_back(Node(m,c,b,id,as.node.id));Q.push(AstarNode(as.g+1,PathNode[id]));主函数：intmain(intargc,char*argv[]){inti=3;M=C=i;B=1;K=2;pr

5、intf（nM（＞道士）二%d人C（野人）=%d人K（限剩=%d人B（船）=%d条”,M,C,K,B）;Safe=false;Astar（）;if（!Safe）{printf（n没有方案可以安全渡河!!!"）;}putchar（lO）;return0;}三、实验结果:教师签名四、实验心得：这次实验还是设计A*算法，整体的结构设计和上次没什么太大的出入，所以并没有什么困难的地方。只要找准状态设计和启发函数就问题不人了。教师评价优良