第7章 修道士野人问题.docxVIP

第七章实验报告1.基本信息实验项目名称：修道士野人问题实验类型：综合性实验班级：090615学号：2009061502姓名：丛远东实验日期：6月232.问题描述河的左岸有N个野人和N个修道士以及一条小船，修道士们想用这条小船把所有的人都运到河的右岸，但又受到以下限制：修道士和野人都会划船，但船一次只能载C人。在任何岸边，为了防止野人侵犯修道士，野人数不能超过修道士数，否则修道士将会被野人吃掉。假定野人愿意服从任何一种过河的安排，本设计的主要任务是规划出一种确保修道士安全的过河方案。数据输入：修道士与野人的人数N和船可容纳的人数C。数据输出：过河的最优方法。3.数据结构设计定义每一步运送的结构体为struct step{int wild;//每次运送的野人数int monk; //每次运送的传道士数int sum; //每次运送的总人数（野人也算人啊） };定义可行方案的容器为：vectorstep AllSteps1;vectorstep AllSteps2;定义左岸的状态的结构体为：struct node{int wildLeft;//某一时刻左岸的野人数int monkLeft;//某一时刻左岸的传道士人数bool boat;//某一时刻船是否在左岸 true:船在左岸;false:船在右岸int parent; //某一节点的父节点};4.算法设计修道士与野人问题的一般算法为：先求出所有的状态，此时这个问题的求解便类似于寻路问题，已知两个结点和所有节点间的连接关系，求两结点之间的一的最短路径，简单地进行广度优先有哪些信誉好的足球投注网站即可。为了得到最短路径，广搜的同时保证左岸一次运走的人越多越好（即左岸运多人优先），同时野人优先运走；右岸一次运走的人越少越好（即右岸运少人优先），同时修道士优先运走。1）首先求出所有的的运送方式，存入容器之中：for(int ii=N;ii=0;ii--) for(int jj=N;jj=0;jj--){ if(ii+jj=Cii+jj0){ s.wild=ii;s.monk=jj; //coutii jjendl; system(pause); s.sum=ii+jj; AllSteps1.push_back(s); AllSteps2.push_back(s);k++; } }2）对容器中数据进行排序：为了找到最优方案，按照算法，应该满足岸一次运走的人越多越好，同时野人优先运走；右岸一次运走的人越少越好，同时修道士优先运走。所以应当对容器中的可行状态进行排序。左岸的按照人数，修道士优先级降序排序，右岸的按照人数升序，修道士升序优先级排序。为了简化代码，我使用sort（）函数进行排序，写出相应的cmp函数：bool cmp1(step a,step b){//按照人数，修道士优先级降序排序 if(a.sum==b.sum) return a.wildb.wild; else return a.sumb.sum; }bool cmp2(step 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.wildLeft0||a.monkLeftN||a.wildLeftN)//判断是否合法return false;else{if(a.monkLeft==0||a.monkLeft==N)return true;else{if(a.monkLeft=a.wildLeft(N-a.monkLeft)=(N-a.wildLeft))return true;}return false;}}然后开始广搜，按照容器中的最优解进行有哪些信誉好的足球投注网站，如果满足，则存入队列，再对队列首元素进行有哪些信誉好的足球投注网站，看下一级元素是否满足合法状态，满足，再入栈，直到左岸的状态为0，0，false，判断函数为：bool IsFinish(node a){i