wangc

Nov 17, 2017

上一章提到知识系统的推理。推理过程不仅依赖于所用的推理方法，也依赖于推理的控制策略。推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略。由于智能系统的推理过程一般表现为一种搜索过程，因此，推理控制策略又可分为推理策略和搜索策略。这一章主要了解搜索策略（即搜索，后同）。

搜索概述

搜索是人工智能中的一个基本问题，它与推理密切相关，一个智能系统搜索策略的优劣，将直接影响到该系统的性能与推理效率。

搜索的含义

依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索。

人工智能所研究的对象大多是属于结构不良或非结构化的问题。对于这些问题，一般很难获得其全部信息，更没有现成的算法可供求解使用。因此，只能依靠经验，利用已有知识逐步搜索求解。
对那些结构性能较好，理论上有算法可依的问题，如果问题或算法的复杂性较髙（如按指数形式增长），由于受计算机在时间和空间上的限制，也无法付诸实用。这就是人们常说的组合爆炸问题。像这类问题，也需要采用搜索的方法来进行求解。

搜索可有多种不同的分类方法，例如可根据搜索过程是否使用启发式信息分为盲目搜索和启发式搜索，也可根据问题的表示方式分为状态空间搜索和与/或树搜索。

是人工智能中最基本的问题求解方法，它所采用的问题表示方法称为状态空间表示法。任何以状态和操作为基础的问题求解方法都可称为状态空间问题求解方法，简称状态空间法。其中，状态空间搜索是一种用状态空间法求解问题时的搜索方法。（详细…）

问题归约法是不同于状态空间方法的另外一种形式化方法，其基本思想是对问题进行分解或变换。当一个问题比较复杂时，如果直接进行求解，往往比较困难，此时可通过分解或变换，将它转化为一系列较简单的问题，然后通过对这些较简单问题的求解来实现对原问题的求解。（详细…）

尽管肓目搜索的性能不如启发式搜索，但由于启发式搜索需要抽取与问题本身有关的特征信息，而这种特征信息的抽取往往比较困难，因此盲目搜索仍不失为一种有用的搜索策略。这里主要讨论状态空间的盲目搜索策略和与或树的盲目搜索策略。

一般树的盲目搜索主要包括广度优先搜索算法和深度优先搜索算法两种。 (详细…)

在一般树搜索策略中，实际上都进行了一种假设，认为状态空间中各边的代价（权重）都相同，且都为一个单位量。从而，可用路径的长度来代替路径的代价。但是，对许多实际问题，这种假设是不现实的，它们的状态空间中的各个边的代价不可能完全相同。例如，城市交通问题，各城市之间的距离是不同的。

代价树的广度优先搜索也称为分枝界限法。它每次从Open表中选择节点或往Closed表中存放节点时，总是选择代价最小的节点。也就是说，Open表中的节点总是按照其代价从小到大排列的，代价小的节点排在前面，代价大的节点排在后面，与节点在树中的位置无关。代价树的广度优先搜索算法如下：

把初始节点S0放人Open表中，置S0的代价g(S0) = 0。
如果Open表为空，则问题无解，失败退出。
把Open表的第一个节点取出放入Closed表,并记该节点为n。
考察节点n是否为目标节点。若是，则找到了问题的解，成功退出。
若节点n不可扩展，则转第2步。
扩展节点n，生成其子节点ni（i=1,2, …），将这些子节点放人Open表中，并为每一个子节点设置指向父节点的指针。按如下公式:(ni) = g(n) + c(n, ni) (i=1, 2,… ) 计算各子节点的代价，并根据各节点的代价对Open表中的全部节点按照从小到大顺序重新进行排序。然后转第2步。代价树的广度优先搜索策略是完备的。如果问题有解，上述算法一定能够找到它，并且找到的一定是最优解。

代价树的深度优先搜索和代价树的广度优先搜索的步骤也基本相同，它们之间的主要区别在于，每次选择最小代价节点的方法不同。广度优先搜索每次都是从Open表的全体节点中选择一个代价最小的节点，而深度优先搜索则是从刚扩展的子节点中选择一个代价最小的节点。

代价树的深度优先搜索策略也是一种非完备的策略，某些本身有解的问题,按代价树的深度优先搜索可能找不到最优解，也可能根本找不到解。例如，当搜索进人无穷分支时，算法将无法找到解。对这一问题，同样可以通过增加深度限制的方法来解决。此处不再赘述。

发式搜索是一种能够利用搜索过程所得到的问题自身的一些特性信息来引导搜索过程尽快达到目标的搜索方法。由于它具有较强的针对性，因此，可以缩小搜索范围，提髙搜索效率。

启发式搜索方法所依据的是问题自身的启发性信息，而启发性信息又是通过估价函数作用到搜索过程中的。因此，在讨论启发式搜索方法之前，需要先给出启发性信息与估价函数的概念。

启发性信息：启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。启发性信息一般有以下三种：
- 有效地帮助确定扩展节点的信息；
- 有效地帮助决定哪些后继节点应被生成的信息；
- 能决定在扩展一个节点时哪些节点应从搜索树上删除的信息。一般来说，搜索过程所使用的启发性信息的启发能力越强，扩展的无用节点就越少。
估价函数：用来估计节点重要性的函数称为估价函数。估价函数f(n)被定义为从初始节点S。出发，约束经过节点n到达目标节点Sg的所有路径中最小路径代价的估计值。它的一般形式为f(n) = g(n)式中，g(n)是从初始节点S0到节点n的实际代价是从节点n到目标节点Sg的最优路径的估计代价。对g(n)的值，可以按指向父节点的指针，从节点n反向跟踪到初始节点S0，得到一条从初始节点S0到节点n的最小代价路径，然后把这条路径上所有有向边的代价相加，就得到g(n)的值。对h(n)的值，则需要根据问题自身的特性来确定，它体现的是问题自身的启发性信息，因此也称h(n)为启发函数。