目录
文章目录
前言
一、八数码难题是什么？
二、算法详解
1.启发函数（曼哈顿距离）
2.状态移动处理
3. A*搜索并返回路径
三、完整代码（注释很详尽）
总结
前言
本文用python实现A*算法解决了八数码问题，有被八数码问题困扰的uu们，抓紧时间，进入正文，一定会对你有所帮助！
一、八数码难题是什么？
八数码问题是在一个3×3的棋盘上有1−8位数字随机分布，以及一个空格，与空格相连的棋子可以滑动到空格中，问题的解是通过空格滑动，使得棋盘转化为目标状态，如下图所示。
7 2 4 0 1 2
5 0 6 -----------> 3 4 5
8 3 1 6 7 8
init state target state
为了简化问题的输入，首先将空格用数字0表示，然后将3×3的棋盘用9位长的字符串表示，则上图的初始状态为724506831，目标状态为012345678.
对于上图的初始状态，将数字2移动到空格，称之为u操作（空格上移），将数字3移动到空格，称之为d操作（空格下移），将数字5移动到空格，称之为l操作（空格左移），将数字6移动到空格，称之为r操作（空格右移）
二、算法详解
1.启发函数（曼哈顿距离）
- def calcDistH(self, src_map, dest_map):
- #采用曼哈顿距离作为估值函数
- cost = 0
- for 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!")
- break
- top = 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 < 3 and y >= 0 and y < 3):
- next_index = x*3+y
- next_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] = depth
- open.append(
- (next_state, depth+self.calcDistH(next_state, targ)))
- dict_link[next_state] = top[0]
- else:
- #当前节点在深度表中且当前深度小于深度表中的值，更新深度表，建立父子关系
- if (depth < dict_depth[next_state]):
- dict_depth[next_state] = depth
- dict_link[next_state] = top[0]
- #如果当前节点在closed表中，将其移出closed表，将更新后的节点移入open表
- if (next_state in closed):
- del closed[next_state]
- open.append(next_state, depth +
- self.calcDistH(next_state, targ))
- #循环结束，路径关系全部在dict_link中，从目标状态出发寻找路径
- s = targ
- while (s != init):
- move = s.index('0')-dict_link[s].index('0')
- if (move == -1):
- path.append('l')
- elif (move == 1):
- path.append('r')
- elif (move == -3):
- path.append('u')
- else:
- path.append('d')
- s = dict_link[s]
- path.reverse()
- #将path逆序(如果想要打印出路径每一步的状态，只需要按照path和init就能实现)
- print("SearchPath->","".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!")
- break
- top = 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 < 3 and y >= 0 and y < 3):
- next_index = x*3+y
- next_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] = depth
- open.append(
- (next_state, depth+self.calcDistH(next_state, targ)))
- dict_link[next_state] = top[0]
- else:
- #当前节点在深度表中且当前深度小于深度表中的值，更新深度表，建立父子关系
- if (depth < dict_depth[next_state]):
- dict_depth[next_state] = depth
- dict_link[next_state] = top[0]
- #如果当前节点在closed表中，将其移出closed表，将更新后的节点移入open表
- if (next_state in closed):
- del closed[next_state]
- open.append(next_state, depth +
- self.calcDistH(next_state, targ))
- #循环结束，路径关系全部在dict_link中，从目标状态出发寻找路径
- s = targ
- while (s != init):
- move = s.index('0')-dict_link[s].index('0')
- if (move == -1):
- path.append('l')
- elif (move == 1):
- path.append('r')
- elif (move == -3):
- path.append('u')
- else:
- path.append('d')
- s = dict_link[s]
- path.reverse()
- #将path逆序(如果想要打印出路径每一步的状态，只需要按照path和init就能实现)
- print("SearchPath->","".join(path))
- return "".join(path)
-
- def calcDistH(self, src_map, dest_map):
- #采用曼哈顿距离作为估值函数
- cost = 0
- for 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
-
- 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)
-
- #本程序实现了Astar类，可通过创建Astar对象来调用相关方法
- #以下仅为测试用例
- test=Astar()
- test.salvePuzzle("724506831","012345678")
总结
以上就是今天要讲的内容，本文介绍了如何使用python实现A*算法，解决八数码难题，希望能够对uu们有所帮助，如果有uu们有不懂的问题或者有更好的创意和建议，可以在评论区留下宝贵意见，随时欢迎私信博主，给博主点个关注，留个赞，博主不胜感激
文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览43944 人正在系统学习中