3

这15 Puzzle是涉及启发式算法建模的经典问题。该问题常用的启发式方法包括计算错放瓷砖的数量，并找出每个块之间的曼哈顿距离之和及其在目标配置中的位置。请注意，两者都是可接受的，即它们永远不会高估剩余的移动次数，这确保了某些搜索算法（例如 A*）的最优性。

  • 你认为什么Heuristic是合适的，A*似乎工作得很好，你有一个例子，也许在cor java？
4

2 回答 2

8

启发式

我选择的启发式方法是找出排列中所有反转的总和是奇数还是偶数 - 如果是偶数，那么 15Puzzle 是可解的。

一个排列中的反转次数等于它的逆排列的次数（Skiena 1990, p. 29; Knuth 1998）。

只有当我知道它可以解决时，解决它才有意义。然后的任务是减少逆和 - viola 问题解决了。找到一个解决方案应该不超过 80 步。

更多帮助

置换方程为：

在此处输入图像描述

0 到 16 范围内的阶乘为 {1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 130206743688002,088002 如果您需要更多，请在WolframAlpha中搜索Range[1,20]！

如果您想了解更多信息，请阅读：15Puzzle。

于 2011-03-20T10:18:37.227 回答
1

使用 A* 算法在 C++ 中实现十五个谜题https://gist.github.com/sunloverz/7338003

于 2013-11-07T13:02:30.170 回答