15拼图启发式
cMi*_*nor 3 algorithm artificial-intelligence heuristics
这15 Puzzle是涉及启发式的建模算法的经典问题.针对此问题的常用启发式方法包括计算错放的磁贴的数量,并找出每个块与其在目标配置中的位置之间的曼哈顿距离的总和.请注意,两者都是可接受的,即它们永远不会高估剩余的移动次数,这可确保某些搜索算法(如A*)的最佳性.
Heuristic你认为什么是正确的,A*似乎工作得很好,你有一个例子,也许在c或java？
启发式
我的选择启发式是找出排列中所有倒置的总和是奇数还是偶数 - 如果是偶数,那么15Puzzle是可解的.
置换中的倒置数等于其逆置换的倒数(Skiena 1990,p.29; Knuth 1998).
只有我知道它可以解决才有意义解决它.那么任务就是减少逆,并解决中提问题.要找到解决方案,应该不超过80步.
更多的帮助
置换方程为:
在0到16范围内的因子是{1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000}.如果你需要更多它们,请搜索WolframAlpha for Range [1,20]!
如果你想了解更多关于它的信息,请阅读:15Puzzle.