a算法八数码问题图解（探索八数码问题）

探索八数码问题

问题简介

　　八数码问题又称八数码拼图、九宫问题或九连环等，是一个益智玩具，玩具的形式是，有一个3*3九宫格，摆放着1-8这8个数字和一个空格，你可以在相邻的格子之间移动这些数字，最终目标是将其按顺序排列，即排列为如下形式： 1 2 3 4 5 6 7 8      　　在实际生活中，我们经常遇到各种各样的八数码问题，例如：给出两个状态，如何从一个状态转移到另一个状态；如何确定从初始状态到目标状态的最短路径等。本文主要介绍通过A*算法求解八数码问题的过程和思路。

问题分析

　　八数码问题的解法有很多，其中A*算法是比较基础且常用的算法之一。该算法可以帮助我们找到从起点到终点的最短路径，它的实现思路如下： 　　（1）首先，在进入搜索状态之前，需要将起点状态、终点状态及初始空格的位置记录下来，同时初始化open表和closed表，将起点状态（原始状态）加入到open表中； 　　（2）进一步，对每一个出队（即扩展）状态，根据估价函数计算它的评估值，如果该状态为目标状态，则返回路径；否则，将该状态的节点加入到open表中，同时标记该状态为处理过的状态； 　　（3）接着，从open表中选择一个评估值最小的状态，并将其从open表中删除，同时将其节点加入到closed表中； 　　（4）最后，重复第（2）步和第（3）步，直到open表为空或找到目标状态为止。

算法实现

　　对于该问题，采用A*算法的关键在于如何设置状态的估价函数。我们可以将距离目标状态的“曼哈顿距离”作为估价函数，具体实现方法如下： 　　（1）首先，定义状态的评估函数F（n）= G（n）+ H（n），其中： 　　　　G（n）表示已经花费的步数（即起点到当前状态的步数）； 　　　　H（n）表示估价函数，即从当前状态到目标状态的估价。 　　（2）接着，用一个数组dis[][]来记录状态之间的“曼哈顿距离”（即到目标状态的最短距离之和）。 　　（3）最后，根据dis[][]来计算每个状态的估价值H（n），即将每个数字对应的距离相加。 　　下面是A*算法求解八数码问题的具体实现： ```python def move(x,y,dir): if dir==0: return x-1,y # up if dir==1: return x,y+1 # right if dir==2: return x+1,y # down if dir==3: return x,y-1 # left def h(a,end): s=0 for i in range(3): for j in range(3): if a[i][j]==0: continue s+=dis[a[i][j]][end[i][j]] return s def astar(start,end): h1=h(start,end) global ans,f1 f1[h1]=1 cur={'g':0,'h':h1,'step':'','a':start} heap=[cur] while heap: u=heap.pop(0) if u['a']==end: ans=u['step'] return for i in range(4): newx,newy=move(u['a'][0].index(0),u['a'][1].index(0),i) if newx<0 or newx>2 or newy<0 or newy>2: continue a=copy.deepcopy(u['a']) a[newx][newy],a[u['a'][0].index(0)][u['a'][1].index(0)]=0,a[newx][newy] h1=h(a,end) if f1.get(h1) is None: f1[h1]=1 v={'g':u['g']+1,'h':h1,'step':u['step']+chr(ord('A')+i),'a':a} heap.append(v) heap.sort(key=lambda x:x['g']+x['h']) return ``` 　　需要解释一下上述代码中的参数： 　　start为起点状态矩阵，end为终点状态矩阵，f1为全局变量，用于记录已访问状态的估价函数值是否出现过，ans表示最短路径。 　　整个算法的时间复杂度为O(nlogn)，其中n表示状态的数量。如果采用BFS算法，则时间复杂度为O(n)，但会遇到内存超限的问题。

总结

　　八数码问题是谷歌面试的常见问题之一，通过本文的介绍，我们可以知道这个问题可以用A*算法求解。A*算法是一种常用的图的遍历算法，具有启发式的特点，在搜索过程中能够尽可能地引导搜索方向，从而有效地减少搜索次数，快速地找到最优解。