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

1、人工智能：野人与修道士问题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

2、,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（

3、0,0,1） s23（2,0,0） s31（0,0,0）初始状态：（ 3,3,1 ）目标状态：（ 0,0,0 ）3、L:把i个修道士，j个野人从河的左岸送到右岸ijR:把i个修道士，j个野人从河的右岸送到左岸ij整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。问 题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说 的算符，根据题目要求，可以得出以下 5 个算符（按照渡船方向的不同，也可以 理解为 10 个算符）:渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师即: L01或R01, L10 或 R10, L11 或 R11, L02 或 R02, L20

4、 或 R20 4L02 R01 S18L01 L02 R01 L20 S0 S17 S1 S14 S2 S26S21 L11 R10R11S10 L11 R10L02 R01 L20 S31 S30 S29 S14 S12 S5 L01S18 R21 L025算法：在应用状态空间表示和搜索方法时，用（ M C, B）来表示状态描述， 其中M和C分别表示在左岸的传教士与野人数。B为1表示船在左岸，为0表示在右岸。于是初始状态为（ 0, 0, 0）,目标状态为（ 3, 3, 1）。我们将此问题用图 表示出来,首先生成各种安全状态结点,存放在顶点向量中；在建立了图的邻接矩阵存储结构后，利用深度优先搜

5、索思想从顶点（ 0，0，0）到顶点(3，3，1)的一条简单路径。#include <stdio.h>#include <math.h>#define VEX_NUM 18 /* 最大顶点个数 */ typedef struct /* 点类型 */int Missionary,Cannibal,Boat; Vextype;typedef structint vexnum ; /* 图的当前顶点数 */Vextype vexsVEX_NUM; /* 顶点向量 */int adjVEX_NUMVEX_NUM; /* 邻接矩阵 */ AdjGraph;int visitedVE

6、X_NUM; /* 遍历过程中进行标记用的辅助数组 int pathVEX_NUM;/*查找顶点(M C, B)在顶点向量中的位置*/int locate(AdjGraph *G,int M,int C,int B) int i;for (i=0;i<G->vexnum;i+)if ( G->vexsi.Missionary=M && G->vexsi.Cannibal=C && G->vexsi.Boat=B )return(i);return(-1);*/定义图的顶/*判断状态(M C, B)是否合理*/int is_safe(

7、int M,int C,int B) if (M=C)if (M=3)if (B=0)return (0);elsereturn (1); else if (M=0) if (B=1)return (0);elsereturn (1);elsereturn (1);else if (M=0)|(M=3)return (1);elsereturn (0); /* 检查第 i 个状态和第 j 个状态是否可转换 */int is_connected(AdjGraph *G,int i,int j) int k=0;while (G->vexsi.Boat=1) if ( G->vexsj

8、.Missionary - G->vexsi.Missionary = -1 && G->vexsj.Cannibal=G->vexsi.Cannibal ) if ( G->vexsj.Missionary=G->vexsi.Missionary && G->vexsj.Cannibal - G->vexsi.Cannibal= -1 ) k+;if ( G->vexsj.Missionary - G->vexsi.Missionary= -2 &&G->vexsj.Cannibal=

9、G->vexsi.Cannibal )k+;if ( G->vexsj.Missionary = G->vexsi.Missionary &&G->vexsj.Cannibal - G->vexsi.Cannibal = -2 ) k+;if ( G->vexsj.Missionary - G->vexsi.Missionary = -1 &&G->vexsj.Cannibal - G->vexsi.Cannibal = -1 ) k+;if ( G->vexsj.Boat=0 && k

10、>=1)return (1);elsereturn (0);while (G->vexsi.Boat=0) if ( G->vexsj.Missionary - G->vexsi.Missionary=1 && G->vexsj.Cannibal =G->vexsi.Cannibal ) k+;if ( G->vexsj.Missionary = G->vexsi.Missionary &&G->vexsj.Cannibal - G->vexsi.Cannibal= 1 )k+;if ( G->v

11、exsj.Missionary - G->vexsi.Missionary= 2 && G->vexsj.Cannibal= G->vexsi.Cannibal ) k+;if ( G->vexsj.Missionary = G->vexsi.Missionary &&G->vexsj.Cannibal - G->vexsi.Cannibal =2 ) k+;if ( G->vexsj.Missionary - G->vexsi.Missionary = 1 &&G->vexsj.Can

12、nibal - G->vexsi.Cannibal =1 ) k+;if ( G->vexsj.Boat = 1 && k>=1 )return (1);elsereturn (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->vexsi.Missionary=M;G->vexsi.Cannibal=C;G-

13、>vexsi.Boat=B;i+;G->vexnum=i;for (i=0;i<G->vexnum;i+) /* 生成邻接矩阵 */for (j=0;j<G->vexnum;j+)if (is_connected(G,i,j)G->adjij=G->adjji=1;elseG->adjij=G->adjji=0;return;void DFS_path(AdjGraph *G,int u,int v) /*求从 U 到 V 的简单路径 */ int j;visitedu=1;for (j=0;j<G->vexnum;j+)

14、if ( G->adjuj=1 && visitedj=0 && visitedv=0 ) pathu=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->vexsk.Missionary,G->vexsk.Cannibal, G->vexsk.Boat);k=pathk;printf("(%d,%d,%d)n",G->vexsk.Missionary,G->vexsk.Cannibal, G->vexsk.Boat);getchar