Question

7.14.骑士之旅分析

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

Figure 12-13

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

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

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

def orderByAvail(n):
    resList = []
    for v in n.getConnections():
        if v.getColor() == 'white':
            c = 0
            for w in v.getConnections():
                if w.getColor() == 'white':
                    c = c + 1
            resList.append((c,v))
    resList.sort(key=lambda x: x[0])
    return [y[1] for y in resList]
Next Section - 7.15. General Depth First Search