目录

文章目录

前言

一、八数码难题是什么？

二、算法详解

1.启发函数（曼哈顿距离）

2.状态移动处理

3. A*搜索并返回路径

三、完整代码（注释很详尽）

总结

前言

本文用python实现A*算法解决了八数码问题，有被八数码问题困扰的uu们，抓紧时间，进入正文，一定会对你有所帮助！

一、八数码难题是什么？

八数码问题是在一个3×3的棋盘上有1−8位数字随机分布，以及一个空格，与空格相连的棋子可以滑动到空格中，问题的解是通过空格滑动，使得棋盘转化为目标状态，如下图所示。

7 2 4 012

5 0 6 ———–> 3 45

8 3 1 678

init statetarget state

为了简化问题的输入，首先将空格用数字0表示，然后将3×3的棋盘用9位长的字符串表示，则上图的初始状态为724506831，目标状态为012345678.

对于上图的初始状态，将数字2移动到空格，称之为u操作（空格上移），将数字3移动到空格，称之为d操作（空格下移），将数字5移动到空格，称之为l操作（空格左移），将数字6移动到空格，称之为r操作（空格右移）

二、算法详解

1.启发函数（曼哈顿距离）

 def calcDistH(self, src_map, dest_map):#采用曼哈顿距离作为估值函数cost = 0for i in range(len(src_map)):if (src_map[i] != '0'):cost += abs(int(src_map[i])//3-i//3) + \abs(int(src_map[i]) % 3-i % 3)return cost

2.状态移动处理

def moveMap(self, cur_map, i, j):cur_state = [cur_map[i] for i in range(9)]cur_state[i] = cur_state[j]cur_state[j] = '0'return "".join(cur_state)

3. A*搜索并返回路径

def salvePuzzle(self, init, targ):#传入初始状态init,目标状态targ，返回移动路径（string形式）open = [(init, self.calcDistH(init, targ))]#open表元素(状态，f值)closed = {}dict_depth = {init: 0}#深度表，用来记录节点是否被访问过及对应的深度dict_link = {}#关系表，用来记录父子关系，孩子-->父亲dict_dirs = {'u': [-1, 0], 'd': [1, 0], 'l': [0, -1], 'r': [0, 1]}#移动方向，对应二维坐标的变化dirs = ['l', 'r', 'u', 'd']path = []#用来记录移动路径while (len(open)):open.sort(key=lambda open: open[1])#每循环一次对列表按由小到大排序一次while (open[0][0] in closed):open.pop([0])#如果表头元素在closed表中，移出open表if (open[0][0] == targ):print("Successfully!")breaktop = open[0]open[0:1] = []closed[top[0]] = top[1]#取表头元素，并将表头元素移出open表，压入closed表cur_index = top[0].index('0')for i in range(4):x = cur_index // 3 + dict_dirs[dirs[i]][0]y = cur_index % 3 + dict_dirs[dirs[i]][1]if (x >= 0 and x = 0 and y < 3):next_index = x*3+ynext_state = self.moveMap(top[0], cur_index, next_index)depth = dict_depth[top[0]]+1#当前节点不在深度表中，压入深度表和open表，并建立父子关系if ((next_state in dict_depth) == False):dict_depth[next_state] = depthopen.append((next_state, depth+self.calcDistH(next_state, targ)))dict_link[next_state] = top[0]else:#当前节点在深度表中且当前深度小于深度表中的值，更新深度表，建立父子关系if (depth ","".join(path))return "".join(path)

三、完整代码（注释很详尽）

class Astar:def salvePuzzle(self, init, targ):#传入初始状态init,目标状态targ，返回移动路径（string形式）open = [(init, self.calcDistH(init, targ))]#open表元素(状态，f值)closed = {}dict_depth = {init: 0}#深度表，用来记录节点是否被访问过及对应的深度dict_link = {}#关系表，用来记录父子关系，孩子-->父亲dict_dirs = {'u': [-1, 0], 'd': [1, 0], 'l': [0, -1], 'r': [0, 1]}#移动方向，对应二维坐标的变化dirs = ['l', 'r', 'u', 'd']path = []#用来记录移动路径while (len(open)):open.sort(key=lambda open: open[1])#每循环一次对列表按由小到大排序一次while (open[0][0] in closed):open.pop([0])#如果表头元素在closed表中，移出open表if (open[0][0] == targ):print("Successfully!")breaktop = open[0]open[0:1] = []closed[top[0]] = top[1]#取表头元素，并将表头元素移出open表，压入closed表cur_index = top[0].index('0')for i in range(4):x = cur_index // 3 + dict_dirs[dirs[i]][0]y = cur_index % 3 + dict_dirs[dirs[i]][1]if (x >= 0 and x = 0 and y < 3):next_index = x*3+ynext_state = self.moveMap(top[0], cur_index, next_index)depth = dict_depth[top[0]]+1#当前节点不在深度表中，压入深度表和open表，并建立父子关系if ((next_state in dict_depth) == False):dict_depth[next_state] = depthopen.append((next_state, depth+self.calcDistH(next_state, targ)))dict_link[next_state] = top[0]else:#当前节点在深度表中且当前深度小于深度表中的值，更新深度表，建立父子关系if (depth ","".join(path))return "".join(path)def calcDistH(self, src_map, dest_map):#采用曼哈顿距离作为估值函数cost = 0for i in range(len(src_map)):if (src_map[i] != '0'):cost += abs(int(src_map[i])//3-i//3) + \abs(int(src_map[i]) % 3-i % 3)return costdef moveMap(self, cur_map, i, j):cur_state = [cur_map[i] for i in range(9)]cur_state[i] = cur_state[j]cur_state[j] = '0'return "".join(cur_state)#本程序实现了Astar类，可通过创建Astar对象来调用相关方法#以下仅为测试用例test=Astar()test.salvePuzzle("724506831","012345678")

总结

以上就是今天要讲的内容，本文介绍了如何使用python实现A*算法，解决八数码难题，希望能够对uu们有所帮助，如果有uu们有不懂的问题或者有更好的创意和建议，可以在评论区留下宝贵意见，随时欢迎私信博主，给博主点个关注，留个赞，博主不胜感激