《人工智能：野人与修道士问题.docx》由会员分享，可在线阅读，更多相关《人工智能：野人与修道士问题.docx（8页珍藏版）》请在三一文库上搜索。
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 、（
2、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
3、)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，
4、 L10 或 R10，L11 或 R11，L02 或 R02，L20 或 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
6、_NUM; /*邻接矩阵*/ AdjGraph;int visitedVEX_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);/*判
7、断状态（ M，C，B）是否合理 */int is_safe(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->vexs
8、i.Boat=1) 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->vexsj.Missionary - G->vexsi.Missionary= -2 &am
9、p;& 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.Cannibal - G->vexsi.Cannibal = -1 ) k+;if (
10、 G->vexsj.Boat=0 && k>=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->ve
11、xsi.Cannibal= 1 ) k+;if ( G->vexsj.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.Mission
12、ary = 1 && G->vexsj.Cannibal - 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.Missi
13、onary=M; G->vexsi.Cannibal=C;G->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
14、;for (j=0;j<G->vexnum;j+)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.B
15、oat);k=pathk;printf("(%d,%d,%d)n",G->vexsk.Missionary,G->vexsk.Cannibal, G->vexsk.Boat);getchar();/* 主程序如下： */ main() int i,j;AdjGraph graph;CreateG(&graph);for (i=0;i<graph.vexnum;i+)visitedi=0;i=locate(&graph,0,0,0);j=locate(&graph,3,3,1);DFS_path(&graph,i,j);if (visitedj)print_path(&graph,i,j);