《第7章 修道士野人问题.docx》由会员分享，可在线阅读，更多相关《第7章 修道士野人问题.docx（5页珍藏版）》请在三一文库上搜索。
1、第七章实验报告1.基本信息实验项目名称：修道士野人问题实验类型：综合性实验班级：090615学号：2009061502姓名：丛远东实验日期：6月232.问题描述河的左岸有N个野人和N个修道士以及一条小船，修道士们想用这条小船把所有的人都运到河的右岸，但又受到以下限制：l 修道士和野人都会划船，但船一次只能载C人。l 在任何岸边，为了防止野人侵犯修道士，野人数不能超过修道士数，否则修道士将会被野人吃掉。假定野人愿意服从任何一种过河的安排，本设计的主要任务是规划出一种确保修道士安全的过河方案。数据输入：修道士与野人的人数N和船可容纳的人数C。数据输出：过河的最优方法。3.数据结构设计 定义每一步运
2、送的结构体为struct stepint wild; /每次运送的野人数int monk; /每次运送的传道士数int sum; /每次运送的总人数（野人也算人啊） ;定义可行方案的容器为：vector AllSteps1;vector AllSteps2;定义左岸的状态的结构体为：struct nodeint wildLeft;/某一时刻左岸的野人数int monkLeft;/某一时刻左岸的传道士人数bool boat;/某一时刻船是否在左岸 true:船在左岸;false:船在右岸int parent; /某一节点的父节点;4.算法设计 修道士与野人问题的一般算法为：先求出所有的状态，此时
3、这个问题的求解便类似于寻路问题，已知两个结点和所有节点间的连接关系，求两结点之间的一的最短路径，简单地进行广度优先搜索即可。 为了得到最短路径，广搜的同时保证左岸一次运走的人越多越好（即左岸运多人优先），同时野人优先运走；右岸一次运走的人越少越好（即右岸运少人优先），同时修道士优先运走。1）首先求出所有的的运送方式，存入容器之中：for(int ii=N;ii=0;ii-) for(int jj=N;jj=0;jj-) if(ii+jj0) s.wild=ii;s.monk=jj; /coutii jjb.wild; else return a.sumb.sum; bool cmp2(step
4、 a,step b) /按照人数升序，修道士升序优先级排序 if(a.sum=b.sum) return a.monkb.monk; else return a.sumb.sum; 用sort函数排序：sort(AllSteps1.begin(),AllSteps1.end(),cmp1); sort(AllSteps2.begin(),AllSteps2.end(),cmp2);3）广搜最优解： 广搜之前，首先要写一个函数用来判断每一个状态是否合法，即野人会不会吃修道士： bool IsValid(node a)if(a.monkLeft0|a.wildLeftN|a.wildLeftN)/
5、判断是否合法return false;elseif(a.monkLeft=0|a.monkLeft=N)return true;elseif(a.monkLeft=a.wildLeft&(N-a.monkLeft)=(N-a.wildLeft)return true;return false;然后开始广搜，按照容器中的最优解进行搜索，如果满足，则存入队列，再对队列首元素进行搜索，看下一级元素是否满足合法状态，满足，再入栈，直到左岸的状态为0，0，false，判断函数为：bool IsFinish(node a)if(a.wildLeft = 0 & a.monkLeft = 0 & a.boat = false)return true;elsereturn false;修道士与野人的问题可能无解，不可解时给出提示。5.界面设计要求输入修道士与野人的人数N和船可容纳的人数C：6.运行、测试与分析1）当问题有解时无解时显示：注：此处的无解并非真正无解，而是在有限的阀值内无解。7.实验收获及思考通过此次实验，我又获得了不少知识。首先，我了解了容器的使用方法。其次，我复习了sort（）函数中cmp的写法。尤其是对于容器的sort函数，要使用begin（）函数和end（）函数。与数组的排序不相同。此外，我还了解了修道士野人问题的算法，使用广搜算法求得了最优解。