0

我正在为类似于河内塔任务的任务寻找解决方案，但这与河内不同，因为磁盘不受大小限制。我正在创建的伦敦塔任务有 8 个磁盘，而不是传统的 3 个或 5 个（如维基百科链接所示）。我使用的PEBL软件“主要用 C++ 编程（尽管您不需要了解 C++ 即可使用 PEBL），但也使用 flex 和 bison（lex 和 yacc 的 GNU 版本）来处理解析。”

以下是该任务的实际效果视频：http ://www.youtube.com/watch?v=IiBJ94HRpeM&noredirect=1

*每个磁盘都是一个数字。例如，蓝盘=1，红盘=2，等等。

    1            \  
    2         ----\ 
    3         ----/     3     1
    4  5         /      2  4  5
=========              =========

左侧由您必须移动的磁盘组成，以匹配右侧。有3列。

因此，如果我用 8 个磁盘制作它，我会创建一个如下所示的试用版：

    1            \  
    2         ----\        7  8
 6  3  8      ----/     3  6  1
 7  4  5         /      2  4  5
=========              =========

我如何确定左侧看起来像右侧所需的最小移动量是多少？我不需要使用 PEBL 来编写代码，但我需要知道，因为我正在计算一个人每次试验的最低值有多接近。

4

1 回答 1

0

原理很简单，称为广度优先搜索：

每个状态都有一定数量的后续状态（由可能的移动定义）。

  1. 您从一组包含初始状态和步骤号 0 的状态开始。
  2. 如果结束状态在状态集中，则返回步数。
  3. 增加步数。
  4. 通过用每个后继状态替换当前状态来重建状态集。
  5. 前往 2

因此，在每个步骤中，计算您当前可用状态的后续状态，并查看您是否达到了目标状态。

但是，请注意，这可能需要一段时间并占用大量内存！在我们的案例中，您可以进行一些优化，因为您可以省略前任状态。不过，在大多数州，您将有 5 种可能的移动方式。这意味着您将在 N 步后考虑 5^N 个状态。

例如，如果我没有出错，您的第二个示例将需要 10 步。这将为您提供大约 1000 万个州。大多数当代计算机将无法搜索深度 15 以上。

我认为找到解决方案的算法会简单快捷，但我们没有证据证明这个解决方案是最短的。

于 2013-07-16T17:51:32.550 回答