根据模式进行多堆栈排序的算法

Question

在我(很少)的空闲时间里，我想出了一个小的个人项目作为练习使用新技术(对我来说!)的动力，例如 Python 3 和 Node JS。

我想尝试创建一个拼图的解决例程，类似于建筑中的汉诺塔，如下图所示:

拼图规则

1. 8 个彩色 block 随机放置在 3 个堆栈(S1-S3)上，容量分别为 5、3、3。
2. 大小为 3 的第四个堆栈 (S4) 是空的，但用作其他堆栈之间移动的临时存储；例如在 S2 中将蓝色移动到紫色旁边:移动红色 [S2 -> S4]、移动绿色 [S2 -> S4]、移动蓝色 [S3 -> S4]、移动蓝色 [S4 -> S2] 等
3. 随机生成 5 个 block 的目标模式， block 必须在堆栈之间一个接一个地移动(通过 S4)，直到 S1 中出现正确排序的 block ，此时 S4 必须再次为空(最终状态S2，S3 并不重要)。
4. 请注意，我的插图并不完美，随机场景实际上更具挑战性!但是，假设所有堆栈都在其底部访问，因此 S1 上的第一个可访问 block (左侧)是黑色 block ，等等。
5. 有一些解决方案的技巧最终可以编码到算法中，例如首先关注最后一个 block ，在本例中为紫色。

算法:

我一直在寻找基于模式的最合适的多堆栈“排序”算法，以避免重新发明轮子，但找不到任何看起来相关的东西，尽管我可能是找错地方了。Towers of Hanoi 经典递归似乎太基础了，而 Shunting Yard 和 Traveling Salesman 等算法(以及标准的 Bubblesort、Quicksort 等)看起来不太合适(如果我错了，请纠正我!)。

我的问题:

谁能建议或推荐一个合适的基本算法，我可以以此为基础构建或改编以解决这个难题？它可能需要递归才能找到正确的路径，但我确定这种类型的多堆栈或基于模式的排序已经在某处完成了吗？我最终想通过所需的最少步骤数获得最佳效率，但那是后来的事情。

正如我所提到的，我很可能最终会使用 Python 或 JS 来实现它，但在此阶段任何想法或片段都会受到赞赏 - 我希望稍后自己进行开发工作。

提前致谢!

艾伦

Answer 1

一种方法是先将 3 个未使用的 block 移动到 S4。设置分布，使其 S1 = 3 个 block ，S2 = 3 个 block ，S3 = 2 个 block 。如果 S3 有 1 或 2 个未使用的 block ，则需要 1 或 2 次移动才能将未使用的 block 移动到 S4。对 S2 重复，进行 1 到 3 次移动以移动 1 到 3 个未使用的 block 。未使用的 block 最后从 S1 中删除。

现在您有 5 个 block 和 3 个堆栈。假设 S1 有 3 个 block ，S2 有 2 个 block 。属于 S1 顶部的 block 可能需要最多的移动次数才能到达 S1 唯一的 block 所在的位置。例如，属于 S1 顶部的 block 位于 S2 的顶部。因此，将 2 个 block 从 S2 移动到(现在为空)S3，因此关键 block 位于 S3 的底部。然后将所有 3 个 block 从 S1 移动到 S2，然后将关键 block 移动到 S1。之后问题就变成了大小为4,3,3的4 block 3叠，应该不会太难。完成后，S4 中的 3 个 block 可以移动到 S2 或 S3。

对于 3 堆栈排序，多相归并排序最快，但所有 3 个堆栈的大小必须相同，因此此处不适用。