盲目搜索策略及其在实际中的应用研究

商务学院课 程 论 文论 文 题 目盲目搜索策略及其在实际中的应用研究专 业 年 级 08计科24班 课 程 名 称 人工智能 指 导 教 师 刘文江 学 生 姓 名 伍铖煌 学 号 200818131023 成 绩 教务处制二O一一 年 十 月 十日 盲目搜索策略及其在实际中的应用研究摘要：搜索策略是人工智能研究的主攻方向之一,采用不同的搜索策略在求解问题的过程中也会存在差异.通过对于八数码的搜索求解分析,采用盲目搜索中的广度优先搜索算法和宽度搜索算法进行实现,将广度优先搜索算法与宽度搜索算法进行比较,从而评价这两种搜索算法的优劣性.关键字：搜索策略；深度优先；宽度优先；八数码1 盲目的图搜索策略图搜索策略可分为两种：一种称为盲目的图搜索策略，或称无信息图搜索策略；而另一种称为启发式搜索策略，又称为有信息的图搜索策略。盲目搜索是不利用问题的有关信息, 而根据事先确定好的某种固定的搜索方法进行搜索1。最常用的两种无信息图搜索策略是宽度优先搜索和深度优先搜索。1.1 宽度优先搜索2它是从根节点（起始节点）开始，按层进行搜索，也就是按层来扩展节点。所谓按层扩展，就是前一层的节点扩展完毕后才进行下一层节点的扩展，直到得到目标节点为止。这种搜索方式的优点是，只要存在有任何解答的话，它能保证最终找到由起始节点到目标节点的最短路径的解，但它的缺点是往往搜索过程很长。1.2 深度优先搜索3它是从根节点开始，首先扩展最新产生的节点，即沿着搜索树的深度发展下去，一直到没有后继结点处时再返回，换一条路径走下去。就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进直到不能再前进（到达叶子节点或受到深度限制）时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。由于一个有解的问题树可能含有无穷分枝，深度优先搜索如果误入无穷分枝（即深度无限），则不可能找到目标节点。为了避免这种情况的出现，在实施这一方法时，定出一个深度界限，在搜索达到这一深度界限而且尚未找到目标时，即返回重找，所以，深度优先搜索策略是不完备的4。另外，应用此策略得到的解不一定是最佳解（最短路径）。2用深度优先或宽度优先解决8数码(见附录)【八数码问题】5 所谓八数码问题是指这样一种游戏：将分别标有数字1，2，3，8的八块正方形数码牌任意地放在一块33的数码盘上。放牌时要求不能重叠。于是，在33的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，将任意摆放的数码盘逐步摆成某种特殊的排列。 解决八数码问题的算法很多，盲目是搜索算法如深度优先搜索、宽度优先搜索等7。 1 八数码游戏问题的状态空间法表示 1.1 状态描述 我们在八数码问题中，将号码牌摆放的位置抽象成一个序列，用来记录不同码值的号码牌的摆放位置。 若用0来表示空格，则 将初始状态为：，目标状态为：的八数码问题转换为从开始序列：2,8,3,1,0,4,7,6,5 转换到目标序列 1,2,3,8,0,4,7,6,5 的问题。 1.2 操作符描述 对于八数码问题中空格的移动问题，我们建立以下操作符: 左移：1；上移：2；下移：3；右移：4 建立下列状态转换： 空格右移了一步，所以用4来表示。 1.3 状态空间法的数据结构 struct Node public: int path2;/path0 is the line of the closed box path1 is the direction of /the father node move to this node int layer;/layer is the deep nums of the node in the whole graph string seq; / using the string to achieve the sequence ; 其中string seq 记录数码位置，path2以及int layer。path0表示这个结点记录是closed表当中的第几个记录，path1 是本记录结点的父结点。Layer表示在已搜索的树当中是第几层。 空格移动规则如表1所示。 2 八数码游戏问题的盲目搜索技术 2.1 宽度优先搜索 2.1.1 宽度优先搜索的搜索步骤 把起始节点放到 OPEN 表中(如果该起始节点为一目标节点，则得到解) 如果 OPEN 是个空表，则无解，失败退出；否则继续下一步 把第一个节点(记作节点 n )从 OPEN 表移出，并把它放入 CLOSED 的已扩展节点表中 扩展节点 n 。如果没有后继节点，则转向第步 把 n 的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到 n 的指针 如果 n 的任一个后继节点是个目标节点，则找到一个解（反向追踪得到从目标节点到起始节点的路径），成功退出，否则转向第步 2.1.2 宽度优先的成员数据结构 string InitialString,ResultString; 初始序列以及结果序列 OPEN表：SeqQueue ws_open (特别说明，这里的SeqQueue 是我自己实现的队列模板，因为想试下有没有用，就放到程序里试了一下) 存放待扩展的节点，从数据结构上来说，它是一个先进先出的队列 CLOSED 表：vector ws_closed; （堆栈用vector实现） 是存放已被扩展过的节点（包括有后继节点的非端节点和无后继节点的端节点） int WsExpand(Node node,int No) 宽度优先搜索的扩展结点函数 输入：待扩展结点 node；父结点（即node结点）在closed表的编号No 结果：扩展上下左右四个方向的结点，并存入open表。如果生成结点中有目标结点，则返回最后一步移动的方向。 void swap(char &a,char &b ) 字符交换函数 输入：字符a，字符b 结果：在序列中，将a和b的位置交换 （深度和宽度合用） void WideSearch() 输入：无 结果：对成员初始序列到结果序列进行宽度优先搜索，得出搜索过程。 bool isInOpenOrClosed(Node s) 输入：待测结点s 结果：返回带测结点在open或closed表中的真值 2.2 深度优先搜索 2.2.1 深度优先搜索的搜索过程 把起始节点 S 放到未扩展节点的 OPEN 表（此时OPEN表是一个堆栈，后进先出）中。如果此节点为一目标节点，则得到解 如果 OPEN 为一空表，则无解、失败退出 把第一个节点(记作节点 n )从 OPEN 表移到 CLOSED 表 如果节点 n 的深度等于最大深度，则转向 扩展节点 n ，产生其全部后继节点，并把它们放入 OPEN 表的前头。如果没有后继节点，则转向 如果后继节点中有任一个节点为目标节点，则求得一个解（反向追踪从目标节点到起始节点的路径），成功退出；否则，转向 2.2.2 深度优先搜索的成员数据结构 string InitialString,ResultString; 初始序列以及结果序列 OPEN表： vector ds_open 在深度优先搜索中，open表式一个后进先出的堆栈，这里用vector来实现。 CLOSED 表：vector ds_closed 在宽度优先搜索中，closed表用vector来实现，是存放已被扩展过的节点（包括有后继节点的非端节点和无后继节点的端节点） int DsExpand(Node node,int No) 深度优先搜索的扩展结点函数 输入：待扩展结点 node；父结点（即node结点）在closed表的编号No 结果：扩展上下左右四个方向的结点，并存入open表。如果生成结点中有目标结点，则返回最后一步移动的方向 void swap(char &a,char &b ) 字符交换函数 输入：字符a，字符b 结果：在序列中，将a和b的位置交换 （深度和宽度合用） void DeepSearch() 输入：无 结果：对成员初始序列到结果序列进行深度优先搜索，得出搜索过程。 bool isInDSOpenOrClosed(Node s) 输入：待测结点s 结果：返回带测结点在open或closed表中的真值 3 例子及分析 初始状态通过目标状态倒推 3.1.1 宽度优先搜索 程序运行如图3.1.1所示。图3.1.1 如图所示，宽度优先搜索共走了4步，所用时间约为0.65秒，获得的解为全局最优解。 3.1.2 深度优先搜索 而深度优先搜索结果和深度界限有关，所以当深度界限分别为3,5,20时，结果如下： 当深度界限为3时，如图3.1.2所示。 图3.1.2当深度界限为5时，如图3.1.3所示。 图3.1.3走了4步，耗费时间0.027s 当深度界限为20时如图3.1.4所示。 图3.1.4走了20步，所用时间为4.65s 4 结束语 从例子的结果来看，宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径（所用操作符最少），只要结点间可以到达，就一定可以找到一个最优解。深度优先搜索具有深度界限，当搜索深度达到深度界限时，停止搜索。所以，深度优先搜索有可能会得不到结果，是一种不安全的搜索方法。但是当结果在搜索界限内时，可以快速的得到结果，时间效率高。故对于深度优先搜索，如何去定义一个较好的搜索界限，是下一步需要继续改进的方面。3深度优先搜索和宽度优先搜索的优缺点6(1)宽度优先搜索在有解的情况下可以找到最优解，但深度优先搜索不同，它不保证第一次碰到某个状态时，找到的就是到这个状态的最短路径，而且也不保证一定能找到解。(2)宽度优先可以保证找到解，但是如果存在一个不利的分支（各个状态相对很多的情况），那么会非常耗时。(3) 如果要搜索具有很多分支的空间，那么深度优先搜索的效率更高，因为它不必把给定层的所有结点保存到open列表中(4)选择深度优先搜索还是宽度优先搜索的最佳答案是仔细分析问题空间并向这个领域的专家咨询。例如，对于国际象棋来说，宽度优先搜索就是不可能的。在更简单的游戏中，宽度优先搜索不仅是可能的，而且可能是避免迷失的惟一方法。附录：利用宽度优先算法解决8数码（源代码）#include#include#include#define max_layer 5 /*最大扩展层数宏定义*/#define true 1#define fail 0#define null 0struct link int data33;/*八数码状态*/ int layer; /*该节点的层数*/ struct link *next; struct link *prior; ;struct link *close_head; /*Close表的根节点*/struct link *open_head;/*Open表的根节点*/*/* 函数名称：output()*/* 功能说明：输出指针P指向的节点的数据 */*/void output(struct link *p) int i,j; while(p!=NULL) for(i=0;i3;i+) /*行输出控制*/ for(j=0;jdataij);/*输出i行j列上的数据*/ printf(n); /*每输出一行数据，回车换行*/ printf(-n); /*输出一条横线以区分屏幕上其他节点数据*/ p-;/* 函数名称：compare*/* 功能说明：将指针Operate指向的节点中的数据与二维数组dest中的数据进行比较*/int compare(struct link *q,int dest33) int i,j,count=0; for(i=0;i3;i+) /*行比较控制*/ for(j=0;jdataij=destij) /*比较i行j列上的数据*/count+; /*计数器加一*/else /*只要发现有一个数据不相等*/*即返回 fail，宣告比较失败*/ j=3; /*强制推出for循环*/ i=3; /*强制推出for循环*/ return 0; if(count=9)/*相等的数据的个数与维数平方相等*/ return 1; /*表示数据都对应相等，返回true */* 函数名称：eight()*/ /* 功能说明：通过深度扩展的方式找出八数码问题从初始状态到目标状态的路径 */ int eight(struct link *open_head,int dest33) int i,j,zero_x,zero_y; /*0的横坐标，0的纵坐标*/ struct link *new_point; /*处理open表的一个临时指针*/ struct link *open_point=*open_head;/*open表操作指针1*/ struct link *close_point; while(open_link_point!=NULL) close_point=open_point; open_point-prior-next=NULL; open_point-; if(compare(close_point,dest)=1) printf(find solution); output(close_point); return 1; else if(close_point-layermax_layer) close_point-next=*open_point; close_point+; else for(i=0;i3;i+)/*获取0的坐标*/ for(j=0;jdataij=0) /*data or dest*/ zero_x=i;/*横坐标*/ zero_y=j;/*纵坐标*/ j=3; /*强制退出循环*/ i=3; /*强制退出循环*/ if(zero_x-1)=0)/*往上移*/ /*申请内存空间*/ new_point=(struct link *)malloc(sizeof(struct link); for(i=0;i3;i+)/*对新扩展的节点赋值*/ for(j=0;jdataij=close_point-dataij; new_point-datazero_xzero_y=new_point-datazero_x-1zero_y; new_point-datazero_x-1zero_y=0; open_point-next=*new_point; open_point+; if(zero_x+1)3)/*往下移*/ /*申请内存空间*/ new_point=(struct link *)malloc(sizeof(struct link); for(i=0;i3;i+)/*对新扩展的节点赋值*/ for(j=0;jdataij=close_point-dataij; new_point-datazero_xzero_y=new_point-datazero_x+1zero_y; new_point-datazero_x+1zero_y=0; open_point-next=*new_point; open_point+; if(zero_y-1)=0)/*0往右移*/ /*申请内存空间*/ new_point=(struct link *)malloc(sizeof(struct link); for(i=0;i3;i+)/*对新扩展的节点赋值*/ for(j=0;jdataij=close_point-dataij; new_point-datazero_xzero_y=new_point-datazero_xzero_y-1; new_point-datazero_xzero_y-1=0; open_point-next=*new_point; open_point+; if(zero_y+1)3)/*0往左移*/ /*申请内存空间*/ new_point=(struct link *)malloc(sizeof(struct link); for(i=0;i3;i+)/*对新扩展的节点赋值*/ for(j=0;jdataij=close_point-dataij; new_point-datazero_xzero_y=new_point-datazero_xzero_y+1; new_point-datazero_xzero_y+1=0; open_point-next=*new_point; open_point+; if(open_point=NULL) printf(no solution); /* 函数名称：main*/ void main() int i,j; int destination33; /*二维数组，用以存放目标状态*/ struct link *open_head=(struct link *)malloc(sizeof(struct link); /*申请一个节点空间* printf(The max dimention is 3); /*提醒用户八数码的维数大小*/ printf(Please input the initial state of :n); for(i=0;i3;i+) /*获取八数码的初始状态*/ for(j=0;jdataij); /*把初始状态存放在申请的节点中，即Open表*/ printf(Please input the final state of :n); for(i=0;i3;i+) /*获取八数码的目标状态*/ for(j=0;jlayer=0; /*初始化初始状态节点的层数为0，表示还为进行扩展 */ eight(open_head,destination); 参考文献1耿汝年 浅谈人工智能中的搜索策略山东轻工业学院学报 2005 年 20 卷 2 期(30-31)2马少平 图的深度优先遍历算法及运用电脑编程技巧与维护2011年卷 16 期(93-94)3耿汝年 无信息图搜索算法的改进研究山东轻工业学院学报2006年20卷2期(40-44)4殷永峰 深度优先搜索的优化算法计算机仿真 2011 第 07 期(20-23)5曾范清 求解八数码问题的算法比较福建电脑报 2008 第 12 期(3) 6龙振海 林泓 深度优先和宽度优先 计算机科学 2010 第 2 期7周浩 八数码问题DFS和BFS算法的设计与实现 电脑知识与技术 2011 第 22 期8钱莹 基于广度优先搜索的八数码问题解决方案 电脑学习 2008 第 01 期9刘翔 龚道雄 深度优先算法的仿真研究 制造业自动化 2011 第 11 期10钟声 基于深度优先的图匹配算法 计算机工程与科学 2008 第 12 期