传教士和野人问题实验报告(共5页).doc
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《传教士和野人问题实验报告(共5页).doc》由会员分享,可在线阅读,更多相关《传教士和野人问题实验报告(共5页).doc(5页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上1.上机内容传教士与野人问题求解(宽度搜索算法)二 问题背景:从前有一条河,河的左岸有m个传教士(Missionary)和m个野人(Cannibal),和一艘最多可乘n人的小船。约定左岸,右岸和船上或者没有传教士,或者野人数量少于传教士,否则野人会把传教士吃掉。三 实验内容:编程,接收m和n,搜索一条可让所有的野人和传教士安全渡到右岸的方案,例如下图:(M表示传教士(Missionary),C 表示野人(Cannibal))初态目标LeftBankRiverRightbankLeftBankRiverRightbankM.M.C.C.注:本实验的举例均以3个传教士和3
2、个野人同在左岸作为初始状态。四 实验方案和算法: 1数据结构: 本实验需要用到的数据结构主要是队列和堆栈,其实现均包含于dso.h头文件中,分别命名为class stack和class queue。2宽度搜索算法:(1)结点结构:class Move public: int missionary; /要移动的传教士数量 int cannibal; /野人;class ElemType : Move /继承Move类,获得传教士,野人数据成员。private: bool boat; /船是否在左岸?public: ElemType* flag; / 标示前一状态即扩展出本结点的父结点信息 Ele
3、mType(int MAX_PEOPLE) /创建初始状态 missionary = cannibal = MAX_PEOPLE; boat = true; flag = NULL;在这里,Elemtype集成了Move,从而获得Move类的传教士和野人数据成员。以上两个类的数据成员用于保存所有扩展生成的结点。其中missionary表示表示左岸上传教士的树目,cannibal表示左岸上野人的树目,boat表示船在哪个岸上(其中true表示在左岸,这是船的初始状态,表示false在右岸), flag用于标示前一状态即扩展出本结点的父结点信息,以便最后回搜找出解的路径。举例说明:假设左岸有3个传
4、教士和3个野人,小船最多可乘2人。把当前左岸的状态抽象为:(3,3,1),前两个3代表左岸有3个传教士和3个野人,1代表船在左岸。很明显,目标状态为(0,0,0),表示左岸的传教士和也人数目都是0,而船在右岸。(2)船的行动规则(successor function):把每一次可行的渡船方案作为行动规则,用Move类的(m,c)表示。行动规则的两位数分别代表要移动的传教士,野人的数量。对于固定大小的船,其装载能力是一定的,所以它的行动规则空间也是一定的。在这里,用MoveGroup类的构造函数构造出所有的行动规则。 注意,这里MoveGroup类中的Move对象只有500的可用空间,所以,输入
5、的传教士和野人数目构成的行动规则不能超过500种。(3)宽度优先算法:实验的主要搜索算法由ANSWER类的构造函数实现,这里主要用到了OPEN和CLOSED队列,以及一个临时的TEMP堆栈。其中,OPEN表用于存放扩展结点,CLOSED表用于存放被扩展结点,TEMP则用于用于记录成功搜索的路径。搜索过程大致如下描述:先构造初始结点以及船的行动规则,初始结点入OPEN队列,以宽度优先依次搜索OPEN队列头结点的子结点,同时保存受访问结点的父结点信息,知道搜索到目标结点或者无解为止。算法框图如下所示: 开始初始接结点并入OPEN队列Y返回OPEN为空?NOPEN队列头结点n出列,并入CLOSED队
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 传教士 野人 问题 实验 报告
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内