人工智能实验报告(同名16515).doc

计算机科学与技术 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）数据结构：0 已达1 未达 1 栈STACK，记下“已达”状态及踪迹，并兼作队列。 2 STATEX1X2= （4）算法基本思想的具体实现： 1 初始化：置STATEN+1N+12中的有状态为“未达”0 未达目标1 已达到目标置队列STACK空，cond为当前是否已达到目标： cond= cond置初值2 以S（n,n,1）为始点，置STATE为“已达”。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 (未达到目标，且所有物品还未取尽，且NUMi，将第种物品放回一件：NUM-:退栈；i+;while(未达到目标，且并非所有情况均已列举完) dicision ( ) if (当前状态（x1,x2,x3）合法且未达) 则(x1,x2,x3)及前趋指针入队列STACK；if (x1,x2,x3)=0,0,0) 则 cond=1;五、源程序#include typedef struct nodeint np; /* The normal peoples number at start shore. */int mp; /* The mad peoples number at start shore. */int shore; /* 0=end shore,1=start shore */int track; /* The track of the point */NODE;NODE stack80; /* The massage from stack1*/int state80802,n,c,front,back,cond;void dicision(int t) int a4,i;for(i=0;i4;i+) ai=ti;if(a2=1) a0=n-a0; a1=n-a1; if(a0=0|a0=n|a0=a1) & statea0a1a2=1) back+;stackback.np=a0;stackback.mp=a1;stackback.shore=a2;stackback.track=front;statea0a1a2=0;if(a0=0 & a1=0 & a2=0)cond=1; void combine(int t) int sp80;/* The stack */int top; /* The stack sps top*/int all; /* The peoples number at start shore */int num; /* The things number which allready get */int i;top=i=num=0; t2=!t2; all=t0+t1;dowhile(cond!=1 & num0 & i2) if(ti=0)if(i0) i=sp-top;ti+; all+; num-; i+;while(cond!=1&( top0 | (i0) ) );void put(NODE stack) int i,j,m,b80;printf(nStack Np Mp Shore Last pointn);for(i=1;i=back;i+)printf(%5d%5d%7d%10dn,i,stacki.np,stacki.mp,stacki.shore,stacki.track);if(cond=1) i=back;m=0; while(i!=0) bm+=i; i=stacki.track; printf(The cross way is: );for(j=m-1;j=0;j-) printf(%d,stackbj.np);printf(%d,stackbj.mp);printf(%d,stackbj.shore);if(j!=0)printf()-);printf()n);printf(The stack is: %d-,back);for(j=0;j);printf(nSeccess!);else printf(Failure!);printf(n);void main() int i,j,s,t4;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;i80;i+)for(j=0;j80;j+)for(s=0;sfront & cond!=1) front+;t0=stackfront.np;t1=stackfront.mp;t2=stackfront.shore;t3=stackfront.track;if(t2=0) t0=n-t0; t1=n-t1; 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 goalNN = 1,2,3,/目标状态8,0,4,7,6,5;struct state /状态结点int arrStateNN;int value;/该结点的启发值f(n)int depth;/所在的第几层int parent;/父节点int nID; /结点标记public:state()for(int i=0; iN; i+)for(int j=0; jN; j+)arrStateij = -1;value = -1;/该结点的启发值f(n)depth = -1;/所在的第几层parent = -1;/父节点nID = -1; /结点标记state& operator = (state s)for(int i=0; iN; i+)for(int j=0; jN; j+)arrStateij = s.arrStateij;value = s.value;depth = s.depth;parent = s.parent;nID = s.nID;return *this;bool operator = (state s)for(int i=0; iN; i+)for(int j=0; jN; j+)if(arrStateij != s.arrStateij)return false;return true;bool operator != (state s)return !(*this = s);class Eightprivate:state openM;/open 表int openIndex;/open表的元素个数state closedM;/close 表int closedIndex;/closed 表的元素个数int startNN;/开始的状态int nAutoIncrease;public:Eight();Eight(int sN);void init();/初始化open 和closeint f(state s);int w(int sNN);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 sNN);void findPath();void show(state s);Eight:Eight()start00 = 2;start01 = 8;start02 = 3;start10 = 1;start11 = 6;start12 = 4;start20 = 7;start21 = 0;start22 = 5;nAutoIncrease = 1;openIndex = -1;closedIndex = -1;Eight:Eight(int sN)for(int i = 0; iN; i+)for(int j = 0; jN; j+)startij = sij;nAutoIncrease = 1;openIndex = -1;closedIndex = -1;void Eight:init()for(int i = 0; iN; i+)for(int j = 0; jN; j+)open0.arrStateij = startij;open0.nID = 0;open0.depth = 0;open0.parent = 0;open0.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+)coutt;for(int j = 0; j N; j+)couts.arrStateij ;coutendl;coutendl;/coutfn=s.valuetdepth=:s.depthtnID=:s.nIDtparent=:s.parentendl;/启发值f(n) = depth + w(n)int Eight:f(state s)return s.depth + w(s.arrState);/计算不在位w(n)的值int Eight:w(int sNN)int count = 0;for(int i = 0; i N; i+)for(int j = 0; j N; j+)if(sij = 0 )/不考虑0的位置continue;if(sij != goalij)count+;return count;/ sort for Open tablevoid Eight:sortOpen()state temp;for(int i=0; i openIndex; i+)for(int j = i+1; j openj.value)temp = openi;openi = openj;openj = temp; / find current state 0 postionvoid Eight:findZeroPostion(int &x, int &y, state s)for(int i = 0; i N; i+)for(int j = 0; j N; j+)if(s.arrStateij = 0)x = i;/保持行坐标y = j;/保存列坐标return;/ the two states exchangevoid Eight:move(state des, state src)for(int row = 0; rowN; row+)for(int col = 0; colN; col+)des.arrStaterowcol = src.arrStaterowcol;des.depth = src.depth;des.parent = src.parent;des.value = src.value;/extend other statesvoid Eight:genNewState(state oldState)int row,col;int temp;/保存状态转换数组中的值state newState;findZeroPostion(row,col,oldState);/find zero positionif(row +1 -1)/0向上移动newState = oldState;newState.depth = oldState.depth +1;newState.parent = oldState.nID;newState.nID = nAutoIncrease+;/对ID自动编号/switchtemp = newState.arrStaterowcol; newState.arrStaterowcol = newState.arrStaterow-1col;newState.arrStaterow-1col = temp;newState.value = w(newState.arrState) + newState.depth;/newState.value = f(newState);/push newState to opengenToOpen(newState);if(col +1 -1)/0向左移动newState = oldState;newState.depth = oldState.depth +1;newState.parent = oldState.nID;newState.nID = nAutoIncrease+;/对ID自动编号/switchtemp = newState.arrStaterowcol; newState.arrStaterowcol = newState.arrStaterowcol-1;newState.arrStaterowcol-1 = temp;newState.value = w(newState.arrState) + newState.depth;/newState.value = f(newState);/push newState to opengenToOpen(newState);/把open表中已访问的state放到closed表中void Eight:moveToClosed(state s)int i = +closedIndex;closedi = s;/delete from open tablefor(int j = 0;j openIndex-1; j+)openj=openj+1;/open length-1openIndex-;/把扩展的状态放入open表中void Eight:genToOpen(state s)if(IsInOpen(s)/show(s);/cout该状态已存在open表中！endl;nAutoIncrease-;return;if(IsInClosed(s)/show(s);/cout该状态已存在closed表中！endl;nAutoIncrease-;return;int i = +openIndex;openi = s;openi.depth = s.depth;openi.parent = s.parent;openi.value = s.value;/ current state compare to goal statebool Eight:compare(state s)for(int i=0; iN; i+)for(int j=0; jN; j+)if(s.arrStateij != goalij)return false;return true;/ Is current state in closed tablebool Eight:IsInClosed(state s)for(int k = 0; k = closedIndex; k+)if(closedk = s)return true;return false;/ Is current state in open tablebool Eight:IsInOpen(state s)for(int k = 0; k = openIndex; k+)if(openk = s)return true;return false;void Eight:heuristicSearch()init();state curState; /保存当前的状态/coutf0=f(open0)endl;int n = 0;while(openIndex != -1)/while(n 50000)curState = open0;/*for(int i = 0; iopenIndex+1; i+)coutopen i:endl;show(openi);cout-=M | openIndex = M)cout宽度已达到极限endl;return;if(compare(curState)cout已获得求解endl;return;/输出moveToClosed(open0);/将该结点放入closed表中genNewState(curState);/扩展结点 并且将结点压入open表中sortOpen();/对新的open表排序n+;cout深度达到极限 -1; i-)if(nID = closedi.nID)show(closedi);/输出nID = closedi.parent;#include using namespace std;void main()int goalNN = 8,0,3,2,1,4, 7,6,5; Eight e(goal); e.heuristicSearch();e.findPath();八实验结果和分析 实验三：专家系统一、实验目的专家系统是人工智能的重要研究内容和组成部分之一，本实验通过设计一个简单的专家系统，加深学生对专家系统的组成结构和构造原理的理解，并能转化为具体的应用。二问题描述设计一个简单的专家系统，可根据属性的输入值自动识别事物的具体类别，内容自拟。如一个动物专家系统可由以下11个属性组成，根据属性的对应值(Y或N)，可判断动物的具体种类，运行结果如下图所示：三、实验组织运行要求本实验采用开放授课形式，每个同学独立完成上述实验要求。四、实验条件每人一台计算机独立完成实验。5、 源代码 #include #include using namespace std; char *animal=企鹅,海燕,鸵鸟,斑马,长颈鹿,虎,金钱豹; char *feature=有毛,产奶,有羽毛,会飞,会下蛋,吃肉,有犬齿,有爪,眼睛盯前方,有蹄,反刍,黄褐色,有斑点,有黑色条纹,长脖,长腿,不会飞,会游泳,黑白两色,善飞,哺乳类,鸟类,肉食类,蹄类,企鹅,海燕,鸵鸟,斑马,长颈鹿,