1、盲目搜索就是无“向导”的搜索，启发式搜索就是有“向导”的搜索。启发式搜索由于时间和空间资源的限制，穷举法只能解决一些状态空间很小的简单问题，而对于那些大状态空间的问题，穷举法就不能胜任，往往会导致“组合爆炸”。所以引入启发式搜索策略。启发式搜索就是利用启发性信息进行制导的搜索。它有利于快速找到问题的解。由八数码问题的部分状态图可以看出，从初始节点开始，在通向目标节点的路径上，各节点的数码格局同目标节点相比较，其数码不同的位置个数在逐渐减少，最后为零。所以，这个数码不同的位置个数便是标志一个节点到目标节点距离远近的一个启发性信息，利用这个信息就可以指导搜索。即可以利用启发信息来扩展节点的选择，减
2、少搜索范围，提高搜索速度。 启发函数设定。对于八数码问题，可以利用棋局差距作为一个度量。搜索过程中，差距会逐渐减少，最终为零，为零即搜索完成，得到目标棋局。3. 系统实施Windows操作系统、SQL Server 200X3.2 系统主要功能介绍该搜索为一个搜索树。为了简化问题，搜索树节点设计如下：struct Chess/棋盘 int cellNN;/数码数组 int Value;/评估值 Direction BelockDirec;/所屏蔽方向 struct Chess * Parent;/父节点;int cellNN; 数码数组：记录棋局数码摆放状态。int Value; 评估值：记录
3、与目标棋局差距的度量值。Direction BelockDirec; 所屏蔽方向：一个屏蔽方向，防止回推。Direction ：enum DirectionNone,Up,Down,Left,Right;/方向枚举struct Chess * Parent; 父节点：指向父亲节点。下一步可以通过启发搜索算法构造搜索树。搜索采用广度搜索方式，利用待处理队列辅助，逐层搜索（跳过劣质节点）。搜索过程如下： （1）、把原棋盘压入队列； （2）、从棋盘取出一个节点； （3）、判断棋盘估价值，为零则表示搜索完成，退出搜索； （4）、扩展子节点，即从上下左右四个方向移动棋盘，生成相应子棋盘；（5）、对子节点
4、作评估，是否为优越节点（子节点估价值小于或等于父节点则为优越节点），是则把子棋盘压入队列，否则抛弃； （6）、跳到步骤（2）；3.3 处理流程图 #include stdio.hstdlib.htime.hstring.h#include stackusing namespace std;const int N=3;/3*3棋盘const int Max_Step=30;/最大搜索深度/方向 int cellNN;/父节点;/打印棋盘void PrintChess（struct Chess *TheChess） printf（-n）; for（int i=0;iN;i+） t for（int
5、j=0;jcellij）; ntttt差距:%dnValue）;/移动棋盘struct Chess * MoveChess（struct Chess * TheChess,Direction Direct,bool CreateNewChess） struct Chess * NewChess; /获取空闲格位置 int i,j; for（i=0; bool HasGetBlankCell=false; for（j=0; if（TheChess-cellij=0） HasGetBlankCell=true; break; if（HasGetBlankCell） /移动数字 int t_i=i,
6、t_j=j; bool AbleMove=true; switch（Direct） case Up: t_i+; if（t_i=N） AbleMove=false; case Down: t_i-; if（t_i case Right: t_j-; if（t_j ; if（!AbleMove）/不可以移动则返回原节点 return TheChess; if（CreateNewChess） NewChess=new Chess（）; for（int x=0;xx+） for（int y=0;ycellxy=TheChess-cellxy; else NewChess=TheChess;celli
7、j=NewChess-cellt_it_j;cellt_it_j=0; return NewChess;/初始化一个初始棋盘struct Chess * RandomChess（const struct Chess * TheChess） int M=30;/随机移动棋盘步数 memcpy（NewChess,TheChess,sizeof（Chess）; srand（unsigned）time（NULL）;M; int Direct=rand（）%4; /printf（,Direct）; NewChess=MoveChess（NewChess,（Direction） Direct,false）
8、;/估价函数int Appraisal（struct Chess * TheChess,struct Chess * Target） int Value=0;cellij!=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
9、=（struct Chess *）Queue1.front（）; Queue1.pop（）; for（int i=1;=4;i+）/分别从四个方向推导出新子节点 Direction Direct=（Direction）i; if（Direct=p1-BelockDirec）/跳过屏蔽方向 continue; p2=MoveChess（p1,Direct,true）;/移动数码 if（p2!=p1）/数码是否可以移动 Appraisal（p2,Target）;/对新节点估价 if（p2-ValueValue）/是否为优越节点 p2-Parent=p1; switch（Direct）/设置屏蔽方向
10、,防止往回推p2-BelockDirec=Down;break;BelockDirec=Up;BelockDirec=Right;BelockDirec=Left; Queue1.push（p2）;/存储节点到待处理队列Value=0）/为0则,搜索完成 p=p2; i=5; else delete p2;/为劣质节点则抛弃 p2=NULL; Step+; if（StepMax_Step） return NULL; while（p=NULL | Queue1.size（）Parent=NULL;BelockDirec=None; Target.Value=0;目标棋盘: PrintChess（
11、&初始棋盘: PrintChess（Begin）; /图搜索 T=Search（Begin,& /打印 if（T） /*把路径倒序*/ Chess *p=T; stackStack1; while（p-Parent!=NULL） Stack1.push（p）; p=p-Parent;搜索结果: while（!Stack1.empty（） PrintChess（Stack1.top（）; Stack1.pop（）;n完成! else搜索不到结果.深度为%dn,Max_Step）; scanf（%d,T）;3.5 系统运行结果4. 开发心得4.1 设计存在的问题 完全能解决简单的八数码问题，但对于
12、复杂的八数码问题还是无能为力。4.2 进一步改进提高的设想 可以改变数码规模（N），来扩展成N*N的棋盘，即扩展为N数码问题的求解过程。2、 内存泄漏。由于采用倒链表的搜索树结构，简化了数据结构，但有部分被抛弃节点的内存没有很好的处理，所以会造成内存泄漏；3、采用了屏蔽方向，有效防止往回搜索（节点的回推），但没能有效防止循环搜索，所以不能应用于复杂度较大的八数码问题；4.3 经验和体会通过独立完成本次课程设计，我对这门课程有了更加深刻的理解。在对八数码的分析、设计中，碰到很多概念上很模糊的问题，通过查阅相关资料，问题得到了解决，设计工作也顺利进行。另外，通过运用数据库连接技术，我对数据库编程技
13、术也有了一定的了解和认识，对于人工智能系统这门课有了极大的兴趣，希望通过以后的学习继续加深这方面相关知识的掌握。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.
