Question

7.11.骑士之旅

另一个经典问题，我们可以用来说明第二个通用图算法称为 “骑士之旅”。骑士之旅图是在一个棋盘上用一个棋子当骑士玩。图的目的是找到一系列的动作，让骑士访问板上的每格一次。一个这样的序列被称为“旅游”。骑士的旅游难题已经吸引了象棋玩家，数学家和计算机科学家多年。一个 $8 \times 8$8×8 棋盘的可能的游览次数的上限为 $1.305 \times 10^{35}$1.305×10​35​​ ;然而，还有更多可能的死胡同。显然，这是一个需要脑力，计算能力，或两者都需要的问题。

虽然研究人员已经研究了许多不同的算法来解决骑士的旅游问题，图搜索是最容易理解的程序之一。再次，我们将使用两个主要步骤解决问题：

• 表示骑士在棋盘上作为图的动作。
• 使用图算法来查找长度为 $rows \times columns-1$rows×columns−1 的路径，其中图上的每个顶点都被访问一次。