实验二 知识表示方法
状态空间法实验
1．实验目的
（1）了解知识表示相关技术；
（2）掌握问题规约法或者状态空间法的分析方法。 2．实验内容（2个实验内容可以选择1个实现）
（1）梵塔问题实验。熟悉和掌握问题规约法的原理、实质和规约过程；理解规约图的表示方法；
（2）状态空间法实验。从前有一条河，河的左岸有m个传教士、m个野人和一艘最多可乘n人的小船。约定左岸，右岸和船上或者没有传教士，或者野人数量少于传教士，否则野人会把传教士吃掉。搜索一条可使所有的野人和传教士安全渡到右岸的方案。 3．实验报告要求
（1）简述实验原理及方法，并请给出程序设计流程图。
有N个传教士和N个野人来到河边准备渡河，河岸有一条船，每次至多可供k人乘渡。问传教士为了安全起见，应如何规划摆渡方案，使得任何时刻，在河的两岸以及船上的野人数目总是不超过传教士的数目。即求解传教士和野人从左岸全部摆渡到右岸的过程中，任何时刻满足M（传教士数）≥C（野人数）和M＋C≤K的摆渡方案。
由于传教士和野人数是一个常数，所以知道了一岸的情况，另一岸的情况也就知道了。因此为了简便起见，在描述问题时，只描述一岸--如左岸--的情况就可以了。另外，该问题我们最关心的是在摆渡过程中，两岸状态的变化情况，因此船上的情况并不需要直接表达出来。在一次摆渡过程中，船上究竟有几个传教士和野人，可以通过两个相连的状态简单得到。这样表达更简练，突出了问题的重点。
（ML，CL，BL），其中0≤ML，CL≤3，BL∈{0，1}，其中ML表示在左岸的传教士人数，CL表示在左岸的野人数，BL＝1表示船在左岸，BL＝0表示船在右岸。则此时问题描述可以简化为： （N，N，1）→（0，0，0）
（2）源程序清单：
#include
int M; //传教士人数 int C; //野人数 int B; //船 };
data state[50]; //记录状态
int K,M,sum=0; //载重，人数，解的个数 data Right,Left;//左岸和右岸的状态
void setData(data& Data,int m,int c,int b)//设置两岸状态 {
Data.M=m; Data.C=c; Data.B=b; }
void Print(int depth) //输出状态序列 {
for(int i=0;i cout<<\ cout<<\-1].B<<\ } bool noCircle(int m,int c,int k) //看状态序列中是否有自环 { bool flag=false; for(int i=0;i if((state[i].B==Right.B)&&(state[i].M==m)&&(state[i].C==c)) { flag=true; break; } if(flag)return false; return true; } bool safe(int m,int c) //看过河方案是否合理 { if((m+c)>0&&(m+c)<=K) { if(Right.B==0&&(m>=c||m==0)&&(((Left.M-m)>=(Left.C-c))||Left.M==m)&&(((Right.M+m)>=(Right.C+c))||(Right.M+m)==0)&&(Left.M-m>=0)&&(Left.C-c>=0)&&(Right.M+m<=M)&&(Right.C+c<=M))return true; if(Right.B==1&&(m>=c||m==0)&&((Left.M+m)>=(Left.C+c)||(Left.M+m)==0)&&((Right.M-m)>=(Right.C-c)||Right.M==m)&&(Left.M+m<=M)&&(Left.C+c<=M)&&(Right.M-m>=0)&&(Right.C-c>=0))return true; } return false; } void Find(int depth) //递归求解 { if(Left.M==0&&Left.C==0) //出口 { sum++; Print(depth); } else for(int i=0;i<=M;i++) { for(int j=0;j<=M;j++) { if((Left.B==1)&&safe(i,j)&&noCircle(Left.M-i,Left.C-j,depth)) { setData(state[depth],Left.M-i,Left.C-j,0); //在左岸，递归并回溯 setData(Right,Right.M+i,Right.C+j,1); setData(Left,Left.M-i,Left.C-j,0); Find(depth+1); setData(state[depth],0,0,0); setData(Right,Right.M-i,Right.C-j,0); setData(Left,Left.M+i,Left.C+j,1); } if((Left.B==0)&&safe(i,j)&&noCircle(Left.M+i,Left.C+j,depth)) { setData(state[depth],Left.M+i,Left.C+j,1); //在右岸，递归并回溯 setData(Right,Right.M-i,Right.C-j,0); setData(Left,Left.M+i,Left.C+j,1); Find(depth+1); setData(state[depth],0,0,0); setData(Right,Right.M+i,Right.C+j,1); setData(Left,Left.M-i,Left.C-j,0); } } } } int main() { cout<<\请输入人数：\ cin>>M; cout<<\请输入容量：\ cin>>K; setData(state[0],M,M,1); //设置初始状态 setData(Left,M,M,1); setData(Right,0,0,0); Find(1); //开始求解 if(sum==0)cout<<\ else cout<<\共有\个解\ return 0; } （3）实验结果及分析。 由以上结果可知成功完成实验目的，仅展示一个较简单的结果，下面展示人数为5，容量为3的结果
