[Algo] Eight Puzzle Game 九宫格游戏 - SegmentFault
Eight Puzzle Game
九宫格游戏，给定最终状态如下，再给出一个初始状态，0代表空位，相邻的格子中的方块可以和0互换位置，求初始状态到最终状态的最小步数。
1 2 3 4 5 6 7 8 0
A*搜索
思路
典型的A*算法应用，我们将棋盘的状态抽象为类似"123456780"的字符串，其中0代表空位，然后每3位代表一行，这时候我们从起始状态开始搜索，搜索中使用一个优先队列存放边缘节点，类似于广度优先搜索，但我们每次取出来的都是函数值最小的节点。这里函数值f(n) = g(n) + h(n)，其中g(n)是到达当前节点的开销，这里也就是步数，而h(n)是指我们对这个节点计算的heuristic值，这题我们有两种可选方法计算heuristic值：
判断错位的格子数量，比如拍
213456780中，2和1是错位的，所以h值是2判断每个格子中数字和其目标状态的位置的曼哈顿距离之和
这里为了实现简单，我们采取第一种，但实际上第二种heuristic优化的时间可以达到一个数量级之上，因为这里第二种总是dominant第一种。
Read full article from [Algo] Eight Puzzle Game 九宫格游戏 - SegmentFault
No comments:
Post a Comment