解迷算法在出口点移动一块
我正在寻找一些建议，关于什么是好的算法，我可以用Javascript解决附加图像上的谜题，最好是如果algo是文档化的，并且可以包含一个JS示例。
白色碎片可以一次移动一个，4个方向，进入灰色点(如果他们适合)游戏结束时，较大的白色块到达红色出口点。
，这只是为了好玩。
我在Javascript中做了这个，我将使用p5.js来显示它。我不是在寻找真正的代码解决方案，这是一个个人的练习乐趣。
我在过去尝试过，但它没有起作用，我记得它花了很多时间计算出口路径，但几分钟后就找不到了。
所显示的拼图是一个非常基本的版本，以掌握想法，但董事会将变得越来越复杂，例如，有许多不同大小的白片在更大的板子。
我知道我可以尝试breadth-first-search algo，但是我不知道如果董事会变大，比如5x7而不是3x3，我不知道它是否仍然适合，我不知道如何估计计算机可以找到最短的出口路径的排列数。
对于BFS，我理解，从董事会的特定状态来看，我需要探索所有可能的结果，每一个分支都是不同的分支，这可能导致数百万的组合，每一个组合都会探索如果一个给定的分支被移到这里而不是那里会发生什么。
，
- ，我会随机选择下一个要移动的部分吗？也许不是，这可能更难调试，因为它不断变化。也许我会选择第一个可以移动的部分，从左上角开始。
- 如何防止回归？例如，在不同的分支(
)中发现了一块已经被探索过的板。
谢谢你的时间和耐心:)
回答 1
Stack Overflow用户
发布于 2020-10-06 16:10:23
根据http://groups.csail.mit.edu/mac/users/bob/sliding-blocks.pdf的说法，滑动谜题在NP-完全问题的世界中常常是有空间的，这些问题通常是粗糙且计算昂贵的(如果可以解决的话)。这就解释了为什么你很难计算出路径。
通常没有通用的方法来解决这些问题，因为每个问题都需要一个特定的定制解决方案。
不过，在你的具体情况下，我建议尝试一种简单的路径查找方法，首先你要尽可能接近这个部分，然后，一个动作被移出，你试着把碎片从潜在的路径中“推开”。
我希望这能为你指明正确的方向：
https://stackoverflow.com/questions/64228477
复制相似问题
腾讯云开发者
