有最后关于骑士之旅一个有趣的话题，然后我们将继续到深度优先搜索的通用版本。主题是性能。特别是，`knightTour` 对于你选择下一个要访问的顶点的方法非常敏感。例如，在一个5乘5的板上，你可以在快速计算机上处理路径花费大约1.5秒。但是如果你尝试一个 8×8 的板，会发生什么？在这种情况下，根据计算机的速度，你可能需要等待半小时才能获得结果！这样做的原因是我们到目前为止所实现的骑士之旅问题是大小为 O(k^N ) 的指数算法，其中 N 是棋盘上的方格数，k 是小常数。Figure 12 可以帮助我们搞清楚为什么会这样。树的根表示搜索的起点。从那里，算法生成并检查骑士可以做出的每个可能的移动。正如我们之前注意到的，可能的移动次数取决于骑士在板上的位置。在角落只有两个合法的动作，在角落邻近的正方形有三个，在板的中间有八个。Figure 13 展示了板上每个位置可能的移动次数。在树的下一级，再次有 2 到 8 个可能的下一个移动。要检查的可能位置的数量对应于搜索树中的节点的数量。


*Figure 12-13*

我们已经看到，高度 N 的二叉树中的节点数量是 2^N+1 - 1。对于具有可以具有多达八个孩子而不是两个节点的树，节点的数量要大得多。因为每个节点的分支因子是可变的，我们可以使用平均分支因子估计节点的数量。重要的是要注意，这个算法是指数：k^N+1 - 1，其中 k 是板的平均分支因子。让我们看看这增长有多快！对于 5×5 的板，树将是 25 级深，或者 N = 24，将第一级算为级 0。平均分支因子是 k = 3.8 因此，搜索树中的节点数量是 3.8^25 - 1 或3.12×10^14 。对于 6x6 板，k = 4.4，有 1.5×10^23 个节点，对于常规的 8x8 棋盘，k = 5.25 ，有 1.3×10^46 。当然，由于问题有多个解决方案，我们不必去探索每个节点，但是我们必须探索的节点的小数部分只是一个不会改变问题的指数性质的常数乘数。我们将把它作为一个练习，看看你是否可以表示k 作为板的大小的函数。

幸运的是有一种方法来加速八乘八的情况，使其在一秒钟内运行完成。在下面的列表中，我们将展示加速 `knightTour` 的代码。这个函数（见Listing 4），被称为 `orderbyAvail` 将被用来代替上面代码中对 `u.getConnections` 的调用。`orderByAvail` 函数中的关键是第 10 行。此行确保我们选择具有最少可用移动的下一个顶点。你可能认为这具有相反效果; 为什么不选择具有最多可用移动的节点？你可以通过运行该程序并在排序后插入行`resList.reverse()` 来尝试该方法。

使用具有最多可用移动的顶点作为路径上的下一个顶点的问题是，它倾向于让骑士在游览中早访问中间的方格。当这种情况发生时，骑士很容易陷入板的一侧，在那里它不能到达在板的另一侧的未访问的方格。另一方面，访问具有最少可用移动的方块首先推动骑士访问围绕板的边缘的方块。这确保了骑士能够尽早地访问难以到达的角落，并且只有在必要时才使用中间的方块跳过棋盘。利用这种知识加速算法被称为启发式。人类每天都使用启发式来帮助做出决策，启发式搜索通常用于人工智能领域。这个特定的启发式称为 `Warnsdorff` 算法，由 `H. C. Warnsdorff` 命名，他在 1823 年发表了他的算法。

给定图 G 和起始顶点 s，广度优先搜索通过探索图中的边以找到 G 中的所有顶点，其中存在从 s 开始的路径。通过广度优先搜索，它找到和 s 相距 k 的所有顶点，然后找到距离为 k + 1 的所有顶点。可视化广度优先搜索算法一个好方法是想象它正在建一棵树，一次建一层。广度优先搜索先从其他起始顶点开始添加它的所有子节点，然后再添加其子节点的子节点。

为了跟踪进度，BFS 将每个顶点着色为白色，灰色或黑色。当它们被构造时，所有顶点被初始化为白色。白色顶点是未发现的顶点。当一个顶点最初被发现时它变成灰色的，当 BFS 完全探索完一个顶点时，它被着色为黑色。这意味着一旦顶点变黑色，就没有与它相邻的白色顶点。另一方面，灰色节点可能有与其相邻的一些白色顶点，表示仍有额外的顶点要探索。

下面 Listing 2 中所示的广度优先搜索算法使用我们先前开发的邻接表表示。此外，它使用一个 Queue，一个关键的地方，决定下一个探索的顶点。

此外，BFS 算法使用 Vertex 类的扩展版本。这个新的顶点类添加了三个新的实例变量：`distance`，`predecessor`和 `color` 。这些实例变量中的每一个还具有适当的 `getter` 和 `setter` 方法。这个扩展的顶点类代码包含在`pythonds`包中，但我们不会在这里展示它，因为没有新的需要学习的点。

BFS 从起始顶点开始，颜色从灰色开始，表明它正在被探索。另外两个值，即距离和前导，对于起始顶点分别初始化为 0 和 None 。最后，放到一个队列中。下一步是开始系统地检查队列前面的顶点。我们通过迭代它的邻接表来探索队列前面的每个新节点。当检查邻接表上的每个节点时，检查其颜色。如果它是白色的，顶点是未开发的，有四件事情发生：

1. 新的，未开发的顶点 nbr，被着色为灰色。

2. nbr 的前导被设置为当前节点 `currentVert`

3. 到 nbr 的距离设置为到 `currentVert + 1` 的距离

4. nbr 被添加到队列的末尾。 将 nbr 添加到队列的末尾有效地调度此节点以进行进一步探索，但不是直到 `currentVert` 的邻接表上的所有其他顶点都被探索。

``` python

from pythonds.graphs import Graph, Vertex

from pythonds.basic import Queue

def bfs(g,start):

start.setDistance(0)

start.setPred(None)

vertQueue = Queue()

vertQueue.enqueue(start)

while (vertQueue.size() > 0):

currentVert = vertQueue.dequeue()

for nbr in currentVert.getConnections():

if (nbr.getColor() == 'white'):

nbr.setColor('gray')

nbr.setDistance(currentVert.getDistance() + 1)

nbr.setPred(currentVert)

vertQueue.enqueue(nbr)

currentVert.setColor('black')

*Listing 2*

让我们看看 bfs 函数如何构造对应于 Figure 1 中的图的广度优先树。开始我们取所有与 `fool` 相邻的节点，并将它们添加到树中。 相邻节点包括 `pool`, `foil`, `foul`, `cool`。 这些节点被添加到新节点的队列以进行扩展。 Figure 3 展示了在此步骤之后树以及队列的状态。


*Figure 3*

在下一步骤中，bfs 从队列的前面删除下一个节点（`pool`），并对其所有相邻节点重复该过程。 然而，当 bfs 检查节点 `cool` 时，它发现 `cool` 的颜色已经改变为灰色。这表明有一条较短的路径到 `cool`，并且 `cool` 已经在队列上进一步扩展。在检查 `pool` 期间添加到队列的唯一新节点是 `poll`。 树和队列的新状态如 Figure 4所示。


*Figure 4*

队列上的下一个顶点是 `foil`。 `foil` 可以添加到树中的唯一新节点是 `fail`。 当 bfs 继续处理队列时，接下来的两个节点都不向队列或树添加新内容。 Figure 5 展示了在树的第二级上展开所有顶点之后的树和队列。


*Figure 5*

*Figure 6*

你应该自己继续完成算法，以便能够熟练使用它。Figure 6 展示了在 Figure 3 中的所有顶点都被扩展之后的最终广度优先搜索树。关于广度优先搜索解决方案的令人惊讶的事情是，我们不仅解决了我们开始的 `FOOL-SAGE` 问题，还解决了许多其他问题。 我们可以从广度优先搜索树中的任何顶点开始，并沿着前导箭头回到根，找到从任何字回到 `fool` 的最短的词梯。 下面的函数（Listing 3）展示了如何按前导链接打印出字梯。

``` python

def traverse(y):

x = y

while (x.getPred()):

print(x.getId())

x = x.getPred()

print(x.getId())

traverse(g.getVertex('sage'))

*Listing 3*

* [7.10.广度优先搜索分析](7.图和图的算法/7.10.广度优先搜索分析/README.md)

* [7.11.骑士之旅](7.图和图的算法/7.11.骑士之旅/README.md)

* [7.12.构建骑士之旅图](7.图和图的算法/7.12.构建骑士之旅图/README.md)

* [7.13.实现骑士之旅](7.图和图的算法/7.13.实现骑士之旅/README.md)

* [7.14.骑士之旅分析](7.图和图的算法/7.14.骑士之旅分析/README.md)