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

商务学院课 程 论 文论 文 题 目盲目搜索策略及其在实际中的应用研究专 业 年 级 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 初始序列以及结果序列 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 /*八数码状态*/ 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;idataij);/*输出 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;idataij=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;idataij=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;idataij=close_point-dataij; new_point-datazero_xzero_y=new_p