[LeetCode]Sliding Puzzle

这道题要我们求最少的move数使得我们可以solve它。这道题我们每次可以进行的操作就是，0和其相邻的tile互换，所以我们根据这一点每次找当前状态的邻接节点即可。时间空间复杂度均为O(4^d)，d为从当前状态到目标状态的最小距离。代码如下：

另外一种做法是A* search，在bfs或者其他非启发式搜索的时候我们keep track of的都是当前状态从开始状态转移过来已经travel的距离g(n)。但是A* search，作为启发式搜索算法，会在搜索的时候考虑估算从当前节点到目标节点的距离，也就是启发方程，heuristic fucniton h(n)。我们在搜索的时候，不再是单纯地考虑已经走过的距离，而是将两者结合在一起:

• f(n) = g(n) + h(n)

其中g(n)代表的是从初始节点到达当前节点走过的距离，h(n)代表的是当前节点到目标节点的估算距离。这里h(n)有几个性质:

• 如果h(n)从来不高估从当前节点到目标节点的距离的话，可以保证让我们找到最优解。我们称这种h(n)为admissble heuristic
• 如果h(n)满足h(n)  <= h(n') + w(n, n')，其中n和n'为相邻节点，w(n, n')为两个节点边的权重，我们称h(n)为consistent或者monotone。那么当我们跑类似dijkstra算法从priority queue上展开节点的时候，到当前节点的最短路径就被找到了。因为f(n) = g(n) + h(n) <= g(n) + h(n') + w(n, n') = g(n') + h(n') = f(n')，也就是说，f(n)在任意一条路径上都是递增的，那么我们只需要用类似dijkstra的证明方法证明即可，这里不做赘述
• 如果h是consistent的并且在目标节点处为0，那么其一定是admissible的。假设n节点经过v1，v2...组成的最短路径到达目标节点t，我们有h(n) <= h(v1) + w(v1, n) <= h(v2) + w(v1, v2) + w(v1, n) <= ... <= shortestPath(n, t) + h(t) = shortestPath(n, t)，这对任意n都成立，证明完毕

回归到这一题，我们可以用所有除了0以为的tile距离目标位置的曼哈顿距离的和做heuristic function，那么h(n)一定是consistent并且admissible的:

• 在目标节点处h为0
• 我们每次只能讲一个tile和0互换，从n状态变为n'，cost为1，这样最多只能把h(n)到h(n')减小1。所以满足h(n)  <= h(n') + w(n, n')

所以我们只需要按照这个f(n)进行A star search即可，实现的话用priority queue，时间复杂度O(d log d)，d为最短路径，因为所有f(n)小于d的节点都会被展开。代码如下: