1、第第5 5章章 搜索搜索求解策略求解策略 技术技术日新月异，人类生活方式正在快日新月异，人类生活方式正在快速转变，这一切给人类历史带来了一系列速转变，这一切给人类历史带来了一系列不可思议的奇点。我们曾经熟悉的一切，不可思议的奇点。我们曾经熟悉的一切，都开始变得陌生。都开始变得陌生。约翰冯诺依曼,19585.1 5.1 搜索的概念搜索的概念 搜索搜索的主要过程的主要过程 从初始或目的状态出发，并将它作为当前状态。从初始或目的状态出发，并将它作为当前状态。扫描操作算子集，将适用当前状态的一些操作算子作用在其上扫描操作算子集，将适用当前状态的一些操作算子作用在其上而得到新的状态，并建立指向其父结点的
2、指针。而得到新的状态，并建立指向其父结点的指针。检查所生成的新状态是否满足结束状态，如果满足，则得到解，检查所生成的新状态是否满足结束状态，如果满足，则得到解，并可沿着有关指针从结束状态反向到达开始状态，给出一解答路并可沿着有关指针从结束状态反向到达开始状态，给出一解答路径；否则，将新状态作为当前状态，返回第步再进行搜索。径；否则，将新状态作为当前状态，返回第步再进行搜索。5.2 5.2 状态空间表示状态空间表示5.2 5.2 状态空间表示状态空间表示2 2.状态空间的图描述状态空间的图描述 状态空间状态空间可用有向图来描述，图的结点表示问题的状态，图可用有向图来描述，图的结点表示问题的状态，
3、图的弧表示状态之间的关系，就是求解问题的步骤的弧表示状态之间的关系，就是求解问题的步骤。初始状态初始状态对应于实际问题的已知信息，是图中的根结点。问对应于实际问题的已知信息，是图中的根结点。问题的状态空间描述中，寻找从一种状态转换为另一种状态的某个题的状态空间描述中，寻找从一种状态转换为另一种状态的某个操作算子序列就等价于在一个图中寻找某一路径。操作算子序列就等价于在一个图中寻找某一路径。5.2 5.2 状态空间表示状态空间表示5.3 5.3 盲目搜索盲目搜索 回溯回溯 回溯搜索是从初始状态出发，不停地试探性地寻找路径，直回溯搜索是从初始状态出发，不停地试探性地寻找路径，直到到达目的或到到达目
4、的或“不可解结点不可解结点”，即，即“死胡同死胡同”为止为止。回溯回溯策略是当遇到不可解结点时就回溯到路径中最近的父结策略是当遇到不可解结点时就回溯到路径中最近的父结点上，查看该结点是否还有其他的子结点未被扩展点上，查看该结点是否还有其他的子结点未被扩展。若若有，则沿这些子结点继续搜索；如果找到目标，就成功退有，则沿这些子结点继续搜索；如果找到目标，就成功退出搜索，返回解题路径。出搜索，返回解题路径。5.3.15.3.1回溯回溯 回溯回溯搜索的算法用三张表来保存状态空间中的不同性质结点。搜索的算法用三张表来保存状态空间中的不同性质结点。(1)(1)路径状态表路径状态表 路径状态（路径状态（Pa
5、th StatesPath States，PSPS）表保存当前搜索路径上的状态。）表保存当前搜索路径上的状态。如果找到了目的，如果找到了目的，PSPS就是解路径上的状态有序集。就是解路径上的状态有序集。(2)(2)新的路径状态表的新的路径状态表的 新的路径状态（新的路径状态（New Path StatesNew Path States，NPSNPS）表包含了等待搜索）表包含了等待搜索的状态，其后裔状态还未被搜索到，即未被生成扩展。的状态，其后裔状态还未被搜索到，即未被生成扩展。(3)(3)不可解状态表不可解状态表 不可解状态（不可解状态（No Solvable StatesNo Solvabl
6、e States，NSSNSS）表列出了找不到解）表列出了找不到解路径的状态路径的状态。如果如果在搜索中扩展出的状态是它的元素，则可立即将之排除，在搜索中扩展出的状态是它的元素，则可立即将之排除，不必沿该状态继续搜索。不必沿该状态继续搜索。5.3.15.3.1回溯回溯目标状态之一目标状态之一5.3.15.3.1回溯回溯5.3.15.3.1回溯回溯5.3.25.3.2广度优先搜索广度优先搜索5.3.35.3.3广度优先搜索广度优先搜索5.3.35.3.3广度优先搜索广度优先搜索5.3.35.3.3深度优先搜索深度优先搜索 深度优先搜索深度优先搜索（Depth-First SearchDepth-
7、First Search，DFSDFS）是尽可能快地深入树中，每）是尽可能快地深入树中，每当搜索方法可以做出选择时，它选择最左当搜索方法可以做出选择时，它选择最左(或最右或最右)的的分支的分支的次序次序A A、B B、D D、E E、C C、F F、G G访问节点来搜索状态，它类似树的先根遍历，是树的先根遍历的推广访问节点来搜索状态，它类似树的先根遍历，是树的先根遍历的推广。5.3.35.3.3深度优先搜索深度优先搜索5.45.4启发式启发式图搜索图搜索5.4.15.4.1启发式策略启发式策略 启发式（启发式（HeuristicHeuristic）策略就是利用与问题有关的启发信息引导搜索。在）
8、策略就是利用与问题有关的启发信息引导搜索。在状态空间搜索中，启发式被定义成一系列操作算子，并能从状态空间中选择状态空间搜索中，启发式被定义成一系列操作算子，并能从状态空间中选择最有希望到达问题解的路径最有希望到达问题解的路径。问题求解问题求解系统可在两种基本情况下运用启发式策略。系统可在两种基本情况下运用启发式策略。由于在问题陈述和数据获取方面存在模糊性，可能会使一个问题没有由于在问题陈述和数据获取方面存在模糊性，可能会使一个问题没有一个确定的解，这就要求系统能运用启发式策略做出最有可能的解释一个确定的解，这就要求系统能运用启发式策略做出最有可能的解释。虽然一个问题可能有确定解，但是其状态空间
9、特别大，搜索中生成扩虽然一个问题可能有确定解，但是其状态空间特别大，搜索中生成扩展的状态数会随着搜索的深度呈指数级增长展的状态数会随着搜索的深度呈指数级增长。5.4.15.4.1启发式策略启发式策略5.4.15.4.1启发式策略启发式策略5.4.25.4.2启发信息和估价函数启发信息和估价函数启发启发信息按运用的方法不同可分为三种。信息按运用的方法不同可分为三种。陈述性启发信息，一般被用于更准确、更精炼地描述状态，使问题的陈述性启发信息，一般被用于更准确、更精炼地描述状态，使问题的状态空间缩小，如待求问题的特定状况等属于此类信息。状态空间缩小，如待求问题的特定状况等属于此类信息。过程性启发信息
10、，一般被用于构造操作算子，使操作算子少而精，如过程性启发信息，一般被用于构造操作算子，使操作算子少而精，如一些规律性知识等属于此类信息。一些规律性知识等属于此类信息。控制性启发信息，它是表示控制策略方面的知识，包括协调整个问题控制性启发信息，它是表示控制策略方面的知识，包括协调整个问题求解过程中所使用的各种处理方法、搜索策略、控制结构等有关的知识。求解过程中所使用的各种处理方法、搜索策略、控制结构等有关的知识。5.4.25.4.2启发信息和估价函数启发信息和估价函数5.4.25.4.2启发信息和估价函数启发信息和估价函数5.4.3 A5.4.3 A搜索算法搜索算法5.4.3 A5.4.3 A搜
11、索算法搜索算法5.4.3 A5.4.3 A搜索算法搜索算法例例5.7 A5.7 A搜索算法求解搜索算法求解8 8拼图问题。拼图问题。8 8拼图问题是拼图问题是3 3拼图问题的扩展，在一个拼图问题的扩展，在一个3 33 3的方格盘上，放有的方格盘上，放有1818的数字，的数字，余下一格为空，空格移动规则同余下一格为空，空格移动规则同3 3拼图问题拼图问题。5.4.3 A5.4.3 A搜索算法搜索算法5.4.3 A5.4.3 A搜索算法搜索算法例例5.7 A5.7 A搜索算法求解搜索算法求解8 8拼图问题。拼图问题。5.4.4 A5.4.4 A*搜索算法搜索算法 A A*搜索算法是由著名的人工智能
12、学者搜索算法是由著名的人工智能学者 NilssonNilsson提出的，它是目前最有影提出的，它是目前最有影响的启发式图搜索算法，也称为最佳图搜索算法。响的启发式图搜索算法，也称为最佳图搜索算法。定义定义h h*()为为状态状态到目的状态的最优路径的代价，则当到目的状态的最优路径的代价，则当A A*搜索算法的搜索算法的启发函数启发函数h(n)h(n)小于等于小于等于h h*()，即满足，即满足 h(n h(n)h)h*()，对所有结点，对所有结点n n时，被称为时，被称为A A*搜索算法。搜索算法。5.4.4 A5.4.4 A*搜索算法搜索算法5.4.5 A5.4.5 A*搜索算法特性搜索算法特性5.4.5 A5.4.5 A*搜索算法特性搜索算法特性5.4.5 A5.4.5 A*搜索算法特性搜索算法特性5.55.5小结小结5.55.5小结小结
