高中信息技术 浙教版选修5 5.2盲目搜索(共13张PPT)

盲目搜索 盲目搜索，是按预定的搜索策略进行的搜索并且不使用搜索过程中获得的中间信息来改进搜索策略。因此这种搜索方法具有盲目性，搜索效率不高，不便于复杂问题的求解。但是用它来求解一些比较简单的问题却是十分有效的，所以它的用途仍然非常广泛。 本节介绍两种最基本的盲目搜索方法，即广度优先搜索和深度优先搜索。了解这两种搜索方法的具体搜索过程，将有助于我们学习其他搜索方法。 2 1 OPEN表与CLOSED表 在搜索过程中保留所有使用定规则后生成的状态图记录，并把它们按顺序链接起来，这就是搜索过程所使用的图搜索策略。一个成功的图搜索策略，将会生成包含目标节点在内的一种图搜索过程。这种搜索过程可以描述成一个算法： “从初始状态节点出发，用规则不断地生成新的状态节点（在状态图中，一个节点的子节点按扩展的顺序从左到右排列），扩展搜索图。在扩展过程中，对那些不能生成后续节点的节点进行标记，因而扩展都是从非标记节点延伸的，直至找到满足目标状态的节点。” 由此可见，搜索过程就是寻找从初始状态到目标状态的操作序列的过程。因为大部分搜索过程的工作量都非常大，所以通常需要借助计算机来完成。然而，正如上述算法所描述的，在搜索过程中，对节点进行标记是使搜索能够有条不紊地进行下去的必要条件。那么，在计算机进行搜索的过程中，是怎样标记这些节点的呢？为此，可构造两个表，即OPEN表和CLOSED表，来实现节点的标记和控制整个搜索过程。 4 OPEN表用于存放刚生成的节点，其形式如下表所示，节点在OPEN表中排列的顺序不同对应着不同的搜索策略。稍后，会对此以详细说明。 CLOSED表用于存放将要扩展或者已扩展的节点，其形式如下表所示。 5 2 广度优先搜索 广度优先搜索又称宽度优先搜索。它的基本思想是：从初始节点S 开始，逐层地对节点进行扩展并考察它是否为目标节点在第n层的节点没有全部扩展并考察之前，不对第n+1层的节点进行扩展。OPEN表中的节点总是按进入的先后次序排列，先进入的节点排在前面，后进入的节点排在后面。下面来介绍下广度优先搜索过程，同时讨论如何构建和修改OPEN表和CLOSED表，并利用这两个表来控制搜索过程逐步进行下去。 0 7 从搜索过程中可以看出，随着搜索的一步一步进行，图G也是在不断地变化，构成一个树型的有向图，