7.11.骑士之旅

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

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

  • 表示骑士在棋盘上作为图的动作。

  • 使用图算法来查找长度为 rows×columns-1 的路径,其中图上的每个顶点都被访问一次。

Last updated