人工智能：野人与修道士问题

人工智能：野人与修道士问题

Missionaries-and-Cannibals Problem

[]：三个野人与三个传教士来到河边，打算乘一只船从右岸渡

到左岸去，该船的最大负载能力为两个人。在任何时候，如果野人人数超过传教

士人数，那么野人就会把传教士吃掉。

用状态空间法表示修道士与野人问题并设计编写计算机程序求问题的解。

左L 右R

修道士M

船

B 野 人C

从上图可知，修道士、野人和船一共有六种可能，MCBMCB可以表、、、、、。LLLRRR示为q＝（M，C，B），其中m表示修道士的数目（0、1、2、3）、c表示野人的数目（0、1、2、3）、b表示船在左岸（1）或右岸（0）。 1、（m，c，b）

2、：

s0(3,3,1) s8(1,3,1) s16(3,3,0) s24(1,3,0)

s1(3,2,1) s9(1,2,1) s17(3,2,0) s25(1,2,0)

s2(3,1,1) s10(1,1,1) s18(3,1,0) s26(1,1,0)

s3(3,0,1) s11(1,0,1) s19(3,0,0) s27(1,0,0)

s4(2,3,1) s12(0,3,1) s20(2,3,0) s28(0,3,0)

s5(2,2,1) s13(0,2,1) s21(2,2,0) s29(0,2,0)

s6(2,1,1) s14(0,1,1) s22(2,1,0) s30(0,1,0)

s7(2,0,1) s15(0,0,1) s23(2,0,0) s31(0,0,0)

初始状态：（3,3,1）

目标状态：（0,0,0）

3、L：把i个修道士，j个野人从河的左岸送到右岸 ij

R：把i个修道士，j个野人从河的右岸送到左岸 ij

整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问

题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的

算符，根据题目要求，可以得出以下5个算符（按照渡船方向的不同，也可以

理解为10个算符）：

渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师 即：L01或R01，L10或R10，L11或R11，L02或R02，L20或R20 4

L02 R01 S18

L01 L02 R01 L20 S0 S17 S1 S14 S2 S26

S21 L11 R10

R11

S10 L11 R10

L02 R01 L20 S31 S30 S29 S14 S12 S5 L01

S18 R21 L02

5

算法：在应用状态空间表示和搜索方法时，用（M，C，B）来表示状态描述，其中M和C分别表示在左岸的传教士与野人数。B为1表示船在左岸，为0表示在右岸。于是初始状态为（0，0，0），目标状态为（3，3，1）。我们将此问题用图表示出来，首先生成各种安全状态结点，存放在顶点向量中；在建立了

图的邻接矩阵存储结构后，利用深度优先搜索思想从顶点（0，0，0）到顶点（3，3，1）的一条简单路径。

#include

#include

#define VEX_NUM 18 /* 最大顶点个数 */ typedef struct{ /* 定义图的顶点类型 */

int Missionary,Cannibal,Boat;

} Vextype;

typedef struct{

int vexnum ; /* 图的当前顶点数 */

Vextype vexs[VEX_NUM]; /* 顶点向量 */

int adj[VEX_NUM][VEX_NUM]; /* 邻接矩阵 */ } AdjGraph;

int visited[VEX_NUM]; /* 遍历过程中进行标记用的辅助数组 */

int path[VEX_NUM];

/* 查找顶点（M，C，B）在顶点向量中的位置 */

int locate(AdjGraph *G,int M,int C,int B)

{ int i;

for (i=0;ivexnum;i++)

if ( G->vexs[i].Missionary==M && G->vexs[i].Cannibal==C &&

G->vexs[i].Boat==B )

return(i);

return(-1);

}

/* 判断状态（M，C，B）是否合理 */

int is_safe(int M,int C,int B) { if (M==C)

if (M==3)

if (B==0)

return (0);

else

return (1);

else if (M==0)

if (B==1)

return (0);

else

return (1);

else

return (1);

else if ((M==0)||(M==3))

return (1);

else

return (0); }

/* 检查第i个状态和第j个状态是否可转换 */

int is_connected(AdjGraph *G,int i,int j)

{ int k=0;

while (G->vexs[i].Boat==1)

{ if ( G->vexs[j].Missionary - G->vexs[i].Missionary == -1 &&

G->vexs[j].Cannibal==G->vexs[i].Cannibal )

k++;

if ( G->vexs[j].Missionary==G->vexs[i].Missionary &&

G->vexs[j].Cannibal - G->vexs[i].Cannibal== -1 )

k++;

if ( G->vexs[j].Missionary - G->vexs[i].Missionary== -2 &&

G->vexs[j].Cannibal==G->vexs[i].Cannibal )

k++;

if ( G->vexs[j].Missionary == G->vexs[i].Missionary &&

G->vexs[j].Cannibal - G->vexs[i].Cannibal == -2 )

k++;

if ( G->vexs[j].Missionary - G->vexs[i].Missionary == -1 &&

G->vexs[j].Cannibal - G->vexs[i].Cannibal == -1 )

k++;

if ( G->vexs[j].Boat==0 && k>=1)

return (1);

else

return (0);

}

while (G->vexs[i].Boat==0)

{ if ( G->vexs[j].Missionary - G->vexs[i].Missionary==1 &&

G->vexs[j].Cannibal ==G->vexs[i].Cannibal )

k++;

if ( G->vexs[j].Missionary == G->vexs[i].Missionary &&

G->vexs[j].Cannibal - G->vexs[i].Cannibal== 1 )

k++;

if ( G->vexs[j].Missionary - G->vexs[i].Missionary== 2 &&

G->vexs[j].Cannibal== G->vexs[i].Cannibal )

k++;

if ( G->vexs[j].Missionary == G->vexs[i].Missionary &&

G->vexs[j].Cannibal - G->vexs[i].Cannibal ==2 )

k++;

if ( G->vexs[j].Missionary - G->vexs[i].Missionary == 1 &&

G->vexs[j].Cannibal - G->vexs[i].Cannibal ==1 )

k++;

if ( G->vexs[j].Boat == 1 && k>=1 )

return (1);

else

return (0);

}

}

void CreateG(AdjGraph *G)

{ int i,j,M,C,B;

i=0;

for (M=0;M<=3;M++) /* 形成所有合理的状态结点 */

for (C=0;C<=3;C++)

for (B=0;B<=1;B++)

if (is_safe(M,C,B))

{ G->vexs[i].Missionary=M;

G->vexs[i].Cannibal=C;

G->vexs[i].Boat=B;

i++;

}

G->vexnum=i;

for (i=0;ivexnum;i++) /* 生成邻接矩阵 */

for (j=0;jvexnum;j++)

if (is_connected(G,i,j))

G->adj[i][j]=G->adj[j][i]=1;

else

G->adj[i][j]=G->adj[j][i]=0;

return;

}

void DFS_path(AdjGraph *G,int u,int v) /* 求从U到V的简单路径 */

{ int j;

visited[u]=1;

for (j=0;jvexnum;j++)

if ( G->adj[u][j]==1 && visited[j]==0 && visited[v]==0 )

{ path[u]=j;

DFS_path(G,j,v); /* 深度优先搜索 */

}

}

void print_path(AdjGraph *G,int u,int v) /* 输出从U到V的简单路径 */

{ int k=u;

while (k!=v)

{ printf(\"(%d,%d,%d)\\n\

G->vexs[k].Boat);

k=path[k];

}

printf(\"(%d,%d,%d)\\n\

G->vexs[k].Boat);

getchar();

}

/* 主程序如下：*/

main()

{ int i,j;

AdjGraph graph;

CreateG(&graph);

for (i=0;ivisited[i]=0;

i=locate(&graph,0,0,0);

j=locate(&graph,3,3,1);

DFS_path(&graph,i,j);

if (visited[j])

print_path(&graph,i,j);

}