. . 计算机科学与技术 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为当前是否已达到目标： 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实现 */

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

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 && num0 && 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{
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;