计算机科学与技术 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: 2 Successed or Failed?: Successed
Optimal 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 初始化：置STATE[N+1][N+1][2]中的有状态为“未达”
置队列STACK空，cond为当前是否已达到目标：
0 未达目标
1 已达到目标 0 已达 1 未达
cond=
cond置初值
2 以S（n,n,1）为始点，置STATE为“已达”。S入队列STACK 3 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 {若该种物品已取尽，则取下一种,i++; 取出第i种物品中一件来，该物来序号（即i）进栈，NUM++; 判断该状态合法否？！ /* 用函数dicision实现 */ } 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 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 }while(cond!=1&&( top>0 || (i<2&&all>0) ) ); } void put(NODE stack[]) { int i,j,m,b[80]; printf(\ Np Mp Shore Last point\\n\ for(i=1;i<=back;i++) printf(\ if(cond==1) { i=back;m=0; while(i!=0) { b[m++]=i; i=stack[i].track; } printf(\ for(j=m-1;j>=0;j--) { printf(\ printf(\ printf(\ if(j!=0) printf(\ } printf(\ printf(\ for(j=0;j else printf(\ printf(\} void main() { int i,j,s,t[4]; printf(\ scanf(\ printf(\ scanf(\ 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++; 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库人工智能实验报告在线全文阅读。
相关推荐：