【Python】A*八数码问题_求解思路与代码实现 A*八数码，求解思路与代码实现

#创作灵感#

人工智能导论课，要求用代码，实现八数码问题的求解。由于算法基础不扎实，除了课上老师的讲解，还去B站，搜集了相关资源，最后顺利完成课程实验。在这里做个分享，也是梳理一遍求解思路。

一、逻辑结构

空格可以往四个方向移动，给定初始状态、目标状态，求两个状态的最短路径、最短路径的长度。无法到达，则输出-1。空格上的数字，用0表示。

用一维数组，表示一个盘面，需要进行上下左右移动时，转换为二维数组，操作完成后，再转换为一维数组。一维数组下标，与二维数组下标的关系：A[6] = A[6//3][6%3]，A[1][2] = A[1*3+2]。

每次空格只能往四个方向移动一格，移动后的状态数组，与之前的状态数组，只有两个元素不同。四个方向的移动，对二维坐标的影响：

用两个数组，来记录X、Y的改变量，方便快速计算空格的二维新坐标：

 另外，如果不加以管控，八数码问题的状态空间是图，因为可能会出现重复结点，并进入死循环，求无权图的最短路径更适合BFS，找到目标状态就可以退出循环：

为避免死循环，需要对新入队结点，进行排重，可以定义查找列表。如果当前结点，在查找表中没有出现过，插入查找列表并入队，如果已经出现过，则不入队。没有重复结点产生，八数码的状态空间就可以看成树。

A*是用结点的估价函数值，决定访问的优先次序。估价函数为：f(x) = p(x) +s(x)。p(x)代表前半段距离(从初始状态，到该节点的距离，即结点深度)。s(x)代表后半段距离(从当前节点，到目标状态的估计距离)。s(x)设计的是否合理，决定搜索效率，这里用3倍当前结点到目标状态的曼哈顿距离，作为后半段距离s(x)的估计值。(两个盘面的曼哈顿距离，等于0除外的每个元素的曼哈顿距离之和，每个元素的曼哈顿距离，等于两个盘面中，该元素的横坐标之差+纵坐标之差，具体可以看一下这个视频：A*算法的书面求解步骤）

为了方便求曼哈顿距离，可以对目标状态”打表“，把每个数字的坐标打成二维形式,比如目标状态为goal = "436708125",那么可以定义列表x，y,就可以快速查到目标状态中相应数字的X、Y坐标：

大致的求解思路：先计算初始状态、目标状态的逆序数，如果奇偶性不相同，那么无解，返回-1( 相关的理论证明，在这个链接里：深入理解逆序数+八数码原理)。奇偶性相同，那么计算初始状态的代价f，并入队，进入循环，循环条件：如果队列不空。循环体为：

取队首元素，判断是否为目标状态，如果是，返回队首结点与初始状态的距离(即结点深度）。否则，按照上、下、左、右，依次循环扩展该结点，并计算新结点的估价值f。如果移动合法，产生新节点入队。四个方向搜索结束，队首结点出队，根据剩余结点的估价值f，对队列中所有结点排序，最后进入下一循环。

二、逻辑实现

一个结点st_state，包括两个数据项：估价值f、盘面state。估价值f为int类型，而盘面state的保存，用python字符串实现。最后用二元组，来存储这两个数据项。

所有的结点，用列表st来保存。当前结点与初始状态的距离，用列表dist存储。当前结点的父节点索引，用列表fu保存。最后从逻辑上看，应该是这样：

单个数据元素的结构：

数据元素间的关系(队列)：

入队出队操作：

上下左右移动，通过交换字符实现

从字符串的角度看，移动前后，其实就是置换两个字符的位置。其中一个字符是0，另一个字符，是某个相邻滑块。

如果找到两个字符的索引，交换位置是非常高效的。字符0的索引，通过for循环遍历得到。而相邻滑块的索引，可以通过字符0的索引，计算得到，方法如下：

先将0的索引，转换为二维坐标。如果state[z] = '0'，那么‘0’的二维坐标就是state[z//3][z%3]。

再根据上下左右移动，对坐标的影响，计算出空格的二维新坐标，例如state[X][Y]往i方向移动：

， 

此时将state[newX][newY]转换成一维坐标：

，

这样，就能够得知，与0交换位置的，相邻滑块的索引。从逻辑上看，应该是这样的：

先找到0的索引：

转换为二维坐标：

往i方向移动，以i=1(下移)为例，计算移动后的二维新坐标：

转换为一维坐标，就能够知道，索引为5、8指向的字符，交换位置,就是下移后的状态数组：

三、代码实现

import sys
init_lookup_table = [] #定义查找表为全局变量，确保每个函数都能访问到
#打印初始状态、目标状态，在转换为二维数组后，每个元素的x、y坐标
def daBiao(state):
 #创建X、Y数组，用于存放坐标信息
 state_X = list(range(9))
 state_Y = list(range(9))
 #将0的x、y置为-1，不会计算0元素的曼哈顿距离
 state_X[0],state_Y[0] = -1,-1
 #计算状态中每个元素的坐标
 for i in range(9):
 #计算下表为i的元素的x、y
 x = i // 3
 y = i % 3
 #判断当前元素是1-8中的谁
 value_ = int(state[i])
 #修改对应元素的二维坐标
 state_X[value_] = x
 state_Y[value_] = y
 #循环结束，返回X，Y
 return state_X,state_Y
# 计算某个状态state，与goal的曼哈顿距离
def man_ha_dun(state,goal):
 # 对初始状态\目标状态打表，为后续计算曼哈顿距离做准备
 goal_x,goal_y = daBiao(goal)
 # 计算曼哈顿距离
 list = 0 # 初始化
 for i in range(9):
 if state[i] == '0': #表示不计算空格的曼哈顿距离
 break
 # 获取第i个元素的值，计算该元素的曼哈顿距离
 value_ = int(state[i])
 # 获取该元素的二维坐标
 X = i // 3
 Y = i % 3
 # 根据initial_x、initial_y,计算出该元素的曼哈顿距离
 list_i = abs(goal_x[value_] - X) + abs(goal_y[value_] - Y)
 list += list_i
 if state[4] != '0': #如果中间有将牌，那么list+1
 list += 1
 return list
#计算逆序数
def ni_xu_shu(data):
 answer = 0
 data_list = []
 for i in data: #遍历字符串data
 if int(i) != 0:
 data_list.append(int(i)) #把不为0的放前面
 data_list.append(0) #队尾加0
 #计算data_list的逆序数
 for i in range(8): #计算前7个数的逆序数,最后一个数的逆序数为0
 for j in range(i+1,9): #第i个元素，依次与后面i+1个元素比较
 if data_list[i] > data_list[j]: #如果满足条件，逆序数+1
 answer += 1
 return answer
# 判断某个元素是否被访问过，如果没有被访问过，则返回True，并加入查找表
def try_to_insert(st_state):
 global init_lookup_table
 if init_lookup_table.count(st_state) == 0:
 init_lookup_table.append(st_state)
 return True
 else:
 return False
#重排序函数，根据新入队节点的曼哈顿距离，返回一个新的节点顺序，调整其在队列中的位置（调整访问顺序）
def soreted_st_state(new_st_state_list):
 return sorted(new_st_state_list,key=lambda x:x)
#A*算法，搜索到目标状态后，返回与初始状态的距离、访问路径，否则返回-1，表示不可到达
def A_star(initial,goal):
#0、先判断有无解
 #求initial、goal的逆序数
 initial_nixushu = ni_xu_shu(initial)
 goal_nixushu = ni_xu_shu(goal)
 #判断有无解，如果无解，返回-1
 if (initial_nixushu % 2 == 0)and(goal_nixushu % 2 != 0) or (initial_nixushu % 2 != 0)and(goal_nixushu % 2 == 0):
 # 如果奇偶性不同，返回-1,表示无解
 return -1,None
#1、定义好基本的变量，做准备
 #定义队列state的最大入队元素数量(最大搜索节点数，避免不可到达而死循环)
 Max_st = 100000
 #定义队列st、距离数组distance、存储父亲节点索引的fu
 st = []
 distance = list(range(Max_st))
 fu = list(range(Max_st))
 #注意：st的元素都是二元组,需要单独定义，开一个这样的列表
 for i in range(Max_st):
 st.append((i,"012345678"))
 #定义队首指针front、队尾指针rear
 front,rear = 1,2
 #定义好上下左右四个操作，对x\y改变的两个数组
 dx = [-1,1,0,0]
 dy = [0,0,-1,1]
 #求出initial到goal的曼哈顿距离，初始化distance,fu、st、init_lookup_table
 initial_f = 0 + 3*man_ha_dun(initial,goal)
 distance[1] = 0 #表示初始状态到初始状态的距离为0
 fu[1] = -1 #表示初始状态没有父结点
 #将节点表示为元组的形式，保存在查找表、st中(元组的1号位表示代价，2号位表示字符序列)
 initial_st = (initial_f,initial)
 st[front] = initial_st
 global init_lookup_table
 init_lookup_table.append(initial_st)
 count_iter = 0 #记录循环次数
#3、开始搜索
 while front != rear:
 #判断当前队首节点是否为goal_st,如果是，则返回与initale的距离、访问路径
 if st[front][1] == goal:
 da_ying = [st[front][1]] #用于反向打印
 fu_index = front #定义一个变量，记录当前结点的父节点索引
 while fu[fu_index] != -1: #初始状态没有父节点
 #把当前节点的父节点添加进打印队列中
 da_ying.append(st[fu[fu_index]][1])
 #准备把父节点的父节点加入队列
 fu_index = fu[fu_index]
 return distance[front],da_ying
 #否则扩展队首节点，按照0元素上下左右
 #先找到0元素的一维下标z
 z = 0
 for i in range(9):
 if st[front][1][i] == '0':
 z = i
 break
 #再算0的二维坐标
 x = z // 3
 y = z % 3
 for i in range(4): #开始扩展节点
 new_x = x + dx[i] #移动s后的X坐标
 new_y = y + dy[i] #移动后的Y坐标
 new_z = new_x * 3 + new_y #移动后的一维坐标
 if (new_x>=0) and (new_x=0) and (new_y

四、写在最后的话

下面相关的视频链接，精心挑选的，可以看一下：

BFS求解八数码、八数码书面求解、曼哈顿距离

要学的还有很多，代码实战很关键啊。