15 谜题启发式
15 Puzzle 是涉及启发式的建模算法的经典问题。此问题常用的启发式方法包括计算错位图块的数量以及计算每个块与其在目标配置中的位置之间的曼哈顿距离之和。请注意，两者都是可接受的，即它们永远不会高估剩余的移动次数，这确保了某些搜索算法（例如 A*）的最优性。
- 您认为什么
启发式是正确的，A*似乎工作得很好，您有一个例子吗，也许是在c或java中？
The 15 Puzzle is a classical problem for modelling algorithms involving heuristics. Commonly used heuristics for this problem include counting the number of misplaced tiles and finding the sum of the Manhattan distances between each block and its position in the goal configuration. Note that both are admissible, i.e., they never overestimate the number of moves left, which ensures optimality for certain search algorithms such as A*.
- What
Heuristicdo you think is proper,A*seems to work nice, do you have an example, maybe incorjava?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
启发式
我选择的启发式是找出排列中所有反转的总和是奇数还是偶数 - 如果是偶数，则 15Puzzle 是可解的。
只有当我知道它可以解决时，解决它才有意义。接下来的任务是减少逆数并解决中提琴问题。找到解决方案的步数不应超过 80 步。
更多帮助
排列方程为：
0 到 16 范围内的阶乘为 {1, 2, 6、24、120、720、5040、40320、362880、3628800、39916800、479001600、6227020800、87178291200、1307674368000、20922789888000 }。如果您需要更多，请在 WolframAlpha 中搜索 范围[1,20]！
如果您想了解更多信息，请阅读：15Puzzle。
Heuristic
My heuristic of choice is to find if the sum of all inversions in a permutation is odd or even - if it is even, then the 15Puzzle is solvable.
Only if I know it can be solved does it make sense to solve it. The task then is to reduce inverses and - viola problem solved. To find a solution should be no more then 80 moves.
Even more help
The equation for permutation is:
Factorials in range of 0 to 16 are {1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000}. If you need more of them, search WolframAlpha for Range[1,20]!
If you want to learn more about it read: 15Puzzle.
使用 A* 算法在 C++ 中实现十五个谜题 https://gist.github.com/sunloverz/7338003
Fifteen puzzle implemetation in C++ using A* algorihtm https://gist.github.com/sunloverz/7338003