15 拼图启发式算法

Question

3

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

- edgarmtze

不管代码怎样，只要提供启发式建议或您的意见即可。 - edgarmtze

3

与使用A*算法解决15数码问题相关的问题。 - jfs

2个回答

1

使用A*算法在C++中实现的十五拼图https://gist.github.com/sunloverz/7338003

- Aydar Omurbekov

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Margus · Accepted Answer

启发式算法

我的选择启发式算法是找出排列中所有逆序对的和是奇数还是偶数——如果是偶数，那么15Puzzle是可解的。

排列中逆序对的数量等于其逆置排列的数量（Skiena 1990年，第29页；Knuth 1998年）。

只有当我知道它是可解的时候，才有解决它的意义。因此，任务就是减少逆序对，问题就迎刃而解了。要找到一个解决方案，不应超过80步。