《人工智能及其应用》课件第5章 搜索求解策略

第5章搜索求解策略技术日新月异，人类生活方式正在快速转变，这一切给人类历史带来了一系列不可思议的奇点。我们曾经熟悉的一切，都开始变得陌生。——约翰·冯·诺依曼,19585.1搜索的概念

搜索的主要过程①从初始或目的状态出发，并将它作为当前状态。②扫描操作算子集，将适用当前状态的一些操作算子作用在其上而得到新的状态，并建立指向其父结点的指针。③检查所生成的新状态是否满足结束状态，如果满足，则得到解，并可沿着有关指针从结束状态反向到达开始状态，给出一解答路径；否则，将新状态作为当前状态，返回第②步再进行搜索。5.2状态空间表示

5.2状态空间表示2.状态空间的图描述

状态空间可用有向图来描述，图的结点表示问题的状态，图的弧表示状态之间的关系，就是求解问题的步骤。

初始状态对应于实际问题的已知信息，是图中的根结点。问题的状态空间描述中，寻找从一种状态转换为另一种状态的某个操作算子序列就等价于在一个图中寻找某一路径。5.2状态空间表示

5.3盲目搜索回溯

回溯搜索是从初始状态出发，不停地试探性地寻找路径，直到到达目的或“不可解结点”，即“死胡同”为止。

回溯策略是当遇到不可解结点时就回溯到路径中最近的父结点上，查看该结点是否还有其他的子结点未被扩展。

若有，则沿这些子结点继续搜索；如果找到目标，就成功退出搜索，返回解题路径。5.3.1回溯

回溯搜索的算法用三张表来保存状态空间中的不同性质结点。(1)路径状态表

路径状态（PathStates，PS）表保存当前搜索路径上的状态。如果找到了目的，PS就是解路径上的状态有序集。(2)新的路径状态表的

新的路径状态（NewPathStates，NPS）表包含了等待搜索的状态，其后裔状态还未被搜索到，即未被生成扩展。(3)不可解状态表

不可解状态（NoSolvableStates，NSS）表列出了找不到解路径的状态。

如果在搜索中扩展出的状态是它的元素，则可立即将之排除，不必沿该状态继续搜索。5.3.1回溯

目标状态之一5.3.1回溯5.3.1回溯5.3.2广度优先搜索

5.3.3广度优先搜索

5.3.3广度优先搜索

5.3.3深度优先搜索

深度优先搜索（Depth-FirstSearch，DFS）是尽可能快地深入树中，每当搜索方法可以做出选择时，它选择最左(或最右)的分支的次序A、B、D、E、C、F、G访问节点来搜索状态，它类似树的先根遍历，是树的先根遍历的推广。5.3.3深度优先搜索

5.4启发式图搜索5.4.1启发式策略

启发式（Heuristic）策略就是利用与问题有关的启发信息引导搜索。在状态空间搜索中，启发式被定义成一系列操作算子，并能从状态空间中选择最有希望到达问题解的路径。

问题求解系统可在两种基本情况下运用启发式策略。

①由于在问题陈述和数据获取方面存在模糊性，可能会使一个问题没有一个确定的解，这就要求系统能运用启发式策略做出最有可能的解释。

②虽然一个问题可能有确定解，但是其状态空间特别大，搜索中生成扩展的状态数会随着搜索的深度呈指数级增长。5.4.1启发式策略

5.4.1启发式策略

5.4.2启发信息和估价函数启发信息按运用的方法不同可分为三种。

①陈述性启发信息，一般被用于更准确、更精炼地描述状态，使问题的状态空间缩小，如待求问题的特定状况等属于此类信息。

②过程性启发信息，一般被用于构造操作算子，使操作算子少而精，如一些规律性知识等属于此类信息。

③控制性启发信息，它是表示控制策略方面的知识，包括协调整个问题求解过程中所使用的各种处理方法、搜索策略、控制结构等有关的知识。5.4.2启发信息和估价函数

5.4.2启发信息和估价函数

5.4.3A搜索算法

5.4.3A搜索算法

5.4.3A搜索算法例5.7A搜索算法求解8拼图问题。

8拼图问题是3拼图问题的扩展，在一个3×3的方格盘上，放有1~8的数字，余下一格为空，空格移动规则同3拼图问题。5.4.3A搜索算法

5.4.3A搜索算法例5.7A搜索算法求解8拼图问题。

5.4.4A*搜索算法

A*搜索算法是由著名的人工智能学者Nilsson提出的，它是目前最有影响的启发式图搜索算法，也称为最佳图搜索算法。定义h*(𝑛)为状态𝑛到目的状态的最优路径的代价，则当A*搜索算法的启发函数h(n)小于等于h*(𝑛)，即满足h(n)≤h*(𝑛)