A*算法求解八数码难题（python实现）_class solution: def salvepuzzle(self, init, targ):

目录

文章目录

前言

一、八数码难题是什么？

二、算法详解

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们有不懂的问题或者有更好的创意和建议，可以在评论区留下宝贵意见，随时欢迎私信博主，给博主点个关注，留个赞，博主不胜感激