华容道/滑块问题算法改进 （使用A*算法）

https://leetcode.com/problems/sliding-puzzle/

code on github

我之前写过 一篇关于这个问题的解法，想法是使用双向BFS在中间找到重合状态，这样可以在搜索的初期就找到结果，减少搜索空间。 但是双向BFS的问题在于代码复杂度有点高，容易出现bug. 其实这道题目使用A*算法是可以比较好解决的，而且代码也不复杂。

我这边使用的评估函数很简单，就是计算每个单元格到自己应该的位置的 *曼哈顿距离*。只要评估函数小于真实距离的话，那么最终是可以得到最优解的。

def cost(self):
    ans = 0
    n, m = self.n, self.m
    for i in range(n * m):
        dx, dy = i // m, i % m
        if self.data[i] == 0:
            ans += abs(n - 1 - dx) + abs(m - 1 - dy)
        else:
            x, y = (self.data[i] - 1) // m, (self.data[i] - 1) % m
            ans += abs(x - dx) + abs(y - dy)
    return ans

可以看到结果还是非常喜人的，时间能缩短到原来的1/5.

➜  misc git:(master) ✗ python3 sliding-puzzle-astar.py
================================
[[8, 6, 7], [2, 5, 4], [3, 0, 1]]
BFS: timers = 3.2484140396118164, ans = 31
A*: timers = 0.6865568161010742, ans = 31
================================
[[6, 4, 7], [8, 5, 0], [3, 2, 1]]
BFS: timers = 3.429565191268921, ans = 31
A*: timers = 0.845940113067627, ans = 31