问题标签 [sliding-tile-puzzle]

我需要知道是否有任何算法可以预先知道，而无需搜索初始集合的所有可能解决方案，如果我们可以达到第二个给定集合。

例如：

[1,0,2,3,5,6,4,8,7] -> [2,3,4,5,8,0,7,1,6]

如果从第一个集合可以到达第二个集合，则该算法将返回 True ，否则返回False 。

我想了一下，我可以肯定地说，如果初始集合是可解的（可以将所有正方形按顺序排列），第二个也是如此，那么这个算法将返回 True，因为：

[1,2,3,4,5,6,7,0,8] <-> [1,2,3,4,5,6,7,8,0] <-> [1,2,3 ,4,5,0,7,8,6]

对于任何给定的可解谜题，可以将其反转以获得原始集合。

另一方面，如果一个集合是可解的，而第二个是不可解的，那么算法肯定会返回 False，因为如果你可以从不可解集开始达到可解集，那么我们就会产生矛盾。

现在，真正的问题是当两个集合都无法解决时。出于某种原因，我很肯定给定一个不可解的集合，有可能达到任何其他不可解的集合配置，因为当集合是可解的时候就会发生这种情况。但我找不到证据或任何文件！有人可以启发我吗？

我编写了一个算法来使用广度优先搜索来解决N-puzzle问题。为了让事情变得更快，我决定预先分配一个大数组，而不是重复地将值推送和移动到一个空数组。

偶然我注意到一个奇怪的行为，即两次分配大数组实际上使挂钟时间更快。我用完整的代码创建了一个要点，但是给我奇怪行为的部分在这里：

在我的机器上，使用 node.js 初始化两次值的典型运行时间约为 550 毫秒。当我注释掉我实例化值的地方之一时，我只实例化它一次，运行时间增加到大约 650 毫秒 - 700 毫秒。在我看来，当只分配一次数组时，运行时间应该会减少。我制作了一个视频来解释我在做什么，并在此处显示我的机器上的运行时间。

奇怪的是，当我在repl.it上运行它时，无论是否被注释掉，运行时都差不多，这让我觉得它与 v8 引擎有关。

谁能给我一个解释，为什么在做应该少做的工作时挂钟时间会增加？

您好我正在使用 java 创建一个 Solver 程序，该程序使用 HeapMinPQ 和节点的帮助来解决基于“8 拼图”格式的任何板。我已经通过“Board”数据类型创建了该数据类型，它使用二维数组来计算图块（“0”是空白区域）。在我的 SearchNodes 中，我有一个优先整数，它解释了“曼哈顿”值（我确信该方法可以正常工作）。问题是我一直在努力取得进展，虽然我的程序可以编译，但它只是卡在运行而没有给出适当的输出（所需的最少移动次数）。我想我很难理解所有这些，但这是我到目前为止要解决的代码......

这是我来自“板”数据类型的“双胞胎”方法。

我在这里肯定有一个严重的错误计算，我很确定它从 solve(heap, twinHeap); 开始。公共 Solver(Board initial) 方法中的方法。任何帮助将不胜感激。

我正在尝试在 PHP 中使用广度优先搜索来解决 8 个难题，但我不断收到错误消息。我试图找出在我的代码中显示 T_Variable 的错误的语法错误，但我没有看到。

解析错误：语法错误，第 9 行 C:\xampp\htdocs\8BFS.php 中的意外 '$this' (T_VARIABLE)

我的代码是

我只停留在开始，我找不到那个错误不断出现。它曾经是意外的''错误，在我删除了所有多余的空格后，现在它显示了意外的'$this'。

这里的语法错误可能是什么，我让我的朋友运行相同的程序，她说它运行得很好，她说她安装了相同的 php 版本，我安装了这个：

最终我用一张桌子制作了一个滑块拼图，但目前我正在生成一个新的拼图并打乱瓷砖，但我的代码中的某些东西似乎使这项工作不正确。（并非所有表格单元格都已填充，等等。）知道是什么原因造成的吗？

在我正在编写的程序中，我正在使用 body onload 来构建拼图，但由于某种原因在 Fiddle 中不起作用：

小提琴示例

我尝试在解决 8 益智游戏的尝试中实施广度优先搜索算法。但在某些情况下，我的内存不足，但在更简单的情况下，它可以毫无问题地解决。

如何改进我的算法来修复它？

主程序

游戏.c

我正在尝试对 Lisp 中的拼图“8-puzzle”实施启发式搜索策略 A*。

要运行我的搜索，我使用以下命令： (run-best '(0 1 2 3 4 5 6 B 7) '(0 1 2 3 4 5 6 7 B))

其中第一个状态是开始目标，第二个是最终目标。

但是，我的程序运行了很长时间。最终，我认为它会stack-overflow。*编辑：它并没有耗尽内存，但是它花了 30 分钟，比我的广度优先搜索要长得多。

搜索算法代码：

8puzzle 的启发式函数：

我用 Python 开发了自己的程序来解决 8 个谜题。最初，我使用“盲目”或不知情的搜索（基本上是暴力破解）生成和探索所有可能的继任者，并使用广度优先搜索。当它找到“目标”状态时，它基本上会回到初始状态并提供（我相信）是解决它的最优化步骤。当然，在某些初始状态下，搜索会花费大量时间并在找到目标之前生成超过 100,000 个状态。

然后我添加了启发式 - 曼哈顿距离。解决方案开始呈指数级增长，并且探索的状态要少得多。但我的困惑是，在某些时候，生成的优化序列比使用盲目或不知情的搜索所达到的要长。

我正在做的基本上是这样的：

1. 对于每个状态，查找所有可能的移动（上、下、左和右），并生成后续状态。
2. 检查状态是否重复。如果是，则忽略它。
3. 计算该州的曼哈顿。
4. 挑选出曼哈顿最低的继任者并添加到列表的末尾。
5. 检查目标状态。如果是，则打破循环。

我不确定这是否符合贪婪优先或 A* 的条件。

我的问题是，这是曼哈顿距离启发式的固有缺陷，有时它不会给出最佳解决方案，或者我做错了什么。

下面是代码。我很抱歉这不是一个非常干净的代码，但主要是顺序的，应该很容易理解。我也为长代码道歉 - 我知道我需要优化它。也将不胜感激任何清理代码的建议/指导。这是什么：

如果您想检查，这里有一些初始状态和计算的优化步骤（上面的代码将提供此选项以在盲搜索与知情搜索之间进行选择）

初始状态
- 283164507 盲人：19 曼哈顿：21
- 243780615 盲人：15 曼哈顿：21
- 102468735 盲人：11 曼哈顿：17
- 481520763 盲人：13 曼哈顿：23
- 723156480 盲人：16 曼哈顿：20

我特意选择了结果很快（几秒钟或几分钟内）的例子。

您的帮助和指导将不胜感激。

编辑：我做了一些快速更改并设法减少了大约 30 多行。不幸的是，此时不能做太多事情。
注意：我已经硬编码了初始状态和盲目与知情选择。请更改初始状态的变量“string”的值和 Informed/Blind 的变量“inf”[I/B] 的值。谢谢！

我对此很陌生，所以我会这样称呼 [element1,element2,element3]

我有一个如上所示的数组，我想找到这个数组的解决方案。它应满足以下条件：

第一个元素0：

它应该至少有一个解决方案[0,1,11],[0,2,11],[0,3,10],[0,4,10],[0,5,9],[0,6,9]

第一个元素1：

这个 ：[1,7,9],[1,5,11],[1,6,11]

第一个元素2：

和这个 ：[2,7,11],[2,8,10]

这样第二个元素和第三个元素对于每个解决方案都是唯一的（其中第一个元素=0，第二个元素=1，第三个元素=2）

o/p 可以是 : [0,1,11]和[1,7,9]和[2,8,10]

错误输出： [0,1,11], [1,6,11] ,[2,8,10] 这里第一个和第二个的参数 3 相同。

我正在尝试编写算法来解决爬山的随机 8 谜题。我已经使用首选、最佳选择和随机重启来编写它，但它们总是陷入无限循环。有什么方法可以防止这种情况发生吗？同样在生成随机谜题时，我使用了一种算法来确保生成的所有谜题都是可解决的。所以在可解性问题上没有问题。这是随机重启类型的功能，它应该解决几乎 100% 的谜题的 8 个谜题：