传教士问题

《传教士问题》由会员分享，可在线阅读，更多相关《传教士问题（14页珍藏版）》请在装配图网上搜索。

1、一 问题描述有 M 个传教士和 N 个野人来到河边准备渡河，河岸有一条船，每次至多可供 k 人乘渡。任何时刻在河的两岸以及船上的野人数目总是不超过传教士的数目。 二 问题分析本问题采用A*算法求解，解答的关键与难点如下：1 评估函数的建立。评估函数为 f=h+d=M+N-2*B+d.。M 表示左岸的传教士的人数， N 表示左岸野人的数目， B 取值为 0 或 1 。1 表示 船在左岸，0表示船在右岸。d表示节点的深度。下面我们来证明h(n) = M+C-2B是满足A*条件的。我们分两种情况考虑。先考虑船在左岸的情况。如果不考虑限制条件，也 就是说，船一次可以将三人从左岸运到右岸，然后再有一个人

2、将船送回来。这样， 船一个来回可以运过河2人，而船仍然在左岸。而最后剩下的三个人，则可以一 次将他们全部从左岸运到右岸。所以，在不考虑限制条件的情况下，也至少需要 摆渡 ( M +N-3 ) /2 * 2 +1次。其中分子上的3表示剩下三个留待最后一次运过去。 除以2是因为一个来回可以运过去2人，需要(M+N-3)/2个来回，而来回数不 能是小数，需要向上取整，这个用符号 表示。而乘以2是因为一个来回相当 于两次摆渡，所以要乘以2。而最后的1，则表示将剩下的3个运过去，需要 一次摆渡。化简有： M+N-2。再考虑船在右岸的情况。同样不考虑限制条件。船在右岸，需要一个人将 船运到左岸。因此对于状

3、态(M, N, 0)来说，其所需要的最少摆渡数，相当于船 在左岸时状态(M+1，N，1)或(M, N+1, 1)所需要的最少摆渡数，再加上第一次 将船从右岸送到左岸的一次摆渡数。因此所需要的最少摆渡数为： (M+N+1)-2+1。 其中(M+N+1 )的+ 1表示送船回到左岸的那个人，而最后边的+ 1，表示送船 到左岸时的一次摆渡。化简有： (M+N+1)-2+1=M+N。综合船在左岸和船在右岸两种情况下，所需要的最少摆渡次数用一个式子 表示为：M+N-2B。其中B = 1表示船在左岸，B = 0表示船在右岸。由于该摆渡次数是在不考虑限制条件下，推出的最少所需要的摆渡次数从前有一条河，河的左岸

4、有m个传教士 (Missionary)和m个野人(Canniba l),和一艘最多可乘n人的小船。约定左岸，右岸和船上或者没有传教士，或 者野人数量少于传教士，否则野人会把传教士吃掉。编程，接收m和n,搜索一条可让所有的野人和传教士安全渡到右岸的方案。我们先假设左岸有3个传教士和3个野人，小船最多可乘2人。把当前左岸的 状态抽象为：(3,3,1)前两个3代表左岸有3个传教士和3个野人，1代表船在左岸。把每一次可行的渡船方案作为算符。比如，在初始状态，让1个传教士和1个野人上船并渡 到右岸，这一算符可表示为：(1,1)算符的两位数分别代表要移动的传教士，野人的数量；把人移到没有船的岸边并 且改变

5、状态向量中船的值。对于固定大小的小船，算符的数量是一定的：class Move public:int missionary;/要移动的传教士数量；class MoveGroup public:Move move500;/算符集int numMove;/可用算符的总数MoveGroup(int MAXON BOAT) /利用构造器求算符集intm, c,i = 0;for(m = 0; m = MAX ON BOAT; m+)for (c = 0; c = MAX ON BOAT; c+)if (c=0 & m!=0)movei.missionary=m;movei.cannibal=O;i+;

6、else if (m=0 & c!=0)movei.missionary=O;movei.cannibal=c;i+;else if(m+c=c)movei.missionarym;movei.cannibalc;numMovei；创建一个MoveGroup对象MoveGroup mg（2）;即可得到当小船最多可乘2人时的算符集。这个程序所要做的，就是通过这个已知的算符集，将初始状态（3,3,1）转变为 最终状态（0,0,0）。我们应将状态作为搜索的元素。构建类时应注意，并不是每个算符对于任意的状态都是可以应用的，这需要对应 用算符后的安全性进行检查，以判断这一算符对当前状态是否可用；同时，类

7、中 也要包含一个判断当前状态是否是最终节点（0,0,0）的方法；当然=”，”=” 这两个运算符以及null值，这是调用dso.h时所不可或缺的。（详见源文件）class ElemType : Move /继承Move类，获得传教士，野人数据成员。private:bool boat;/船是否在左岸？public:ElemType* flag;/这个后边再说，暂时用不到ElemType（int MAX_PEOPLE） /仓建初始状态boa t = true;flagNULL;ElemType() bool operator =(ElemType e) return this-missionary=

8、e.missionary &this-cannibal=e.cannibal &this-boat=e.boat;void operator =(ElemType e) this-missionary = e.missionary;this-cannibal = e.cannibal;this-boat = e.boat;this-flag = e.flag;ElemType friend operator (ElemType source, Move &mv) /移动操作，通过重载运算符“”你将在isSafe(ElemType)中见到用法。ElemType result;if(source.

9、boat = 1)result.missionary = (source.missionary -= mv.missionary);result.cannibal = (source.cannibal -= mv.cannibal);result.boat = 0; else result.missionary = (source.missionary += mv.missionary);result.cannibal = (source.cannibal += mv.cannibal);result.boat1；return result;bool isSafe(Move &mv, int

10、MAX_PEOPLE) /判断当前状态在进行mv操作后还是不是安全状态if( (boat=1&(missionary-mv.missionary 0|cannibal-mv.cannibal MAX_PEOPLE |cannibal+mv.cannibal MAX_PEOPLE)return false;else ElemType temp = this mv;if( temp.missionary=0 | temp.missionary=MAX_PEOPLE |(temp.missionary=temp.cannibal &MAX_PEOPLE-temp.missionary = MAX_P

11、EOPLE-temp.cannibal)return true;else return false;bool isSuccess() return missionary=0 & cannibal=0 & boat=0;/isSuccess()判断当前状态是否为最终节点int getC() return cannibal; int getB() return boat; void pri nt() cout ( missionary , cannibal, boat ) next;return &temp-node;；当得到了一个最终节点（0,0,0 ）时，如果我们前边的操作没有保存路径的话，

12、那么我们就只知道这个问题有解，而不知道解的具体路径。还记得在定义Elem Type时那个旗子指针吗，用它保留它的父节点的地址，问题就解决了。搜索得到的答案也保存在一个队列里，但我们知道：当得到一个最终节点时，根据它的指向父节点的指针向上搜索得到的是一个反的解序列，这里使用一个临时的栈，可以将解的顺序调换过来。class Answer : public Queue private:int max_people;public:MAX ON BOAT) Answer(int MAX PEOPLE, intQueue open;Queuex closed;Stack temp;/这是所使用的临时栈St

13、atus s0(MAX PEOPLE);/这是初始节点MoveGroup mg(MAX_ON_BOAT);/这是算符集/以下是搜索算法:open.enqueue(sO);max_people = MAX_PEOPLE;while(! open.isEmpty()Status si = open.dequeue(), s2; closed.enqueue(sl);ElemType* ptr = closed.getTailPtr();/得到被扩展的父节点的指针ptrfor(int i = 0; i mg.movei;if(closed.locate(s2) = INFEASIBLE) s2.fl

14、ag = ptr; open.enqueue(s2);if(s2.isSuccess() /搜索到最终节点后的操作 closed.enqueue(s2);while(s2.flag != NULL) temp.push(s2); s2 = *(s2.flag);this-enqueue(sO);while(! s2.isSuccess() s2 = temp.pop(); this-enqueue(s2);return;void show() this-traverse(print); ；就要成功了，通过下面这个声明就可以得到MAX_PEOPLE个传教士，MAX_PEOPLE个野人，每艘船上最多乘坐MAX_ON_BOAT人的解：Answer answer(MAX_PEOPLE, MAX_ON_BOAT);通过下面的调用可以列出整个解的过程：answer.show();