传教士和野人问题实验报告(共5页).doc

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