15益智启发 [英] 15 Puzzle Heuristic

问题描述

在 15拼图是涉及启发式建模算法一个经典问题。常用启发式针对此问题包括计数错位的瓦片的数目，并找到每个块和其在目标的配置位置之间的曼哈顿距离的总和。需要注意的是两者都可以受理，也就是说，他们从来没有高估离开移动次数，从而确保最优某些搜索算法，如A *。

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*.

• 什么启发式你认为是正确的， A * 似乎工作不错，你有一个例子，也许在 C 或的Java ？

• What Heuristic do you think is proper, A* seems to work nice, do you have an example, maybe in c or java?

推荐答案

我选择的启发是要找到，如果所有的倒在置换之和为奇数或偶数 - 如果它是偶数，那么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.

反转的中的置换的数目等于其逆置换的（1990 Skiena，第29页; Knuth的1998）。

The number of inversions in a permutation is equal to that of its inverse permutation (Skiena 1990, p. 29; Knuth 1998).

只有当我知道这是可以解决的是否有意义来解决它。然后，该任务是减少逆和 - 中提琴问题解决了。为了找到一个解决办法应该是没有更多的则80的动作。

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.

该公式排列为：

阶乘在0至16范围是{1，2，6，24，120，720，5040，40320，362880，3628800，39916800，479001600，6227020800，87178291200，1307674368000，20922789888000}。如果你需要更多的人，搜索 WolframAlpha的获得的范围[1,20]！

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]!

如果您想了解更多关于它阅读： 15Puzzle

If you want to learn more about it read: 15Puzzle.

这篇关于15益智启发的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！