本质上所有的人工智能程序都使用某种形式的搜索来找到想要的结果。事实上，人工智能的一个领域专门研究不同的搜索算法。抽象地看，所有的搜索算法都是在探索一个具有不同的可能状态的空间，以找到一些能够满足搜索目标的状态。举例来说，在一个下国际象棋的程序中，一个状态就表示下棋过程中的第一个棋盘局面。而目标就是要找到一个状态，使得下棋程序能够将对手将死。要搜索一个赢的状态，程序要使用一种转换函数，根据输入的一个状态生成另一个状态。在下棋的程序中，这个转换函数可以定义为棋子的移动。给定一个状态，程序根据一个可能的移动计算出一个新的状态。典型地，程序需要根据所有可能的移动来考虑产生的状态集合。这些状态被称为后继状态。

国际象棋是一种非常复杂的游戏，会产生相当复杂的搜索空间。这里，我们先讨论一个非常简单的例子。假设你想找到一个朋友的密码锁的数字组合。你可以随机地尝试各种组合并且希望有好运气，但是如果你想要系统地考虑所有的可能，则应该决定一种专门的搜索策略。我们可以按照下面的方式将这个问题形式化为一个状态空间搜索问题。这里，“状态”表示你已经处理过的数字的一个列表。当你拨另一个数字时，就完成了一次“移动”，并产生了一个新的状态，表现为在原来的状态尾部加入这个新的数字。假设我们并不知道需要拨多少数字。为了使这个例子保持在可控制的范围内，我们还假设密码锁只有两个数字1和2。图B.1给出了涉及最多3个数字的状态空间。从初始状态()开始，我们拨数字1或者2，这样就有了两个后继状态(1)和(2)，如图所示。从这两个状态开始，我们可以拨第二个数字，这样每个状态又有两个后继状态，这样一直继续下去。很多搜索策略的研究都可以在一个一般性的框架下进行，这个框架需要维护一个还需要尝试的状态列表。假设TODO就是一个你需要考虑的状态列表。

图B.1简单密码锁的搜索空间

1. 将TODO初始化为仅包含初始状态的(())的列表；

2. 重复下面的操作直至找到目标状态：

   2.1 从TODO中移出一个状态；

   2.2 检查它是否是目标状态（是否能开锁?）；

   2.3 如果不能，生成所有后继状态，并将其加入到TODO列表中。

根据选择下一个要处理的状态的策略的不同，产生了不同的搜索策略。有两种基本的策略。第一种是深度优先策略，使用一个栈作为TODO列表。这样，它总是选择最后一个加到栈中的状态做进一步的处理。考虑在密码锁问题的处理中采用这种策略，假设实际的组合是（211)。一开始，TOD0中只有初始状态()。两个后继状态被加入到列表中，也就是(1)和(2)。加入这两个状态后，TOD0值为((1)(2))。下一步选择状态(1)。发现它不是目标状态（也就是说，它不能开锁），因此两个后继状态，(11)和(12)，产生并加到了TOD0列表中，这时TOD0列表变成了((11)(12)(2))。下面选择状态(11)，发现锁依然无法打开后，两个后继状态(111)和(112)产生出来，并被加入到TOD0列表中，这时TOD0列表变成了((111)(112)(12)(2))。知道(111)不是密码后，后继状态(1111)和(1112)被加入到TOD0列表中。现在你也许注意到了，除非给这个算法规定一个需要产生的数字位数的上限，否则这个策略永远不会找到答案。

另外一种基本的策略称为广度优先搜索，将TOD0当做队列而不是栈。这样，后继状态被添加到TOD0列表的末尾。还是从状态()开始，TOD0列表在算法运行过程中依次取下面这些值：

((1)(2)）

((2)(1 1)(1 2))

((1 1)(1 2)(21)(2 2))

((12)(2 1)(22)(11 1)(1 12))

((21)(22)(111)(112)(121)(122))

等等

可以看到这两种策略以很不一样的顺序探索这个空间。如果在图B.1所示的表示这个搜索空间的树中依据这两种策略来跟踪搜索到的状态，会看到深度优先策略在这棵树上快速向下移动，不断地在更深的层次上探索状态。另一方面，广度优先策略总是系统地探索树的某一个层次上所有可能的状态，然后才考虑下一个层次的状态。

对于有限的搜索空间[举例来说，我们可以指定密码最多只有4位，因此类似(1111)的状态就没有后继状态]，通常深度优先策略会更快地找到答案。不过，对于无限的搜索空间，就像对于不限长度的密码锁问题一样，深度优先策略不能保证会找到答案，因为它可能会沿着一条具有无限后继状态但又不包含答案的链搜索下去。广度优先策略可以保证如果存在一个答案就一定能够找到。

很多其他搜索策略也是可能的。一种称为迭代深化的策略类似于深度优先策略，不过它在到达一个特定的深度后就会停下来。如果在特定的深度上没有找到答案，它就增加深度并重复上述操作。虽然这会导致重复劳动，不过人们发现它总体上要好于纯粹的深度优先或广度优先策略。作为选择，你也可以使用启发式搜索，这种策略采用某种启发式信息来选择下一个状态。举例来说，如果你认为不包含相同数字反复出现的序列更有可能是密码，你也许总是尽可能选择一个不包含重复数字的状态，只有在不存在这种状态时才考虑其他的可能性。你可能将包含重复数字的状态加入到TOD0列表的末尾，而将其他状态加入到前面。

((1)（2))

((1 2)(2)(1 1))

((121)(2)(11)(122))

等等

启发式搜索的一种一般化的形式描述称为最佳优先搜索。这种策略使用一个函数，为每一个状态返回一个启发式的值。在搜索的每一步，你都选择值最高的状态。

责任编辑：admin