计算机科学与技术1341901301 敏实验一：知识表示方法一、实验目的状态空间表示法是人工智能领域最基本的知识表示方法之一，也是进一步学习状态空间搜索策略的基础，本实验通过牧师与野人渡河的问题，强化学生对知识表示的了解和应用，为人工智能后续环节的课程奠定基础。
二、问题描述有n个牧师和n个野人准备渡河，但只有一条能容纳c个人的小船，为了防止野人侵犯牧师，要求无论在何处，牧师的人数不得少于野人的人数(除非牧师人数为0)，且假定野人与牧师都会划船，试设计一个算法，确定他们能否渡过河去，若能，则给出小船来回次数最少的最佳方案。
三、基本要求输入：牧师人数(即野人人数)：n；小船一次最多载人量：c。
输出：若问题无解，则显示Failed，否则，显示Successed输出一组最佳方案。
用三元组(X1, X2, X3)表示渡河过程中的状态。
并用箭头连接相邻状态以表示迁移过程：初始状态->中间状态->目标状态。
例：当输入n=2，c=2时，输出：221->110->211->010->021->000其中：X1表示起始岸上的牧师人数；X2表示起始岸上的野人人数；X3表示小船现在位置(1表示起始岸，0表示目的岸)。
要求：写出算法的设计思想和源程序，并以图形用户界面实现人机交互，进行输入和输出结果，如：Please input n: 2 Please input c: 2Successed or Failed?: SuccessedOptimal Procedure: 221->110->211->010->021->000四、算法描述（1）算法基本思想的文字描述；从初始状态S(n,n,1)出发，形成的有合法且未达状态S11、S12、……、Sli 。
再分别从S11、S12、……、Sli 出发形成所有合法而未达状态S111、S112、…… 、Sli1、Sli2、Sli ……最终达到目标（0，0，0）（有解），或者找不到合法而未达状态（无解）。
若有解，则从目标返回找前趋状态，前趋状态的前趋状态……直到初始状态。
（2）判别（X1，X2，X3）为合法状态条件：X1=0或X1=n 或X1=X2。
（3）数据结构：1 栈STACK ，记下“已达”状态及踪迹，并兼作队列。
2 STATE[X1][X2]=（4）算法基本思想的具体实现：1 初始化：置STA TE[N+1][N+1][2]中的有状态为“未达”置队列STACK 空，cond 为当前是否已达到目标： cond=cond 置初值2 以S （n,n,1）为始点，置STA TE 为“已达”。
S 入队列STACK3 while （队列STACK 空且未达到目标时）A{ 取出队头元素地址=>p1，队头元素出队列B while （未达到目标，且P1有可达、合法、且未到达过的相邻顶点Q ）if (Q=(000) 则{cond=1,Q 入队列}否则 {置QW 为“已达”，Q 入队列} /* B 可用函数COMBINE 实现 */4 if (cond=1)则按队列中前趋指针指示的次序依次输出序列，否则输出“渡河失败”。
5 COMBINE 函数的功能等价于从数量不等的物品，分别选出1件、2件、……C 件物品的所有组合，同时对每一种组合确定其合法性。
COMBINE （ ）{ 1 栈SP 初始化（SP 存放已放入物品序号），NUM 为已取出物品个数，NUM=0，i 为准备取出物品序号，i<=1。
2 do {while (未达到目标，且所有物品还未取尽，且NUM<C){若该种物品已取尽，则取下一种,i++;取出第i 种物品中一件来，该物来序号（即i ）进栈，NUM++;判断该状态合法否？！ /* 用函数dicision 实现 */0 已达 1 未达0 未达目标1 已达到目标}if (未达到目标，且栈SP不空){则读栈SP=>i，将第种物品放回一件：NUM--:退栈；i++;}}while(未达到目标，且并非所有情况均已列举完)}dicision ( ){ if (当前状态（x1,x2,x3）合法且未达)则(x1,x2,x3)及前趋指针入队列STACK；if ((x1,x2,x3)==0,0,0)) 则cond=1;}五、源程序#include <stdio.h>typedef struct node{int np; /* The normal people's number at start shore. */int mp; /* The mad people's number at start shore. */int shore; /* '0'=end shore,'1'=start shore */int track; /* The track of the point */}NODE;NODE stack[80]; /* The massage from stack[1]*/int state[80][80][2],n,c,front,back,cond;void dicision(int t[]){int a[4],i;for(i=0;i<4;i++) a[i]=t[i];if(a[2]==1){a[0]=n-a[0];a[1]=n-a[1];}if((a[0]==0||a[0]==n||a[0]==a[1]) && state[a[0]][a[1]][a[2]]==1){back++;stack[back].np=a[0];stack[back].mp=a[1];stack[back].shore=a[2];stack[back].track=front;}state[a[0]][a[1]][a[2]]=0;if(a[0]==0 && a[1]==0 && a[2]==0)cond=1;}void combine(int t[]){int sp[80];/* The stack */int top; /* The stack sp's top*/int all; /* The people's number at start shore */int num; /* The things number which allready get */int i;top=i=num=0; t[2]=!t[2]; all=t[0]+t[1];do{while(cond!=1 && num<c && all>0 && i<2){if(t[i]==0){if(i<1) i++;else return;}t[i]--;sp[top++]=i;num++;all--;dicision(t);}if(cond!=1 && top>0){i=sp[--top];t[i]++; all++; num--; i++;}}while(cond!=1&&( top>0 || (i<2&&all>0) ) );}void put(NODE stack[]){int i,j,m,b[80];printf("\nStack Np Mp Shore Last point\n");for(i=1;i<=back;i++)printf("<%2d >%5d%5d%7d%10d\n",i,stack[i].np,stack[i].mp,stack[i].shore,stack[i].track); if(cond==1){i=back;m=0;while(i!=0){b[m++]=i; i=stack[i].track;}printf("The cross way is: ");for(j=m-1;j>=0;j--){printf("(%d,",stack[b[j]].np);printf("%d,",stack[b[j]].mp);printf("%d",stack[b[j]].shore);if(j!=0)printf(")->");}printf(")\n");printf("The stack is: %d->",back);for(j=0;j<m-1;j++){printf("%d",stack[b[j]].track); if(j!=m-2) printf("->");}printf("\nSeccess!");}else printf("Failure!");printf("\n");}void main(){int i,j,s,t[4];printf("please input the number of people (n): "); scanf("%d",&n); printf("please input the capacity of boat (c): "); scanf("%d",&c);for(i=0;i<80;i++)for(j=0;j<80;j++)for(s=0;s<2;s++)state[i][j][s]=1;front=back=0;cond=0;state[n][n][1]=0;back++;stack[back].np=n;stack[back].mp=n;stack[back].shore=1;stack[back].track=0;while(back>front && cond!=1){front++;t[0]=stack[front].np;t[1]=stack[front].mp;t[2]=stack[front].shore;t[3]=stack[front].track;if(t[2]==0){ t[0]=n-t[0]; t[1]=n-t[1]; }combine(t);}put(stack);}六、运行结果实验二：九宫重排一、实验目的A*算法是人工智能领域最重要的启发式搜索算法之一，本实验通过九宫重排问题，强化学生对A*算法的理解与应用，为人工智能后续环节的课程奠定基础。