计算机科学与技术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 初始化:置STA TE[N+1][N+1][2]中的有状态为“未达”
置队列STACK 空,cond 为当前是否已达到目标: cond=
cond 置初值
2 以S (n,n,1)为始点,置STA TE 为“已达”。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 && num { 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; 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*算法的理解与应用,为人工智能后续环节的课程奠定基础。 二、问题描述 给定九宫格的初始状态,要求在有限步的操作,使其转化为目标状态,且所得到的解是代价最小解(即移动的步数最少)。如: 三、基本要求 输入:九宫格的初始状态和目标状态 输出:重排的过程,即途径的状态 四、实验组织运行要求 本实验采用集中授课形式,每个同学独立完成上述实验要求。 五、实验条件 每人一台计算机独立完成实验。 六.算法描述 procedure heuristic_search open :=[start] ;closed:=[ ] ;f(s) := g(s) + h(s) ; while open != [ ] do begin 从open 表中删除第一个状态,称为n ; if n = 目的状态then return (success) ; 生成n 的所有子状态; if n 没有任何子状态then continue ; for n 的每个子状态do case 子状态is not already on open 表or closed 表: begin 计算该子状态的估价函数值; 将该子状态加到open 表中; end ; case 子状态is already on open 表: if 该子状态是沿着一条比在open 表已有的更短路径而到达 then 记录更短路径走向及其估价函数值; case 子状态is already on closed 表: if 该子状态是沿着一条比在closed 表已有的更短路径而到达 begin 将该子状态从closed 表移到open 表中; 记录更短路径走向及其估价函数值; end ; case end ; 将n 放入closed 表中; 根据估价函数值,从小到大重新排列open 表; end ; return (failure); end 七.源代码 #include using namespace std; const int N = 3; //数组的维数 const int M = 100; //open 和close的大小 const static int goal[N][N] = {{1,2,3},//目标状态 {8,0,4}, {7,6,5}}; struct state //状态结点 { int arrState[N][N]; int value; //该结点的启发值f(n) int depth; //所在的第几层 int parent; //父节点 int nID; //结点标记 public: state() { for(int i=0; i for(int j=0; j arrState[i][j] = -1; value = -1; //该结点的启发值f(n) depth = -1; //所在的第几层 parent = -1; //父节点 nID = -1; //结点标记 } state& operator = (state s) { for(int i=0; i for(int j=0; j arrState[i][j] = s.arrState[i][j]; value = s.value; depth = s.depth; parent = s.parent; nID = s.nID; return *this; } bool operator == (state s) { for(int i=0; i for(int j=0; j if(arrState[i][j] != s.arrState[i][j]) return false; return true; } bool operator != (state s) { return !(*this == s); } }; class Eight { private: state open[M]; //open 表 int openIndex;//open表的元素个数 state closed[M]; //close 表 int closedIndex;//closed 表的元素个数 int start[N][N];//开始的状态 int nAutoIncrease; public: Eight(); Eight(int s[][N]); void init();//初始化open 和close int f(state s); int w(int s[N][N]); void sortOpen();//对Open表进行排序 void moveToClosed(state s); //void moveToOpen(state s); void genToOpen(state s); void findZeroPostion(int &x,int &y, state s);//查找0 的位置进行上下左右移动bool compare(state s); //当前的状态与目标状态比较 void genNewState(state oldState); void heuristicSearch();//查找路径 bool IsInOpen(state s); bool IsInClosed(state s); void move(state des,state src); bool IsCanSolve(int s[N][N]); void findPath(); void show(state s); }; Eight::Eight() { start[0][0] = 2; start[0][1] = 8; start[0][2] = 3; start[1][0] = 1; start[1][1] = 6; start[1][2] = 4; start[2][0] = 7; start[2][1] = 0; start[2][2] = 5; nAutoIncrease = 1; openIndex = -1; closedIndex = -1; } Eight::Eight(int s[][N]) { for(int i = 0; i for(int j = 0; j start[i][j] = s[i][j]; nAutoIncrease = 1; openIndex = -1; closedIndex = -1; } void Eight::init() { for(int i = 0; i for(int j = 0; j open[0].arrState[i][j] = start[i][j]; open[0].nID = 0; open[0].depth = 0; open[0].parent = 0; open[0].value = w(start) + 0; //f(0) = w(0) +d(0) openIndex = 0; closedIndex = -1; } //////////////////// void Eight::show(state s) { for(int i = 0; i < N; i++) { cout<<"\t"; for(int j = 0; j < N; j++) cout< cout< } cout< // cout<<"fn="< } //////////////// //启发值f(n) = depth + w(n) int Eight::f(state s) { return s.depth + w(s.arrState); } ////////////// //计算不在位w(n)的值 int Eight::w(int s[N][N]) { int count = 0; for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) { if(s[i][j] == 0 )//不考虑0的位置 continue; if(s[i][j] != goal[i][j]) count++; } return count; } /////////////////////////// // sort for Open table void Eight::sortOpen() { state temp; for(int i=0; i < openIndex; i++) for(int j = i+1; j < openIndex+1; j++) if(open[i].value > open[j].value) { temp = open[i]; open[i] = open[j]; open[j] = temp; } } /////////////////////////// // find current state '0' postion void Eight::findZeroPostion(int &x, int &y, state s) { for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) if(s.arrState[i][j] == 0) { x = i; //保持行坐标 y = j; //保存列坐标 return; } } /////////////////////////// // the two states exchange void Eight::move(state des, state src) { for(int row = 0; row for(int col = 0; col des.arrState[row][col] = src.arrState[row][col]; des.depth = src.depth; des.parent = src.parent; des.value = src.value; } ///////////////////////// // extend other states void Eight::genNewState(state oldState) { int row,col; int temp;//保存状态转换数组中的值 state newState; findZeroPostion(row,col,oldState);//find zero position if(row +1 < N)//0向下移动 { //move(newState, oldState); newState = oldState; newState.depth = oldState.depth +1; newState.parent = oldState.nID; newState.nID = nAutoIncrease++;//对ID自动编号 //switch temp = newState.arrState[row][col]; newState.arrState[row][col] = newState.arrState[row+1][col]; newState.arrState[row+1][col] = temp; newState.value = w(newState.arrState) + newState.depth; //newState.value = f(newState); //push newState to open genToOpen(newState); } if(row - 1 > -1)//0向上移动 { newState = oldState; newState.depth = oldState.depth +1; newState.parent = oldState.nID; newState.nID = nAutoIncrease++;//对ID自动编号 //switch temp = newState.arrState[row][col]; newState.arrState[row][col] = newState.arrState[row-1][col]; newState.arrState[row-1][col] = temp; newState.value = w(newState.arrState) + newState.depth; //newState.value = f(newState); //push newState to open genToOpen(newState); } if(col +1 < N)//0向右移动 { newState = oldState; newState.depth = oldState.depth +1; newState.parent = oldState.nID; newState.nID = nAutoIncrease++;//对ID自动编号 //switch temp = newState.arrState[row][col]; newState.arrState[row][col] = newState.arrState[row][col+1]; newState.arrState[row][col+1] = temp; newState.value = w(newState.arrState) + newState.depth; //newState.value = f(newState); //push newState to open genToOpen(newState); } if(col -1 > -1)//0向左移动 { newState = oldState; newState.depth = oldState.depth +1; newState.parent = oldState.nID; newState.nID = nAutoIncrease++;//对ID自动编号 //switch temp = newState.arrState[row][col]; newState.arrState[row][col] = newState.arrState[row][col-1]; newState.arrState[row][col-1] = temp; newState.value = w(newState.arrState) + newState.depth; //newState.value = f(newState); //push newState to open genToOpen(newState); } } ///////////////////////////////////// //把open表中已访问的state放到closed表中 void Eight::moveToClosed(state s) { int i = ++closedIndex; closed[i] = s; //delete from open table for(int j = 0;j < openIndex-1; j++) open[j]=open[j+1]; //open length-1 openIndex--; } ///////////////////////////////////// //把扩展的状态放入open表中 void Eight::genToOpen(state s) { if(IsInOpen(s)) { //show(s); //cout<<"该状态已存在open表中!"< nAutoIncrease--; return; } if(IsInClosed(s)) { //show(s); //cout<<"该状态已存在closed表中!"< nAutoIncrease--; return; } int i = ++openIndex; open[i] = s; open[i].depth = s.depth; open[i].parent = s.parent; open[i].value = s.value; } //////////////////////////// // current state compare to goal state bool Eight::compare(state s) { for(int i=0; i for(int j=0; j if(s.arrState[i][j] != goal[i][j]) return false; return true; } //////////////////////////// // Is current state in closed table bool Eight::IsInClosed(state s) { for(int k = 0; k <= closedIndex; k++) { if(closed[k] == s) return true; } return false; } //////////////////////////// // Is current state in open table bool Eight::IsInOpen(state s) { for(int k = 0; k <= openIndex; k++) { if(open[k] == s) return true; } return false; } void Eight::heuristicSearch() { init(); state curState; //保存当前的状态 //cout<<"f0=="< int n = 0; while(openIndex != -1) //while(n < 50000) { curState = open[0]; /* for(int i = 0; i { cout<<"open[ "< show(open[i]); } cout<<"------------------------------"< */ show(open[0]); if(closedIndex >=M || openIndex >= M) { cout<<"宽度已达到极限"< return; } if(compare(curState)) { cout<<"已获得求解"< return; //输出 } moveToClosed(open[0]); //将该结点放入closed表中 genNewState(curState); //扩展结点并且将结点压入open表中 sortOpen(); //对新的open表排序 n++; } cout<<"深度达到极限"< } void Eight::findPath() { //int i; sortOpen(); show(open[0]); int nID = open[0].parent; for(int i = closedIndex; i > -1; i--) if(nID == closed[i].nID) { show(closed[i]); //输出 nID = closed[i].parent; } } #include using namespace std; void main() { int goal[N][N] = {{8,0,3}, {2,1,4}, {7,6,5}}; Eight e(goal); e.heuristicSearch(); e.findPath(); } 八.实验结果和分析 实验三:专家系统 一、实验目的 专家系统是人工智能的重要研究容和组成部分之一,本实验通过设计一个简单的专家系统,加深学生对专家系统的组成结构和构造原理的理解,并能转化为具体的应用。 二﹑问题描述 设计一个简单的专家系统,可根据属性的输入值自动识别事物的具体类别,容自拟。如一个动物专家系统可由以下11个属性组成,根据属性的对应值(Y或N),可判断动物的具体种类,运行结果如下图所示: 三、实验组织运行要求 本实验采用开放授课形式,每个同学独立完成上述实验要求。 四、实验条件 每人一台计算机独立完成实验。 五、源代码 #include #include using namespace std; char *animal[]={"企鹅","海燕","鸵鸟","斑马","长颈鹿","虎","金钱豹"}; char *feature[]={"有毛","产奶","有羽毛","会飞","会下蛋","吃肉","有犬齿","有爪","眼睛盯前方","有蹄","反刍","黄褐色","有斑点","有黑色条纹","长脖","长腿","不会飞","会游泳","黑白两色","善飞","哺乳类","鸟类","肉食类","蹄类","企鹅","海燕","鸵鸟","斑马","长颈鹿","虎","金钱豹"}; typedef struct //存放规则的结构体 { int relation[5]; int name; }Rule;