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

1、。商业专科学校课程文本研究文本标题的盲目搜索策略及其在实践中的应用专业年08师24班这门课程的名字是人工智能指的是指导员刘文强这个学生的姓是吴学生编号200818131023成就教务办公室系统2011年10月10日盲搜索策略的研究及其在实践中的应用搜索策略是人工智能的主要研究方向之一，不同的搜索策略在解决问题的过程中存在差异。在分析8位搜索的基础上，采用了盲搜索中的广度优先搜索算法和宽度搜索算法，并对广度优先搜索算法和宽度搜索算法进行了比较，评价了它们的优缺点。关键词：搜索策略；深度优先。宽度优先。数字文学学士1盲图搜索策略图搜索策略可以分为两种类型：一种称为盲图搜索策略，或者无信息图搜索策略

2、；另一种称为启发式搜索策略，也称为信息图搜索策略。盲目搜索是指按照事先确定的固定搜索方法进行搜索，而不使用问题的相关信息。两种最常用的非信息图搜索策略是宽度优先搜索和深度优先搜索。1.1宽度优先搜索2它从根节点(起始节点)开始，逐层搜索，即逐层扩展节点。所谓的逐层扩展意味着在前一层的节点被扩展之前，前一层的节点被扩展，直到获得目标节点。这种搜索方法的优点是如果有任何解，它可以保证找到从起始节点到目标节点的最短路径的解，但是它的缺点是搜索过程往往很长。1.2深度优先搜索3它从根节点开始，首先扩展新生成的节点，即沿着搜索树的深度发展，然后在没有后续节点时返回，并改变路径。也就是说，在搜索树的每一级

3、，只有一个子节点总是被扩展，并且它继续深入，直到它不能再前进(它到达叶节点或者受到深度的限制)，然后它从当前节点返回到较高级别的节点，并且继续向另一个方向前进。这种方法的搜索树是从树根开始逐渐形成的。因为有解的问题树可能包含无限个分支，所以如果深度优先搜索误入无限个分支，就不可能找到目标节点。为了避免这种情况，当实施该方法时，确定深度限制，并且当搜索达到该深度限制并且没有找到目标时，返回再次搜索，因此深度优先搜索策略是不完整的4。此外，通过应用该策略获得的解决方案不一定是最佳解决方案(最短路径)。2使用深度优先或宽度优先来求解8位数(见附录)八个数字问题 5八位数问题指的是一种游戏，其中八张标

4、有数字1，2，3，8的正方形数字卡片被随机放在一张33位数的圆盘上。玩牌时，要求不能重叠。然后，33的数字盘上出现了一个空格。现在，根据一次只有与空间相邻的数字卡可以与空间交换的原则，随机放置的数字盘逐渐排列成特殊的排列。有许多算法可以解决8位数的问题。失明是一种搜索算法，如深度优先搜索和宽度优先搜索7。1.用状态空间法表示八个数字游戏问题1.1状态描述在8位数问题中，我们将车牌的位置抽象成一个序列，用来记录不同码值的车牌位置。如果一个空格用0表示，那么初始状态为：和目标状态为：的八位数问题转化为起始序列为2，8，3，1，0，4，7，6，5的问题转化为目标序列为1，2，3，8，0，4，7，6，

5、5的问题。1.2操作员描述对于八位数问题中的空间移动，我们建立了以下运算符：左移：1；上移：2；下移：3；向右移动：4创建以下状态转换：空间向右移动一步，所以用4表示。1.3状态空间法的数据结构结构节点public:int路径2；/路径0是闭合框的直线，路径1是的方向/父节点移动到这个节点中间层；/layer是整个图中节点的深数值字符串seq/使用字符串实现序列；其中字符串seq记录数字位置、路径2和层间。路径0指示该节点记录在封闭表中的哪个记录，路径1是该记录节点的父节点。图层指示搜索树中的图层。空间运动的规则如表1所示。8个数字游戏问题的盲搜索技术2.1宽度优先搜索2.1.1宽度优先搜索的

6、搜索步骤(1)将起始节点放在OPEN表中(如果起始节点是目标节点，则得到解)2如果OPEN是一个空表，则没有解决方案，并且无法退出；否则，继续下一步将第一个节点(作为节点N)移出开放表，并将其放入封闭扩展节点表中展开节点n.如果没有后续节点，转到步骤将N的所有后继节点放在OPEN表的末尾，并提供从这些后继节点返回N的指针如果N的任何一个后继节点是目标节点，则找到一个解(从目标节点到起始节点的路径是通过后向追踪得到的)，退出成功；否则，转到步骤2.1.2宽度优先的成员数据结构字符串初始化字符串，结果字符串；初始序列和结果序列开放表格：开放(特别是，这里的SeqQueue是一个由我自己实现的队列模

7、板，因为我想尝试一下，所以我把它放入程序中并尝试一下。)存储要扩展的节点。就数据结构而言，它是一个先进先出队列封闭表：向量ws _ closed(堆栈是用vector实现的)是存储扩展节点(包括有后继节点的非端节点和没有后继节点的端节点)节点扩展(节点节点，整数)宽度优先搜索的扩展节点函数输入：节点；待扩展；父节点(即节点节点)在封闭表中没有编号结果：上、下、左、右方向的节点被展开并存储在开放表中。如果生成的节点中有目标节点，则返回到最后一个移动方向。无效交换(char a，char b)字符交换功能输入：字符a，字符b结果：在序列中，甲和乙的位置互换(深度和宽度的组合)void WideSe

8、arch()输入：无结果：从初始序列到结果序列进行宽度优先搜索，得到搜索过程。bool是打开或关闭的节点输入：要测量的节点结果：返回开放或封闭表中测量节点的真实值2.2深度优先搜索2.2.1深度优先搜索过程将起始节点s放入未扩展节点的OPEN表中(此时，OPEN表是一个堆栈，后进先出)。如果该节点是目标节点，则获得解决方案(2)如果OPEN是一个空表，它没有解决方案，并且无法退出将第一个节点(作为节点N)从打开表移动到关闭表如果节点N的深度等于最大深度，转到展开节点N，生成其所有后续节点，并将它们放在OPEN表的前面。如果没有后续节点，请转到如果任一后继节点是目标节点，则得到一个解(反向跟踪从

9、目标节点到起始节点的路径)，退出成功；否则，转到2.2.2深度优先搜索的成员数据结构字符串初始化字符串，结果字符串；初始序列和结果序列开放表：矢量ds _开放在深度优先搜索中，开放表达式是一个后进先出堆栈，在这里是通过向量实现的。封闭表：向量ds_closed在宽度优先搜索中，封闭表由向量实现，向量存储扩展节点(包括有后继节点的非端节点和没有后继节点的端节点)整数扩展(节点节点，整数)深度优先搜索的扩展节点函数输入：节点；待扩展；父节点(即节点节点)在封闭表中没有编号结果：上、下、左、右方向的节点被展开并存储在开放表中。如果在生成的节点中有目标节点，返回到最后一个移动方向无效交换(char a

10、，char b)字符交换功能输入：字符a，字符b结果：在序列中，甲和乙的位置互换(深度和宽度的组合)void DeepSearch()输入：无结果：从初始序列到结果序列进行深度优先搜索，得到搜索过程。bool是打开或关闭的节点输入：要测量的节点结果：返回开放或封闭表中测量节点的真实值3个例子和分析初始状态被目标状态推回3.1.1宽度优先搜索程序运行如图3.1.1所示。图3.1.1如图所示，宽度优先搜索经历了4个步骤，耗时约0.65秒，得到的解是全局最优解。3.1.2深度优先搜索深度优先搜索结果与深度限制相关，因此当深度限制为3、5和20时，结果如下：当深度限制为3时，如图3.1.2所示。图3.

11、1.2当深度限制为5时，如图3.1.3所示。图3.1.3。它走了4步，花了0.027秒。当深度限制为20时，如图3.1.4所示。图3.1.4它走了20步，用了4.65秒。结论从实例的结果来看，宽度优先搜索方法可以保证在搜索树中找到到目标节点的最短路径(用最少的算子)，并且只要能够到达节点，就可以找到最优解。深度优先搜索有深度限制。当搜索深度达到深度限制时，搜索停止。因此，深度优先搜索可能得不到结果，这是一种不安全的搜索方法。然而，当结果在搜索限制内时，可以以高时间效率快速获得结果。因此，对于深度优先搜索，如何定义更好的搜索边界是下一步需要改进的地方。3深度优先搜索和宽度优先搜索的优缺点6(1)

12、当有解时，宽度优先搜索可以找到最优解，但深度优先搜索不同。它不能保证第一次遇到某个状态时会找到该状态的最短路径，也不能保证找到解决方案。(2)宽度优先可以保证找到解决方案，但是如果有一个不利的分支(有相对多的状态)，就会非常耗时。(3)如果您想搜索具有多个分支的空间，深度优先搜索更有效，因为它不需要将给定层的所有节点保存到开放列表中(4)选择深度优先搜索或宽度优先搜索的最佳答案是仔细分析问题空间并咨询该领域的专家。例如，对于国际象棋，宽度优先搜索是不可能的。在简单的游戏中，宽度优先搜索不仅是可能的，也是避免迷路的唯一方法。附录：用宽度优先算法求解8个数(源代码)#包括#包括#包括#定义max_

13、layer 5 /*最大扩展层的宏定义*/#定义true 1#定义失败0#定义null 0结构链接int数据33；/*八位数字状态*/中间层；/*该节点的层数*/结构链接*下一步；结构链接*之前；结构链接* close _ head/*的根节点/*关闭表*/结构链接* open _ head/*打开表的根节点*/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */*函数名：output()*/*功能描述：指针P *指向的节点输出数据/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *无效输出(结构链接*p)int i，j；而(p！=空) for(I=0；i3；I) /*线路输