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

1、商学院授课论文关于文题盲目的搜索策略及其实际应用研究专业年度08订正科24组课程的名称叫做自动智能领导人民教师刘文江学生姓吴铮煌学号200818131023取得成绩教务处制二零十一年十月十日盲目的搜索策略及其实际应用研究摘要：搜索策略是自动智能研究的主攻方向之一，采用不同的搜索策略在解题过程中也存在差异.针对八数字搜索求解分析，运用盲目的搜索中的广度优先搜索算法和宽度搜索算法实现，比较广度优先搜索算法和宽度搜索算法，做评估两搜索算法的优劣关牛鼻子字：搜索策略深度优先宽度优先八数字一盲目的图检索策略地图检索策略分为两类：被称为盲目的的地图检索策略和没有信息的地图检索策略；另一类被称为启发式文明棍

2、检索策略，也称为有信息的格拉夫检索策略。 盲目的搜索基于某种预定的固定搜索方法来进行搜索，而不使用关于该问题的信息。 最常见的两种无信息地图搜索策略是宽度优先搜索和深度优先搜索。1.1宽度优先搜索2它从根结点(开始节点)开始，逐层搜索。 也就是说，节点会逐层扩展。 分层扩展是指在上一层节点的扩展完成之后，进行下一层节点的扩展，直到获得目标节点为止。该搜索方案的优点在于，虽然能够确保如果存在某种解，则最终找到从源节点到目的地节点的最短路径的解，但是它具有搜索过程较长的缺点。1.2深度优先搜索它从根结点开始，首先扩张新生成的节点，即沿着搜索树的深度发展，一直持续到没有后续节点，改变路径。 搜索树的

3、各层总是只扩展一个子节点，在没有向纵深继续前进(到达叶结点或受到深度限制)之前，从当前节点返回上位节点，向别的方向前进。 这种方法的搜索树是从树根逐个形成的。因为有解的问题树中有可能包含无限分支，所以深度优先搜索如果误入无限分支(即深度无限)中就找不到目的节点。 为了避免如此，当实施该方法时，深度优先搜索策略是不完整的，因为确定了深度边界，并且如果搜索到达了该深度边界并且还没有找到目标，则返回到重新搜索。 另外，应用该政策得到的解不一定是最佳解(最短路径)。2深度优先或宽度优先解决8数字(参照附录)【八数字问题】5所谓八数码问题，是指将分别标记有数字1、2、3、8的八张正方形数码卡任意放置在一

4、张33张数码盘上的男同性恋。 放卡片的时候请不要重叠。 于是，在33张数码光盘上留出了空间。 现在，根据只能一次性更换与空间相邻的数码卡和空间的原则，要求将任意配置的数码磁盘分阶段地配置在某种特殊的阵列中。解决八数字化问题的算法很多，盲目的是深度优先搜索、宽度优先搜索等搜索算法7。一八数字游戏问题的尺寸表示1.1状态说明在八数字问题中，我们将车辆号牌的排列位置抽象为一个序列，以便记录不同车辆号牌的排列位置。空白用0表示的话将初始状态：营销对象状态：的八数值问题从开始序列： 2，8，3，1，0，4，7，6，5 转换为营销对象序列 1，2，3，8，0 1.2操作员的说明关于八数字问题中的空间移动问

5、题，建立以下运算符：左移： 1上移： 2下移： 3； 右移： 4创建以下状态转变空格向右偏移了一头地，所以用4表示。1.3尺状态空间的数据结构结构节点。公共：在路径2； /path 0 isthelineoftheclosedboxpath 1 isthedirectionof将节点移动到其他节点内层； /layeristhedeepnumsofthenodeinthewholegraph字符串seq； /usingthestringtoachievethesequence；其中，string seq记录数字位置、path2和int layer。 path0表示该节点记录查询密码是closed

6、表中的第几个记录查询密码，path1是本查询密码节点的父节点。 layer指示在搜索到的树中的第几级。空间移动规则如表1所示。二十八数字游戏问题的盲目的搜索技术2.1宽度优先搜索2.1.1宽度优先搜索的搜索步骤将起点节点放入open表(如果该起点节点是终点节点，则得到解)如果open是空的表，则没有解，如果没有失败结束，则继续下一步将最初的节点(记作节点n )从open表中取下，放入closed的扩展节点表中扩展节点n。 如果没有后续节点，则转到步骤将n的所有后续节点放在open表的末尾，提供从那些后续节点向n移动的指针n的任意后续节点是营销对象节点时，发现解(追踪从营销对象节点到开头节点的路

7、径的反方向上)，正常结束，否则转移到第2步骤2.1.2宽度优先的成员数据结构字符串初始字符串、结果字符串；初始序列和结果序列打开表： seq队列ws _打开(特别说明的话，这里的seqqueue是我在自各儿实现的队列大板块，我想试试看，是否有用，所以我把它放到了计程仪程序里存储要扩展的节点。 在数据结构上，这是一个先进的先入先出队列封闭表格：向量ws _封闭；(栈内存由vector实现)存储扩展节点(包括具有后续节点的非终端节点和不具有后续节点的终端节点)扩展节点，不扩展节点宽优先搜索的扩展节点函数输入：要扩展的节点节点； 父节点(即节点)的closed表的编号no结果：扩展上下左右4个方向的

8、节点，存储在open表中。 如果生成节点有营销对象节点，则向最后的步骤移动的方向移动。卷影交换(卷影a、卷影b )字符交换函数输入：文字a、文字b结果：在序列中，交换a和b的位置(深度和宽度并用)void widesearch ()输入：无结果：从成员的初始序列到结果序列执行宽度优先搜索以获取搜索过程。布尔异或封闭(节点s )输入：被测定节点s结果：返回open或closed表中测试节点的真值2.2深度优先搜索2.2.1深度优先搜索的探索过程将开始节点s放入未扩展节点的open表(此时open表为栈内存，后进先出)。 如果此节点是营销对象节点，则得到解如果open是空的表，则不解或失败而终止将

9、第一个节点(记作节点n )从open表移动到closed表如果节点n的深度等于最大深度则返回扩展节点n，生成其所有后续节点，并将它们置于open表的开头。 如果没有后续节点，则转移到如果后续节点的任一节点是营销对象节点，则求出解(反向跟踪从营销对象节点到星空卫视节点的路径)，如果不正常结束，则转向2.2.2深度优先搜索的成员数据结构字符串初始字符串、结果字符串；初始序列和结果序列打开表：向量打开在深度优先搜索中，open表达式后一个出现的栈内存在这里由vector实现。封闭表格：向量ds _封闭在宽度优先搜索中，closed表以vector实现，并存储扩展了的节点(包括具有后续节点的非末端节点

10、和没有后续节点的末端节点)节点扩展，节点扩展扩展深度优先搜索节点函数输入：要扩展的节点节点； 父节点(即节点)的closed表的编号no结果：扩展上下左右4个方向的节点，存储在open表中。 如果在生成节点中存在营销对象节点，则向最后的步骤移动的方向移动卷影交换(卷影a、卷影b )字符交换函数输入：文字a、文字b结果：在序列中，交换a和b的位置(深度和宽度并用)void深度搜索()输入：无结果：从成员的初始序列到结果序列执行深度优先搜索以获取搜索过程。布尔isindsopenorclosed (节点s )输入：被测定节点s结果：返回open或closed表中测试节点的真值3例与分析初始状态以目

11、标状态片偏移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走了四步，花了0.027s的时间深度极限为20的情况如图3.1.4所示。图3.1.4步行了20步，所需时间为4.65s4结语从例子的结果来看，宽度优先搜索方法可以保证在搜索树中找到通向目的地节点的最短路径(所使用的运算符最少)，并且

12、只要节点之间能够到达，就必定能够找到最优的解。 在深度优先搜索中有深度界限，当探索深度达到深度界限时停止探索。 因此，深度优先搜索可能得不到结果，是不安全的搜索方法。 然而，当结果在搜索极限之内时，可以快速得到结果并且时间效率很高。 因而，对于深度优先搜索如何定义好的搜索极限是需要在下一步继续改进的方面。3深度优先搜索和广度优先搜索的优缺点6(1)宽度优先搜索可以在有解的情况下找到最佳解，但是深度优先搜索不同，不保证在第一次遇到某个状态时，找到到该状态的最短路径，也不保证一定找到解。(2)幅度优先保证找到解，但是有不利的分歧(各个状态相对多的情况)的话会花费时间。(3)搜索具有很多分歧的空间时

13、，深度优先搜索更有效率。 因为没有必要将给定层次的所有节点保存在open列表中(4)选择深度优先搜索还是幅度优先搜索的最好答案是仔细分析问题空间，并与该领域的专门人才进行讨论。 例如，对于国际象棋来说，宽度优先搜索是不可能的。 在更加简单的男同性恋中，仅能够进行宽度优先搜索并且也可能是防止丢失的唯一方法。附录：以宽度优先算法解决8数码(原代码)包括号包括号包括号定义最大层5/*最大扩展层数宏定义*/定义真1定义失败0定义空0建筑链接。数据，数据，数据。 /*八数字状态*/内层； /*此节点的层数*/struct link *下一步；强制链接*优先级；强行链接*关闭_头部；/*关闭表的根结点*/强制链接*打开_头部； /*open表的根结点*/我想买一个，我想买一个，我想买一个，我想买一个，我想买一个。/*函数名称： output()*/*功能说明：输出指针p指向的节点的数据*/我想买一个，我想买一个，我想买一个，我想买一个，我想买一个。void输出(结构链接* p )。英特里、j；威尔！=空值)