传教士和野人问题实验报告.docx

传教士和野人问题实验报告 1.上机内容 传教士与野人问题求解（宽度搜索算法） 二 二 问题背景： 从前有一条河，河的左岸有 m 个传教士(Missionary)和 m 个野人(Cannibal)，和一艘最多可乘 n 人的小船。约定左岸，右岸和船上或者没有传教士，或者野人数量少于传教士，否则野人会把传教士吃掉。 三 三 实验内容： 编程，接收 m 和 n，搜索一条可让所有的野人和传教士安全渡到右岸的方案，例如下图: （M 表示传教士(Missionary)，C 表示野人(Cannibal)） 初 态 目 标 Left Bank River Right bank Left Bank River Right bank M. M. C. C. 注：本实验的举例均以 3 个传教士和 3 个野人同在左岸作为初始状态。 四 四 实验方案和算法： 1 数据结构： 本实验需要用到的数据结构主要是队列和堆栈，其实现均包含于 dso.h