7.11.骑士之旅 - Python 数据结构

返回介绍

7.11.骑士之旅

发布于 2019-08-07 字数 722 浏览 773 评论 0

7.11.骑士之旅

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

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

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

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

目前还没有任何评论,快来抢沙发吧!