第4章搜索策略

人工智能 原理篇搜 索 策 略第四章本 章 导 读 现实世界中多数问题都是非结构化的，一般不能用直接求解的方法来求解这样的问题，而只能利用已有的知识一步一步地摸索着前进。因此，常常使用基于搜索策略的方法来求解问题。搜索策略是人工智能的基本求解策略之一，已在人工智能各领域得到了广泛应用。 本章主要介绍基于状态空间表示法的搜索策略，包括盲目搜索策略和启发式搜索策略。学习目标熟悉搜索的基本内容。理解搜索策略的思想。掌握宽度优先搜索、深度优先搜索和等代价搜索等盲目搜索策略。掌握 A 搜索和 A* 搜索等启发式搜索策略。目 录 4搜 索 概 述盲 目 搜 索 策 略启 发 式 搜 索 策 略010203搜 索 概 述01搜 索 的 概 念4.1.1 搜索就是根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条代价较小的推理路线，使问题得到解决的过程。 搜索是人工智能中的一个核心技术，是推理不可分割的一部分，它直接关系到智能系统的性能和运行效率。在搜索问题中，主要的工作是找到正确的搜索策略。搜索策略反映了状态空间或问题空间扩展的方法，也决定了状态或问题的访问顺序。 在人工智能中，通过运用搜索策略解决问题的基本思想是：首先把问题的初始状态（即起始节点）作为当前状态，选择适用的操作符对其进行操作，生成一组子状态（即后继节点），然后检查目标状态是否在其中出现。若出现，则搜索成功，找到了问题的解；若未出现，则按某种搜索策略从已生成的状态中再选一个状态作为当前状态。重复上述过程，直到目标状态出现或者不再有可供操作的状态及操作符为止。 在运用搜索策略求解问题的过程中，涉及的数据结构除了状态空间图之外，还需要两个辅助的数据结构，即存放已访问但未扩展节点的 OPEN 表，以及存放已扩展节点的CLOSED 表。状态空间图的搜索过程如左图所示。 搜索过程4.1.2（ 1 ）建立一个只含起始节点 的搜索图，并将 放入 OPEN 表中。（ 2 ）建立一个 CLOSED 表，并将其初始化为空表。（ 3 ）判断 OPEN 表是否为空表，若为空表，则失败退出；否则继续（ 4 ）。（ 4 ）选择 OPEN 表上的第一个节点（称为节点 n ），将其从 OPEN 表移出，并放入 CLOSED 表中。（ 5 ）判断节点 n 是否为目标节点。若 n 为目标节点，则有解并成功退出，此解为沿着指针从节点 n 到 的这条路径 [ 指针将在第（ 7 ）步中设置...