《算法技术手册》分析

算法的性能取决问题的共性和特性。一般来说，开放集和闭合集的核心操作会出乎意料地降低算法的性能，因为在集合中寻找元素的朴素实现将会需要O(n)的时间。核心操作包括：

open.remove

从开放集中删除状态。

closed.insert(INode state)

向闭合集中添加状态。

closed.contains(INode state)

查询是否给定的状态在闭合集中。

open.insert(INode state)

向开放集中添加状态，以供稍后访问。

因为深度优先搜索使用了栈来存储开放集，因此添加和删除操作只需要常数时间。但是，如果闭合集是一个简单链表，那么closed.contains(INode)的时间花费将会是O(n)，n是闭合集中状态的数目。这个高昂的开销可以通过使用树或者散列结构来避免，在两种结构中，都需要用到键值（实现INode接口的棋面状态类提供）。

问题的特性在如下方面能够影响性能：（a）一个棋面状态的后继状态数目，以及（b）可行走法的顺序。有些问题中，一个棋面状态下有着大量的可行走法，也就是说，深度优先地选择很多的路径将会是不明智的。同样的，走法的排序也会影响整个搜索过程。如果可以使用某些启发式信息，那么我们将看起来可能能够得到解的走法排在表的前面。我们也可以利用对称性来改进搜索。无论棋盘如何旋转，计算出来的棋面状态键值都是相等的，现在，我们不可能改进开放集的结构，因为深度优先搜索的确需要一个栈结构，但是，我们可以从闭合集入手，减少空间消耗。

我们使用三个例子来讨论一下深度优先搜索的性能，我们可以看到仅仅是状态的些许不同，搜索却差异甚大。在每个例子中，至多需要走10步才能找到解，表7-1列出了使用可变深度限制的深度优先搜索性能。偶尔深度优先搜索能够很快地找到解，见表7-2，使用固定深度8，算法从棋面状态N1开始，在搜索25个棋面状态之后，找到了一个需要走8步的解（比我们预想的要好两步）。图7-7表示的是随着搜索深度的增长，深度优先搜索的搜索树规模变化情况。一般来说，搜索树的规模是分支因子b的指数级。对于八数码问题来说，根据空格的位置，分支因子在1.6～3.81之间变化（Reinefeld，1993）。三个近似函数表示的是给定搜索深度d，从三个初始位置开始，搜索树的规模。

程序员想知道图7-7的搜索树这样的规模下，解的质量如何。我们可以得到如下两个结论：

一个不恰当的搜索深度得不到解

考虑初始状态N2，搜索深度为25，在搜索20 441个棋面状态之后，我们仍然没有得到解。这怎么可能？因为深度优先搜索不会重复访问棋面状态。搜索可是能够在第3451个棋面状态时就能够找到解。

上图是在深度为25时得到的棋面状态，这个棋面状态只有3步就能够得到解。由于这个棋面状态已经访问过，搜索树不会再继续扩展，所以这个状态会被加到闭合集中。并且搜索深度已经达到了深度限制，所以不会从这个状态开始继续搜索，即使之后深度优先搜索在较早的等级访问到这个状态，它也不会继续搜索，因为这个状态已经在闭合集中。

随着深度的增加，解的质量可能会越来越不尽如人意

随着深度的增加，我们可以看到有时得到的解的规模是如何数倍于期望规模的。

很有意思的是，给定初始状态N1，一个没有限制的深度优先搜索将会在访问30个棋面状态之后找到一个30步的解，这时开放集中仍然有23个棋面状态。但是，这种好事可不会一直发生，我们可以从初始状态N2和N3得到的解中可以看出。