A* 搜索未完成 [8 解谜器]

Question

我正在为我的编程任务创建一个 A* 搜索方法。我的问题是 A* 搜索方法应该找到成本最低的路径并始终找到目标状态。但是，我的代码并不能解决某些难题的问题。例如，对于拼图：

  *=====*
  ||103||
  ||426||
  ||758||
  *=====*

但是，对于

有更多瓷砖不合适的谜题，达到了所需的目标状态。例如，对于拼图：

  *=====*
  ||104||
  ||326||
  ||758||
  *=====*

将产生以下错误：

    Step: 3073
    *=====*
    ||016||
    ||342||
    ||758||
    *=====*
Exception in thread "main" java.lang.StackOverflowError
at sun.nio.cs.UTF_8$Encoder.encodeLoop(UTF_8.java:680)
at java.nio.charset.CharsetEncoder.encode(CharsetEncoder.java:579)
at sun.nio.cs.StreamEncoder.implWrite(StreamEncoder.java:271)
at sun.nio.cs.StreamEncoder.write(StreamEncoder.java:125)
at java.io.OutputStreamWriter.write(OutputStreamWriter.java:207)
at java.io.BufferedWriter.flushBuffer(BufferedWriter.java:129)
at java.io.PrintStream.write(PrintStream.java:526)
at java.io.PrintStream.print(PrintStream.java:669)
at java.io.PrintStream.println(PrintStream.java:806)

我的代码可以在这里找到：http://pastebin.com/rwq3cTAq

Answer 1

您忽略了解决方案中的可解决性问题。帖子中的第二个配置是无法解决的，并且您的 A* 算法进入无限递归，导致 StackOverflowError。

这个难题的可解性可以通过检查排列奇偶校验和 0 图块与其目标位置的距离来轻松确定。有关详细信息，请参阅此链接。