传教士野人过河问题，敢不敢晒晒你的解法和实现 - 技术| 编程·课件·Linux - 软院网 RuanYuan.Net

问题描述：设有3个传教士（Missionaries）和3个野人(Cannibals)来到河边，打算乘一只船从右岸渡到左岸去。该船的最大负荷能力为两个人（k=2）。在任何情况下：如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去呢？（提示：用状态空间来描述，其综合数据库：用三元数组表示， m表示传教士，c表示野人，b表示船状态)

按照常用思路得出的渡法说明：
2个野人去，1个野人回
2个野人去，1个野人回
2个传教士去，1个野人与1个传教士回
2个传教士去，1个野人回
2个野人去，1个野人回
2个野人去，完成

这个问题是人工智能中经典的搜索问题，下面用深度优先搜索算法来解这个题，示例代码如下：
编程实现：

[AppleScript] 纯文本查看 复制代码

#include <iostream>
#include <vector>
#include <list>
using namespace std;
typedef struct
{
int m;//表示传教士
int c;// 表示野人
int b;//船状态
}MCNode;
list<MCNode> fringe;//相当于队列
vector<MCNode> closed;//closed表
//判断是否是目标结点
bool IsGoal(MCNode tNode)
{
if(tNode.m==0&&tNode.c==0&&tNode.b==0)
return true;
else
return false;
}
//判断是否是合法状态
bool IsLegal(MCNode tNode)
{
if(tNode.m>=0&&tNode.m<=3&&tNode.c>=0&&tNode.c<=3)
{
if((tNode.m==tNode.c)||(tNode.m==3)||(tNode.m==0))
return true;
else
return false;
}
else
return false;
}
//重载运算符，判断两结构体是否相等
bool operator==(MCNode m1,MCNode m2)
{
if(m1.m==m2.m&&m1.c==m2.c&&m1.b==m2.b)
return true;
else
return false;
}
//判断是否已在closed表中
bool IsClosed(MCNode tNode)
{
int i;
for(i=0;i!=closed.size();i++)
{
if(tNode==closed)
return true;
}
if(i==closed.size())
return false;
}
void ExpandNode(MCNode tNode,int b,list<MCNode> &fringe)
{
MCNode node[5];//应用5条规则集生成新结点
if(b==1)
{
for(int i=0;i<5;i++)
node.b=0;
node[0].m=tNode.m-1;
node[0].c=tNode.c;
node[1].m=tNode.m;
node[1].c=tNode.c-1;
node[2].m=tNode.m-1;
node[2].c=tNode.c-1;
node[3].m=tNode.m-2;
node[3].c=tNode.c;
node[4].m=tNode.m;
node[4].c=tNode.c-2;
}
else
{
for(int i=0;i<5;i++)
node.b=1;
node[0].m=tNode.m+1;
node[0].c=tNode.c;
node[1].m=tNode.m;
node[1].c=tNode.c+1;
node[2].m=tNode.m+1;
node[2].c=tNode.c+1;
node[3].m=tNode.m+2;
node[3].c=tNode.c;
node[4].m=tNode.m;
node[4].c=tNode.c+2;
}
for(int i=0;i<5;i++)
if(IsLegal(node)&&!IsClosed(node))
fringe.push_front(node);//队列后进先出，深度优先搜索，最后得到一条最小解序列
// fringe.push_back(node);//队列后进后出，广度优先搜索，最后得到最小解序列状态空间图
}
void main()
{
MCNode InitNode,unode;
InitNode.m=3;
InitNode.c=3;
InitNode.b=1;
fringe.push_back(InitNode);//将初始状态空间加入到队列
while(!fringe.empty())
{
unode=fringe.front();
fringe.pop_front();
if(IsGoal(unode))
{
closed.push_back(unode);
for(int i=0;i!=closed.size();i++)
cout<<closed.m<<","<<closed.c<<","<<closed.b<<endl;
break;
}
if(!IsClosed(unode))
{
closed.push_back(unode);
ExpandNode(unode,unode.b,fringe);
}
}
}

用人工智能中符号语言及用状态空间来描述，
其综合数据库：用三元数组表示。即
（MR，CR，LR），其中0≤MR，CR≤3,
k=2; LR∈{0,1}(0-船在左岸, 1-船在右岸)
此时问题描述简化为：
（3，3，1）→（0，0，0））
请分析给出（1）完整的规则集合
（2）符合规则的状态数量是多少？分别就“达不到”和“不合法”状态给予说明？
（3）渡法说明（做出推理图）
（18分）
（2-2）若0≤MR，CR≤4; k=2；别的条件同（2-1）；解如何？做图说明。
着回答一下前三问:(1)完整的规则集合 if (MR, CR, LR=1) then (MR-1, CR, LR-1); if (MR, CR, LR=1) then (MR, CR-1, LR-1); if (MR, CR, LR=1) then (MR-1, CR-1, LR-1); if (MR, CR, LR=1) then (MR-2, CR, LR-1); if (MR, CR, LR=1) then (MR, CR-2, LR-1); if (MR, CR, LR=0) then (MR+1, CR, LR+1); if (MR, CR, LR=0) then (MR, CR+1, LR+1); if (MR, CR, LR=0) then (MR+1, CR+1, LR+1); if (MR, CR, LR=0) then (MR+2, CR, LR+1); if (MR, CR, LR=0) then (MR, CR+2, LR+1); (2)状态空间的总状态数为4×4×2=32，只有20个合法状态，其中有4个合法状态达不到，最终解空间由16个状态组成，下面给出说明 (MR, CR, LR) (MR, CR, LR) (0 0 1)达不到 (0 0 0) (0 1 1) (0 1 0) (0 2 1) (0 2 0) (0 3 1) (0 3 0)达不到 (1 0 1)不合法 (1 0 0)不合法 (1 1 1) (1 1 0) (1 2 1)不合法 (1 2 0)不合法 (1 3 1)不合法 (1 3 0)不合法 (2 0 1)不合法 (2 0 0)不合法 (2 1 1)不合法 (2 1 0)不合法 (2 2 1) (2 2 0) (2 3 1)不合法 (2 3 0)不合法 (3 0 1)达不到 (3 0 0) (3 1 1) (3 1 0) (3 2 1) (3 2 0) (3 3 1) (3 3 0)达不到 (3)2个野人去，1个野人回 2个野人去，1个野人回 2个传教士去，1个野人与1个传教士回 2个传教士去，1个野人回 2个野人去，1个野人回 2个野人去，完成不合法的状态和重复状态，我都没画出，你可以自己加一下，也可以结合图说明一下

2个野人去，1个野人回
2个野人去，1个野人回
2个传教士去，1个野人与1个传教士回
2个传教士去，1个野人回
2个野人去，1个野人回
2个野人去，完成

看一下人工智能里的状态树搜索算法

不可能安全地把所有人都渡过河去，因为安全的方法野人是不会同意的，你也没办法和他们讲清道理。

假设有个传教士连哄带骗让野人同意要采取的方法,那就好办

用穷举的方法，就是乱猜，猜到对为止

先设两个数组right[]与left[]，right放右岸的人，left放左岸的人
再设两个数LL表示左岸从数，RL表示右岸人数

部分算法如下：(剩下些很简单的算法就不用我说了吧)

从左岸删除(manNO a,manNO b)
{
if(a!=LL)
从左岸删除(a);
从左岸删除(b);
LL--;
}

结果从右岸选人过河，位置为(manNO a,manNO b)
{
从右岸删除(a,b)；
往左岸加入(a,b)；
if(右岸野人多于传教士 or 左岸野人多于传教士)
      return 反败；
return 成功；
}
结果从左崖选人返回，位置为(manNO a,manNO b)
{
从左岸删除(a,b)；
往右岸增加(a,b)；
if(右岸野人多于传教士 or 左岸野人多于传教士)
      return 反败；
return 成功；
}
结果过河()
{
选定第1次到第7次过河和返回的人的编号
if(这7次过河与返回结果都成功)
      返回成功；
}

上面的 "过河()"函数可能写得太简单，下面是详细的:

typedef int manNO;
manNO h1,h2,H1,H2,i1,i2,I1,I2,j1,j2,J1,J2,k1,k2,K,l1,l2,L1,L2,m1,m2,M1,M2;//全局变量

结果过河()
{ //h1==RL是特殊情况,表示只选一人：h1不选,只选h2
for(h1=0;h1<RL;h1++)for(h2=(h1+1)%RL;h2<=RL;h2++)for(H1=0;H1<LL;H++)for(H2=(H1+1)%LL;H2<=LL;H2++)
for(i1=0;i1<RL;i1++)for(i2=(i1+1)%RL;i2<=RL;i2++)for(I1=0;I1<LL;I++)for(I2=(I1+1)%LL;I2<=LL;I2++)
for(j1=0;j1<RL;j1++)for(j2=(j1+1)%RL;j2<=RL;j2++)for(J1=0;J1<LL;J++)for(J2=(J1+1)%LL;J2<=LL;J2++)
for(k1=0;k1<RL;k1++)for(k2=(k1+1)%RL;k2<=RL;k2++)for(K1=0;K1<LL;K++)for(K2=(K1+1)%LL;K2<=LL;K2++)
for(l1=0;l1<RL;l1++)for(l2=(l1+1)%RL;l2<=RL;l2++)for(L1=0;L1<LL;L++)for(L2=(L1+1)%LL;J2<=LL;L2++)
for(m1=0;m1<RL;m1++)for(m2=(m1+1)%RL;m2<=RL;m2++)
if(从右岸选人过河，位置为(h1,h2)==成功)if(从左崖选人返回，位置为(H1,H2)==成功)
if(从右岸选人过河，位置为(i1,i2)==成功)if(从左崖选人返回，位置为(I1,I2)==成功)
if(从右岸选人过河，位置为(j1,j2)==成功)if(从左崖选人返回，位置为(J1,J2)==成功)
if(从右岸选人过河，位置为(k1,k2)==成功)if(从左崖选人返回，位置为(K1,K2)==成功)
if(从右岸选人过河，位置为(l1,l2)==成功)if(从左崖选人返回，位置为(L1,L2)==成功)
if(从右岸选人过河，位置为(m1,m2)==成功)
return 成功；
}

这个是以前写的野人与传教士的c程序，在win-tc下运行通过，由于其中有中文字符，显示可以会有乱码：

[AppleScript] 纯文本查看 复制代码

#include <stdio.h>
#include <stdlib.h>

#define maxloop 100 /* 最大层数，对于不同的扩展方法自动调整取值 */
#define pristnum 3
#define slavenum 3

struct SPQ{ int sr,pr; /* 船运行一个来回后河右岸的野人、传教士的人数 */
int sl,pl; /* 船运行一个来回后河左岸的野人、传教士的人数 */
int ssr,spr; /* 回来（由左向右时）船上的人数 */
int sst,spt; /* 去时（由右向左时）船上的人数 */
int loop; /* 本结点所在的层数 */
struct SPQ *upnode ,*nextnode;/* 本结点的父结点和同层的下一个结点的地址 */
}spq; 
int loopnum;/* 记录总的扩展次数 */
int openednum;/* 记录已扩展节点个数 */
int unopenednum;/* 记录待扩展节点个数 */
int resultnum;
struct SPQ *opened;
struct SPQ *oend;
struct SPQ *unopened; 
struct SPQ *uend;
struct SPQ *result;
void initiate();
void releasemem();
void showresult();
void addtoopened(struct SPQ *ntx);
int search();
void goon();
int stretch(struct SPQ* ntx);
void recorder();
void main()
{
int flag; /* 标记扩展是否成功 */
for( ; ; )
{
initiate();
flag = search ();
if(flag == 1)
{
recorder();
releasemem();
showresult();
goon();
}
else
{
printf("无法找到符合条件的解");
releasemem();
goon();
}
}
}
void initiate()
{
int x;
char choice;
uend = unopened = (struct SPQ*)malloc(sizeof(spq));
if(uend==NULL)
{
printf("\n内存不够！\n");
exit(0);
}
unopenednum=1;
openednum=0;
unopened -> upnode = unopened; /* 保存父结点的地址以成链表 */
unopened -> nextnode = unopened;
unopened -> sr = slavenum;
unopened -> pr = pristnum;
unopened -> sl = 0;
unopened -> pl = 0;
unopened -> sst = 0;
unopened -> spt = 0;
unopened -> ssr = 0;
unopened -> spr = 0;
unopened -> loop = 0;
printf("题目：设有n个传教士和m个野人来到河边，打算乘一只船从右岸到左岸去。\n");
printf("该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，野人\n");
printf("就会把传教士吃掉。他们怎样才能用这条船安全的把所有人都渡过河去?\n");
printf("\n默认的n、m值皆为3\n");
for(;;)
{
printf("\n是否修改？(Y/N)");
scanf("%s",&choice);
choice=toupper(choice);
if(choice=='Y')
{ 
printf("\n请输入传教士人数");
for(;;)
{
scanf("%d",&x);
if(x>0) 
{
unopened -> pr = x;
break;
}
else printf("\n输入值应大于0！\n请重新输入");
}
printf("\n请输入野人人数");
for(;;)
{
scanf("%d",&x);
if(x>0)
{
unopened -> sr = x;
break;
}
else printf("\n输入值应大于0！\n请重新输入");
} 
break;
}
if(choice=='N')break;
}
}

int search()
{
int flag;
struct SPQ *ntx; /* 提供将要扩展的结点的指针 */
for( ; ; )
{
ntx = unopened; /* 从待扩展链表中提取最前面的一个 */
if(ntx->loop == maxloop)
return 0; 
addtoopened(ntx); /* 将ntx加入已扩展链表，并将这个节点从待扩展链表中去掉 */
flag = stretch(ntx); /* 对ntx进行扩展,返回-1,0,1 */
if(flag == 1)
return 1; 
}
}

int stretch(struct SPQ *ntx)
{
int fsr , fpr ; /* 在右岸上的人数 */
int fsl , fpl ; /* 在左岸上的人数 */
int sst , spt ; /* 出发时在船上的人数 */
int ssr , spr ; /* 返回时船上的人数 */
struct SPQ *newnode;
for (sst = 0 ; sst <= 2 ; sst++) /* 讨论不同的可能性并判断是否符合条件 */
{ fsr = ntx -> sr;
fpr = ntx -> pr;
fsl = ntx -> sl;
fpl = ntx -> pl;
if ((sst <= fsr) && (( 2 - sst) <= fpr))/* 满足人数限制 */
{ spt = 2 - sst;
fsr = fsr - sst;
fpr = fpr - spt;
if((fpr == 0) && (fsr == 0))/* 搜索成功 */
{ 
newnode = (struct SPQ*) malloc (sizeof(spq));
if(newnode==NULL)
{
printf("\n内存不够！\n");
exit(0);
}
newnode -> upnode = ntx; /* 保存父结点的地址以成链表 */
newnode -> nextnode = NULL;
newnode -> sr = 0;
newnode -> pr = 0;
newnode -> sl = opened -> sr;
newnode -> pl = opened -> pr;
newnode -> sst = sst;
newnode -> spt = spt;
newnode -> ssr = 0;
newnode -> spr = 0;
newnode -> loop = ntx -> loop + 1;
oend -> nextnode = newnode;
oend = newnode;
openednum++;
return 1;
} 
else if ((fpr - fsr) * fpr >= 0) /* 判断是否满足传教士人数必须大于或等于野人人数 */
{
fsl = fsl + sst;
fpl = fpl + spt;
for (ssr = 0 ; ssr <= 1 ; ssr++) /* 返回 */
{
int ffsl , ffpl;
if ((ssr <= fsl) && ((1 - ssr) <= fpl))
{
spr = 1 - ssr;
ffsl = fsl - ssr;
ffpl = fpl - spr;
if ((ffpl - ffsl) * ffpl >= 0)
{ /* 若符合条件则分配内存并付值 */
int ffsr , ffpr;
ffsr = fsr + ssr;
ffpr = fpr + spr; 
newnode = (struct SPQ*) malloc (sizeof(spq));
if(newnode==NULL)
{
printf("\n内存不够！\n");
exit(0);
}
newnode -> upnode = ntx; /* 保存父结点的地址以成链表 */
newnode -> sr = ffsr;
newnode -> pr = ffpr;
newnode -> sl = ffsl;
newnode -> pl = ffpl;
newnode -> sst = sst;
newnode -> spt = spt;
newnode -> ssr = ssr;
newnode -> spr = spr;
newnode -> loop = ntx -> loop + 1;
uend -> nextnode = newnode;
uend = newnode;
unopenednum++; 
}
}
}
}
}
} 
return 0;
}

void addtoopened(struct SPQ *ntx)
{
unopened = unopened -> nextnode;
unopenednum--;
if (openednum == 0 )
oend = opened = ntx;
oend -> nextnode = ntx;
oend = ntx;
openednum++;
}

void recorder()
{
int i , loop;
struct SPQ *newnode;
struct SPQ *ntx;
loop = oend -> loop;
ntx = oend;
resultnum = 0;
for( i = 0 ; i <= loop ; i++ )
{
newnode = (struct SPQ*) malloc (sizeof(spq));
if(newnode==NULL)
{
printf("\n内存不够！\n");
exit(0);
}
newnode -> sr = ntx -> sr;
newnode -> pr = ntx -> pr;
newnode -> sl = ntx -> sl;
newnode -> pl = ntx -> pl;
newnode -> sst = ntx -> sst;
newnode -> spt = ntx -> spt;
newnode -> ssr = ntx -> ssr;
newnode -> spr = ntx -> spr;
newnode -> nextnode = NULL;
ntx = ntx -> upnode; 
if(i == 0)
result = newnode;
newnode -> nextnode = result;
result = newnode;
resultnum++;
}
}

void releasemem()
{
int i;
struct SPQ* nodefree;
for ( i = 1 ; i < openednum ; i++ )
{
nodefree = opened;
opened = opened -> nextnode;
free(nodefree);
}
for ( i = 0 ; i < unopenednum ; i++ )
{
nodefree = unopened;
unopened = unopened -> nextnode;
free(nodefree);
}
}

void showresult()
{
int i;
int fsr , fpr ; /* 在右岸上的人数 */
int fsl , fpl ; /* 在左岸上的人数 */
struct SPQ* nodefree;
printf("%d个传教士",result -> pr);
printf("%d个野人",result -> sr);
printf("%d个传教士",result -> pl);
printf("%d个野人",result -> sl);
for ( i = 1 ; i < resultnum ; i++ )
{
nodefree = result;
result = result -> nextnode;
free(nodefree);
printf("\n\n\t左岸人数 船上人数及方向 右岸人数\n");
printf("第%d轮\n",i);
fpl = result -> pl - result -> spt + result -> spr;
fpr = result -> pr - result -> spr;
fsl = result -> sl - result -> sst + result -> ssr;
fsr = result -> sr - result -> ssr;
printf("传教士%8d%8d\t<-\t%8d\n",fpl,result -> spt,fpr);
printf("野 人%8d%8d\t<-\t%8d\n",fsl,result -> sst,fsr);
printf("传教士%8d%8d\t->\t%8d\n",result -> pl,result -> spr,result -> pr - result -> spr);
printf("野 人%8d%8d\t->\t%8d\n",result -> sl,result -> ssr,result -> sr - result -> ssr);
}
printf("\n全体传教士和野人全部到达对岸");
free(result);
}

void goon()
{
char choice;
for(;;)
{
printf("是否继续？(Y/N)\n");
scanf ("%s" , &choice);
choice=toupper(choice);
if(choice=='Y')break;
if(choice=='N')exit(0);
}
}

教科书解答：有三个传教士和三个野人过河，只有一条能装下两个人的船，无论何时何地，如果野人的人数大于教士的人数，那么教士就会被吃掉. 你能不能找出一种安全的渡河方法呢?
　　网上解答为:三个牧师为ABC三个野人为abc
　　1.Aa过
　　2.A回
　　3.bc过
　　4.a回
　　5.AB过
　　6.Ab回
　　7.AC过
　　这应该是教科书上的解法.我们看到第三步时,当abc三个人都过了河时,再要求a回去,实在是对未经教化的野人赋予了太高的道德期望.
　　那看看我的神经质推算:
　　第一步必须是两个人过,不然就是做无用功了或死人了.
　　可选ab,名为方案1,或Aa,名为方案2
　　方案1
　　1.ab过,结果始岸:ABCc彼岸:ab
　　2.a回,此时:始岸:ABCac彼岸:b
　　3.ac过,一走了之,否.
　　 AB过,C被杀,否.
　　 Aa过,结果:始岸:BCc彼岸:Aab,A惨了,否.
　　注意,此时若只选一个人过河,若选教士,则回来的那个人也须是教士,那就是无用功了.若选野人,则又回到第一步的末状态.
　　方案1否
　　方案2
　　1.Aa过,结果:始岸:BCbc彼岸:Aa
　　2.a不能回,所以选A回:结果:始岸:ABCbc彼岸:a
　　3.大家看到我们已回到了方案1的第2步,接下来的结果当然也是否。
　　所以我有点不解地说这题像是在忽悠大家。
　　下面我们来猜测下教科书上方法的结果：
　　1.野人机心叵测，按照教科书上的方法先把教士渡过河去，然后再日后图吃教士肉。而教士说：我不下地狱谁入地狱，却也不肯这么快死去，所以也同意了教科书上的过河方法。
　　2.三个传教士临阵退缩：人类必须为他们的原罪赎罪，but why me?逃之夭夭，野人赶回去作报告。
　　3.教士怕教皇责骂，不能回头，说：Forgive me,my lord.Every one has his own cross.在三VS2(第2步）或3VS1（第4步）时把野人杀掉。再前进。
　　
　　再总体看下有没有其他的歪理使教士野人能过河，又相安无事呢？
　　假设1.我们假设双方都不信任彼此，为了安全过河，要保证任何时候任何地方实力相当。那开始时一定要野人教士各一个上船。过河后，则谁也不能回去了。此路不通。
　　假设2.假设双方信任彼此，条件为不准杀人，双方遵守契约，过河
　　假设3.若只有一方信任，条件为？？？遵守，不遵守？？？
　　假设4.教士为了生存，转变立场，站在野人一方。教士背叛？？？
　　......
　　到后来，我的头已经大了，再想下去恐怕会疯，真的神经质了。
　　这个无解也许是因为我无能力解答这个问题...
　　
　　这时候让我们来清醒下。
　　
　　放到现实中感慨下：
正因为我们的人性是如此的复杂，才有了如此多的可能，世间才有了如此多的故事，精彩也好，沉闷也罢。或者结局令人悲伤，或者令人温暖，都是人在尘世所体验的种种...
　　野人自有野人的生活，传教士有他自己的信仰，当两者撞到了一起，这世上又有一个角落在发生着不可知的故事.
　　
　　由于本人智力低下，文中神经搭错线的地方，还请各位海涵.同时希望各位可以提出各种猜想。
　　《蝴蝶效应》的最后，主人公把从前种种回忆疯想记录都烧掉了，是的，重要的是体验生活，享受生活，面对生活，而不是思考生活.
　　天下本无事，庸人自扰之。别忘了，是人就是庸人。生活除了纷扰以外，也有精彩，或多或少.
　　而是多是少？一如无解的野人与传教士过河了.

野人, 传教士, 过河

[技术| 编程·课件·Linux] 传教士野人过河问题，敢不敢晒晒你的解法和实现