人工智能与专家系统课程设计汇编

1、目录1 .设计任务1.1 设计题目1.2 设计要求1.3 设计任务2 方案设计2.1 原理2.2 具体设计方法3 系统实施3.1 系统开发环境3.2 系统主要功能介绍3.3 处理流程图3.4 核心源程序3.5 系统运行结果4 开发心得4.1 设计存在的问题4.2 进一步改进提高的设想4.3 经验和体会5 参考文献1 .设计任务1.1 设计题目在一个3*3的方棋盘上放置着1,2,3,4,5,6,7,8八个数码,每个数码占一格,且有一个空格。这些数码可以在棋盘上移动，该问题称八数码难题或者重排九宫问题。1.2 设计要求其移动规则是：与空格相邻的数码方格可以移入空格。现在的问题是：对于指定的初始棋局

2、和目标棋局，给出数码的移动序列。1.3 设计任务利用人工智能的图搜索技术进行搜索，解决八数码问题来提高在推理中的水平，同时进行新方法的探讨。2 .方案设计2.1 原理八数码问题是个典型的状态图搜索问题。搜索方式有两种基本的方式，即树式搜索和线式搜索。搜索策略大体有盲目搜索和启发式搜索两大类。盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。2.2 具体设计方法启发式搜索由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快

3、速找到问题的解。由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息就可以指导搜索。即可以利用启发信息来扩展节点的选择，减少搜索范围，提高搜索速度.启发函数设定。对于八数码问题，可以利用棋局差距作为一个度量。搜索过程中，差距会逐渐减少，最终为零，为零即搜索完成，得到目标棋局。3 .系统实施3.1 系统开发环境Windows操作系统、SQLServer200X3.2 系统主要功能介绍该搜索为一个搜索树。为了简

4、化问题，搜索树节点设计如下：structChess/棋盘intcellNN;/数码数组intValue;/评估值DirectionBelockDirec;/所屏蔽方向structChess*Parent;/父节点;intcellNN;数码数组：记录棋局数码摆放状态。intValue;评估值：记录与目标棋局差距的度量值DirectionBelockDirec;所屏蔽方向：一个屏蔽方向，防止回推。Direction:enumDirectionNone,Up,Down,Left,Right;/方向枚举structChess*Parent;父节点：指向父亲节点。下一步可以通过启发搜索算法构造搜索树。搜

5、索采用广度搜索方式，利用待处理队列辅助，逐层搜索(跳过劣质节点)。搜索过程如下:(1)、把原棋盘压入队列；(2)、从棋盘取出一个节点；(3)、判断棋盘估价值，为零则表示搜索完成，退出搜索；(4)、扩展子节点，即从上下左右四个方向移动棋盘，生成相应子棋盘；(5)、对子节点作评估，是否为优越节点(子节点估价值小于或等于父节点则为优越节点)，是则把子棋盘压入队列，否则抛弃;(6)、跳到步骤(2);3.3 处理流程图-3 -方向n);3.4 核心源程序#includestdio.h#includestdlib.h#includetime.h#includestring.h#include#includ

6、eusingnamespacestd;constintN=3;/3*3棋盘constintMax_Step=30;/最大搜索深度enumDirectionNone,Up,Down,Left,Right;/structChess/棋盘intcellNN;/数码数组intValue;/评估值DirectionBelockDirec;/所屏蔽方向structChess*Parent;/父节点;/打印棋盘voidPrintChess(structChess*TheChess)printf(for(inti=0;iN;i+)printf(t);for(intj=0;jcellij);printf(n);

7、printf(tttt差距:%dn,TheChess-Value);/移动棋盘structChess*MoveChess(structChess*TheChess,DirectionDirect,boolCreateNewChess)structChess*NewChess;/获取空闲格位置inti,j;for(i=0;iN;i+)boolHasGetBlankCell=false;for(j=0;jcellij=0)HasGetBlankCell=true;break;if(HasGetBlankCell)break;/移动数字intt_i=i,t_j=j;boolAbleMove=true

8、;switch(Direct)caseUp:t_i+;if(t_i=N)AbleMove=false;break;caseDown:t_i-;if(t_i=N)AbleMove=false;break;caseRight:t_j-;if(t_j0)AbleMove=false;break;if(!AbleMove)/不可以移动则返回原节点returnTheChess;if(CreateNewChess)NewChess=newChess();for(intx=0;xN;x+)for(inty=0;ycellxy=TheChess-cellxy;elseNewChess=TheChess;New

9、Chess-cellij=NewChess-cellt_it_j;NewChess-cellt_it_j=0;returnNewChess;/初始化一个初始棋盘structChess*RandomChess(conststructChess*TheChess)intM=30;/随机移动棋盘步数structChess*NewChess;NewChess=newChess();memcpy(NewChess,TheChess,sizeof(Chess);srand(unsigned)time(NULL);for(inti=0;iM;i+)intDirect=rand()%4;/printf(%dn

10、,Direct);NewChess=MoveChess(NewChess,(Direction)Direct,false);returnNewChess;/估价函数intAppraisal(structChess*TheChess,structChess*Target)intValue=0;for(inti=0;iN;i+)for(intj=0;jcellij!=Target-cellij)Value+;TheChess-Value=Value;returnValue;/搜索函数structChess*Search(structChess*Begin,structChess*Target)Ch

11、ess*p1,*p2,*p;intStep=0;/深度p=NULL;queueQueue1;Queue1.push(Begin);/搜索dop1=(structChess*)Queue1.front();Queue1.pop();for(inti=1;iBelockDirec)/跳过屏蔽方向continue;p2=MoveChess(p1,Direct,true);/移动数码if(p2!=p1)/数码是否可以移动Appraisal(p2,Target);/对新节点估价if(p2-ValueValue)/是否为优越节点p2-Parent=p1;switch(Direct)/设置屏蔽方向,防止往回

12、推caseUp:p2-BelockDirec=Down;break;caseDown:p2-BelockDirec=Up;break;caseLeft:p2-BelockDirec=Right;break;caseRight:p2-BelockDirec=Left;break;Queue1.push(p2);/存储节点到待处理队列if(p2-Value=0)/为0则,搜索完成p=p2;i=5;else- 9 -deletep2;/为劣质节点则抛弃p2=NULL;Step+;if(StepMax_Step)returnNULL;while(p=NULL|Queue1.size()=0);retu

13、rnp;main()Chess*Begin,Target,*T;/设定目标棋盘012,345,678for(inti=0;iN;i+)for(intj=0;jParent=NULL;Begin-BelockDirec=None;Target.Value=0;printf(目标棋盘:n);PrintChess(&Target);printf(初始棋盘:n);PrintChess(Begin);/图搜索T=Search(Begin,&Target);/打印if(T)/*把路径倒序*/Chess*p=T;stackStack1;while(p-Parent!=NULL)Stackl.push(p);

14、p=p-Parent;printf(搜索结果:n);while(!Stack1.empty()PrintChess(Stack1.top();Stack1.pop();printf(n完成!);elseprintf(搜索不到结果.深度为dn,Max_Step);scanf(%d,T);3.5 系统运行结果4 .开发心得4.1 设计存在的问题完全能解决简单的八数码问题，但对于复杂的八数码问题还是无能为力。4.2 进一步改进提高的设想可以改变数码规模（N）,来扩展成N*N的棋盘，即扩展为N数码问题的求解过程。2、内存泄漏。由于采用倒链表的搜索树结构，简化了数据结构，但有部分被抛弃节点的内存没有很好的处理，所以会造成内存泄漏;3、采用了屏蔽方向，有效防止往回搜索（节点的回推），但没能有效防止循环搜索，所以不能应用于复杂度较大的八数码问题；4.3 经验和体会通过独立完成本次课程设计，我对这门课程有了更加深刻的理解。在对八数码的分析、设计中，碰到很多概念上很模糊的问题，通过查阅相关资料，问题得到了解决，设计工作也顺利进行。另外，通过运用数据库连接技术，我对数据库编程技术也有了一定的了解和认识,对于人工智能系统这门课有了极大的兴趣，希望通过以后的学习继续加深这方面相关知识的掌握。-11 -5 .参考文献1 王汝传.计算机图形学M.北京：人