人工智能与专家系统课程设计.doc

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操作系统、SQL Server 200X3.2 系统主要功能介绍该搜索为一个搜索树。为了简化问题，搜索树节

4、点设计如下：struct Chess/棋盘 int cellNN;/数码数组 int Value;/评估值 Direction BelockDirec;/所屏蔽方向 struct Chess * Parent;/父节点;int cellNN; 数码数组：记录棋局数码摆放状态。int Value; 评估值：记录与目标棋局差距的度量值。Direction BelockDirec; 所屏蔽方向：一个屏蔽方向，防止回推。Direction ：enum DirectionNone,Up,Down,Left,Right;/方向枚举struct Chess * Parent; 父节点：指向父亲节点。下一步可

5、以通过启发搜索算法构造搜索树。搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点）。搜索过程如下： （1）、把原棋盘压入队列； （2）、从棋盘取出一个节点； （3）、判断棋盘估价值，为零则表示搜索完成，退出搜索； （4）、扩展子节点，即从上下左右四个方向移动棋盘，生成相应子棋盘；（5）、对子节点作评估，是否为优越节点（子节点估价值小于或等于父节点则为优越节点），是则把子棋盘压入队列，否则抛弃； （6）、跳到步骤（2）；3.3 处理流程图3.4 核心源程序#include stdio.h#include stdlib.h#include time.h#include string.

6、h#include #include using namespace std;const int N=3;/3*3棋盘const int Max_Step=30;/最大搜索深度enum DirectionNone,Up,Down,Left,Right;/方向struct Chess/棋盘 int cellNN;/数码数组 int Value;/评估值 Direction BelockDirec;/所屏蔽方向 struct Chess * Parent;/父节点;/打印棋盘void PrintChess(struct Chess *TheChess) printf(-n); for(int i=

7、0;iN;i+) printf(t); for(int j=0;jcellij); printf(n); printf(tttt差距:%dn,TheChess-Value);/移动棋盘struct Chess * MoveChess(struct Chess * TheChess,Direction Direct,bool CreateNewChess) struct Chess * NewChess; /获取空闲格位置 int i,j; for(i=0;iN;i+) bool HasGetBlankCell=false; for(j=0;jcellij=0) HasGetBlankCell=

8、true; break; if(HasGetBlankCell) break; /移动数字 int t_i=i,t_j=j; bool AbleMove=true; switch(Direct) case Up: t_i+; if(t_i=N) AbleMove=false; break; case Down: t_i-; if(t_i=N) AbleMove=false; break; case Right: t_j-; if(t_j0) AbleMove=false; break; ; if(!AbleMove)/不可以移动则返回原节点 return TheChess; if(Create

9、NewChess) NewChess=new Chess(); for(int x=0;xN;x+) for(int y=0;ycellxy=TheChess-cellxy; else NewChess=TheChess; NewChess-cellij=NewChess-cellt_it_j; NewChess-cellt_it_j=0; return NewChess;/初始化一个初始棋盘struct Chess * RandomChess(const struct Chess * TheChess) int M=30;/随机移动棋盘步数 struct Chess * NewChess;

10、NewChess=new Chess(); memcpy(NewChess,TheChess,sizeof(Chess); srand(unsigned)time(NULL); for(int i=0;iM;i+) int Direct=rand()%4; /printf(%dn,Direct); NewChess=MoveChess(NewChess,(Direction) Direct,false); return NewChess;/估价函数int Appraisal(struct Chess * TheChess,struct Chess * Target) int Value=0;

11、for(int i=0;iN;i+) for(int j=0;jcellij!=Target-cellij) Value+; TheChess-Value=Value; return Value;/搜索函数struct Chess * Search(struct Chess* Begin,struct Chess * Target) Chess * p1,*p2,*p; int Step=0;/深度 p=NULL; queue Queue1; Queue1.push(Begin); /搜索 do p1=(struct Chess *)Queue1.front(); Queue1.pop();

12、for(int i=1;iBelockDirec)/跳过屏蔽方向 continue; p2=MoveChess(p1,Direct,true);/移动数码 if(p2!=p1)/数码是否可以移动 Appraisal(p2,Target);/对新节点估价 if(p2-ValueValue)/是否为优越节点 p2-Parent=p1; switch(Direct)/设置屏蔽方向,防止往回推 case Up:p2-BelockDirec=Down;break; case Down:p2-BelockDirec=Up;break; case Left:p2-BelockDirec=Right;brea

13、k; case Right:p2-BelockDirec=Left;break; Queue1.push(p2);/存储节点到待处理队列 if(p2-Value=0)/为0则,搜索完成 p=p2; i=5; else delete p2;/为劣质节点则抛弃 p2=NULL; Step+; if(StepMax_Step) return NULL; while(p=NULL | Queue1.size()=0); return p;main() Chess * Begin,Target,* T; /设定目标棋盘 0 1 2,3 4 5,6 7 8 for(int i=0;iN;i+) for(i

14、nt j=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) Stack1.push(p); p=p-Parent; printf(搜索结果:n); while(!Stack1.empty() Prin

15、tChess(Stack1.top(); Stack1.pop(); printf(n完成!); else printf(搜索不到结果.深度为%dn,Max_Step); scanf(%d,T);3.5 系统运行结果4. 开发心得4.1 设计存在的问题完全能解决简单的八数码问题，但对于复杂的八数码问题还是无能为力。4.2 进一步改进提高的设想可以改变数码规模（N），来扩展成N*N的棋盘，即扩展为N数码问题的求解过程。2、 内存泄漏。由于采用倒链表的搜索树结构，简化了数据结构，但有部分被抛弃节点的内存没有很好的处理，所以会造成内存泄漏；3、 采用了屏蔽方向，有效防止往回搜索（节点的回推），但没能

16、有效防止循环搜索，所以不能应用于复杂度较大的八数码问题；4.3 经验和体会通过独立完成本次课程设计，我对这门课程有了更加深刻的理解。在对八数码的分析、设计中，碰到很多概念上很模糊的问题，通过查阅相关资料，问题得到了解决，设计工作也顺利进行。另外，通过运用数据库连接技术，我对数据库编程技术也有了一定的了解和认识，对于人工智能系统这门课有了极大的兴趣，希望通过以后的学习继续加深这方面相关知识的掌握。5. 参考文献 1王汝传.计算机图形学M.北京：人民邮电出版社，1999：123130.2刘榴娣，刘明奇，党长民.实用数字图像处理M.北京：北京理工大学出版，2000：1225.3丁兆海.Delphi基础教程M.北京：电子工业出版社，1999.4王小华.Delphi 5程序设计与控件参考M.北京：电子工业出版社，1999:70120.5赵子江.多媒体技术基础M.北京：机械工业出版社，2001：118130.6段来盛，郑城荣，曹恒.Delphi实战演练M.北京：人民邮政出版社，2002：8095.- 12 -