资源描述：
《盲目搜索策略及其在实际中的应用研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、商务学院课程论文论文题目盲目搜索策略及其在实际中的应用研究专业年级08计科24班课程名称人工智能指导教师刘文江学生姓名伍铖煌学号200818131023成绩教务处制二O一一年十月十日盲目搜索策略及其在实际中的应用研究摘要：搜索策略是人工智能研究的主攻方向之一,采用不同的搜索策略在求解问题的过程中也会存在差异.通过对于八数码的搜索求解分析,采用盲目搜索中的广度优先搜索算法和宽度搜索算法进行实现,将广度优先搜索算法与宽度搜索算法进行比较,从而评价这两种搜索算法的优劣性.关键字：搜索策略；深度优先；宽度优先；八数码1盲目的图搜索策略图搜索策略可分为两种：一种称为盲目的
2、图搜索策略，或称无信息图搜索策略； 而另一种称为启发式搜索策略，又称为有信息的图搜索策略。盲目搜索是不利用问题的有关信息,而根据事先确定好的某种固定的搜索方法进行搜索[1]。最常用的两种无信息图搜索策略是宽度优先搜索和深度优先搜索。1.1宽度优先搜索[2]它是从根节点（起始节点）开始，按层进行搜索，也就是按层来扩展节点。所谓按层扩展，就是前一层的节点扩展完毕后才进行下一层节点的扩展，直到得到目标节点为止。这种搜索方式的优点是，只要存在有任何解答的话，它能保证最终找到由起始节点到目标节点的最短路径的解，但它的缺点是往往搜索过程很长。1.2深度优先搜索[3]它是从根
3、节点开始，首先扩展最新产生的节点，即沿着搜索树的深度发展下去，一直到没有后继结点处时再返回，换一条路径走下去。就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进直到不能再前进（到达叶子节点或受到深度限制）时，才从当前节点返回到上一级节点，沿另一方向又继续前进。这种方法的搜索树是从树根开始一枝一枝逐渐形成的。由于一个有解的问题树可能含有无穷分枝，深度优先搜索如果误入无穷分枝（即深度无限），则不可能找到目标节点。为了避免这种情况的出现，在实施这一方法时，定出一个深度界限，在搜索达到这一深度界限而且尚未找到目标时，即返回重找，所以，深度优先搜索策略是不完备的
4、[4]。另外，应用此策略得到的解不一定是最佳解（最短路径）。2用深度优先或宽度优先解决8数码(见附录)【八数码问题】[5]所谓八数码问题是指这样一种游戏：将分别标有数字1，2，3，…，8的八块正方形数码牌任意地放在一块3×3的数码盘上。放牌时要求不能重叠。于是，在3×3的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，将任意摆放的数码盘逐步摆成某种特殊的排列。 解决八数码问题的算法很多，盲目是搜索算法如深度优先搜索、宽度优先搜索等[7]。 1八数码游戏问题的状态空间法表示 1.1状态描述 我们在八数码问题中，将号码牌摆放
5、的位置抽象成一个序列，用来记录不同码值的号码牌的摆放位置。 若用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状态空间法的数据结构 structNode { public: intpath[2];//path[0]isthelineofthe
6、closedboxpath[1]isthedirectionof //thefathernodemovetothisnode intlayer;//layeristhedeepnumsofthenodeinthewholegraph stringseq;//usingthestringtoachievethesequence }; 其中stringseq记录数码位置，path[2]以及intlayer。path[0]表示这个结点记录是closed表当中的第几个记录，path[1]是本记录结点的父结点。Layer表示在已搜索的树当中是第几层。 空格移动
7、规则如表1所示。 2八数码游戏问题的盲目搜索技术 2.1宽度优先搜索 2.1.1宽度优先搜索的搜索步骤 ①把起始节点放到OPEN表中(如果该起始节点为一目标节点，则得到解) ②如果OPEN是个空表，则无解，失败退出；否则继续下一步 ③把第一个节点(记作节点n)从OPEN表移出，并把它放入CLOSED的已扩展节点表中 ④扩展节点n。如果没有后继节点，则转向第②步 ⑤把n的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针 ⑥如果n的任一个后继节点是个目标节点，则找到一个解（反向追踪得到从目标节点到起始节点的路径），成功退出，否则转
8、向第②步 2.1.2宽
