时间戳

首页 > 解决方案 > 计算船上所有部件离开所需步数的算法

algorithm - 计算船上所有部件离开所需步数的算法

问题描述

我有个问题：

在 6x6 板上，您最多收到 6 件。
一块由它的位置定义，以及它在不改变方向的情况下移动的方向（方向：上、下、左、右）。
每次迭代都可以移动任意数量的棋子，但在迭代结束时只有一个棋子可以占据一个方格。如果两块朝相反的方向前进，它们一旦接触就可以相互通过（它们交换位置）。如果一块最终在一个正方形上，一块将在同一次迭代中离开它也是允许的。在多少次迭代（最短时间）内，所有棋子都会在棋盘之外。

我试过这样做：

  1. 接收每件作品的位置
  2. 将可用于第一个列表中的每个移动的每个可能移动创建到新移动列表中，即移动一个棋子，...，移动所有棋子
  3. 删除旧动作，因为它们不会重复。
  4. 检查创建的每个移动是否可以完成并将其添加回移动池。
  5. 从第 2 步开始重复。

这个解决方案的问题是它非常耗时，因此它不起作用。我目前不知道如何解决这个问题。

标签： algorithm

解决方案

第二步将检查每次迭代的 2 6个移动组合（如果棋盘上有 6 个棋子），即对每一个棋子是否会移动做出是/否决定。

通常这些组合中的许多都是无效的，因为它们会让两个棋子占据同一个方格。此外，某些组合不会移动棋子，而该棋子实际上不会妨碍任何其他棋子，因此不移动它没有任何好处。将这样的星座放在你的列表中会减慢这个过程而没有任何好处。

如果它能够识别一些模式，该算法将得到改进：

  1. 如果一些棋子被定位在一个循环中，即它们都移动到循环中“下一个”棋子的位置，那么它们都应该立即移动。

    例子：

    ┌───┬───┐
│ → | ← |
└───┴───┘

    或者：

    ┌───┬───┬───┐
│ ↓ | ← | ← |
├───┼───┼───┤
│ → | → | ↑ |
└───┴───┴───┘

    试图只移动这些移动的一个子集是没有用的：只有在同一迭代中移动它们才是有效的。此外，由于它们不占用之前空闲的方格（并且可能阻碍另一方格），因此绝对没有理由延迟该组合移动。因此，如果检测到这种模式，所有相关的部分都应该移动。

  2. 如果一个棋子会移动到当前没有其他棋子或不能移动到的格子上，则没有理由不移动。它应该被制作。

  3. 当一个棋子可以移动到其他棋子也可以移动到的方格时，考虑这些可能性中的每一种都是值得的，即考虑其中一个棋子移动到该方格而其他棋子移动到该方格的迭代替代方案不要动。

  4. 对于第 3 步的每个备选方案（每个都与规则 1 和 2 的移动相结合），规则 2 应再次应用于那些只能根据步骤 3 中做出的决定移动的棋子。

使用这些“规则”，您可以极大地限制您必须调查的状态数量，即您的列表的大小将受到更多限制。唯一进入替代路径的分支发生在规则 3 中。

当然，实现这一点需要付出一些努力。

其他优化

尽管它不会提高时间复杂度，但您可以通过使用高效的数据结构来获得执行时间的一个因素。

不要使用 x、y 坐标，而是使用一维位置标识，例如映射到 6x6 板的标识，如下所示：

 0  1  2  3  4  5
 8  9 10 11 12 13
16 17 18 19 20 21
24 25 26 27 28 29
32 33 34 35 36 37
40 41 42 43 44 45

并且，与此一致，不要存储方向的字母，而是存储参考上述编号系统的相对位置变化：

Left = -1
Right = +1
Up = -8
Down = +8

因此，对于一件作品，您将有两个数字属性：一个数字表示其位置，另一个数字表示其方向。

当结果位置不在上面列出的任何数字中时，移动就会脱离棋盘。请注意，编号在行之间有间隙，因此也很容易检测到水平溢出。

此外，使用由一个数字而不是一对坐标组成的位置，可以更容易和更快地测试两个棋子是否占据相同的位置。

推荐阅读