用A-star算法解决八数码问题

参考文章

问题描述

八数码问题其实就是数字华容道，九宫格里放着8个数块，有一格是空的，要求出从一种状态到目标状态所需的最小移动数和移动方法。

问题解决

A*算法

关于A*算法相关的内容在这篇文章中，这里不再解释。这里需要搞明白状态空间和启发函数才能应用A*算法。

搜索空间

这个问题的搜索空间是一棵搜索树，根节点是初始状态节点，每一个节点做上下左右的移动都可以产生一棵新的四叉子树。

定义状态空间

状态空间（一个节点所有可能的状态）就是一个九宫格。初末状态可以用数组表示（空格为0）：

start_data = np.array([[2, 8, 3], [1, 6, 4], [7, 0, 5]]) 
end_data = np.array([[1, 2, 3], [8, 0, 4], [7, 6, 5]])

可以用空格在状态空间中的移动（和其他格子的交换）作为一次“操作”。

空格是不能移出边界的，所以在互换位置时要做判断，不要让空格移出去了。

def find_zero(num):
    tmp_x, tmp_y = np.where(num == 0)
    return tmp_x[0], tmp_y[0]
def swap(num_data, direction):
    x, y = find_zero(num_data)
    num = np.copy(num_data)
    if direction == 'left':
        if y == 0:
            # 已经顶到左边，不能左移，直接返回原数组
            return num
        num[x][y] = num[x][y - 1]
        num[x][y - 1] = 0
        return num
    	# 如果可以移动，返回移动后的数组
    if direction == 'right':
        if y == 2:
            return num
        num[x][y] = num[x][y + 1]
        num[x][y + 1] = 0
        return num
    if direction == 'up':
        if x == 0:
            return num
        num[x][y] = num[x - 1][y]
        num[x - 1][y] = 0
        return num
    if direction == 'down':
        if x == 2:
            return num
        else:
            num[x][y] = num[x + 1][y]
            num[x + 1][y] = 0
            return num

定义启发函数

这里把启发函数定义为

$$f(n)=d(n)+w(n)$$

$d(n)$是搜索树深度，$w(n)$是当前状态到目标的最小开销，可以用所有数字到正确位置的曼哈顿距离来定义，或位置错误（当前相比于目标的区别）的数字个数。

# 计算w(n)
def cal_wcost(num):
    con = 0
    for i in range(3):
        for j in range(3):
            tmp_num = num[i][j]
            compare_num = end_data[i][j]
            if tmp_num != 0: # 空位对不上不算，否则会多算一次
                con += tmp_num != compare_num
    return con

计算所有放错位置的东西，返回的是放错位置的和。

A*算法实现

概述

A*算法就是每次从open list拿一个点出来执行一系列操作。可以依据这个流程搭建大致框架。

def A_star():
    while True:
        if len(opened.queue) == 0:
            break
        else:
            current_node = opened.get() # 从队头拿一个点出来做处理。这里的node就是A*算法中的广义节点

如果每次都从队头拿点，那每次更新open队列时都要做排序。

注意

这里所谓的节点不是棋盘上的一个格，每一个节点其实都是一整张棋盘。在搜索时状态更新是以期盼状态为单位的，每次移动都会产生一张新的棋盘。

在搜索时，无非就是选一个最接近目标的状态来搜，通俗来讲就是，在当前状态下，分别做上下左右的移动后，谁更值得继续进行下去？

大致框架

opened = queue.Queue()  # open表
closed = {}  # close表
def A_star():
    while True:
        if len(opened.queue) == 0:
            break
        else:
            current_node = opened.get() # 如果队头的元素已经在正确位置（这个节点的状态和目标状态一致），直接返回，此时已经排好了
            if (node.data == end_data).all():
                 print(f'共搜索{con}轮')
    			return node
            # TODO: 取出的点加入closed
            # 4种搜索动作(类比寻路时的上下左右)
            for action in ['left', 'right', 'up', 'down']:
                # TODO: 创建子节点
                # TODO: 判断是否在closed表中
                    # TODO: 对于搜索到的点，如果不在close表中同时又不在open表，将其加入opened表
            # TODO: 根据f值对open list排序

节点数据结构

对于状态空间中的每一个点，都需要记录：

① 当前状态（这个点上现在各个位置上都是几）；

② 启发函数值（每一轮更新后用来排序）；

③ 父节点；

④ 当前已经走过的步数（这也就是搜索树的深度$d$）。

所以可以把数据结构定义为：

class Node:
    f_loss = -1  # 启发函数值
    step = 0  # 初始状态到当前状态的步数
    parent = None  # 父节点

    def __init__(self, data, step, parent):
        self.data = data  # 当前状态数值
        self.step = step
        self.parent = parent
        self.f_loss = cal_wcost(data) + step

根据输入的numpy数组创建初始节点并加入open表：

start_data = np.array([[2, 8, 3], [1, 6, 4], [7, 0, 5]])
opened = queue.Queue()
start_node = Node(start_data, 0, None)
opened.put(start_node)

同理也可以创建出目标状态的点。

创建子节点

child_node = Node(swap(node.data, action), node.step + 1, node)

也就是对当前节点依次做一遍上下左右的操作，每访问（用它做出一套子节点）一个节点，就算走了一步，在步数上+1。

更新open list的操作

这一步要判断一个点是否在open list中，如果不在就加进来，如果不在，就看看现在加进来的话$f$值会不会更小。如果不会，就不动；如果确实会更小，就加进来并更新它的父节点和各个值：

def refresh_open(now_node):
    tmp_open = opened.queue.copy()
    for i in range(len(tmp_open)):
        data = tmp_open[i]
        now_data = now_node.data
        if (data == now_data).all():
            data_f_loss = tmp_open[i].f_loss
            now_data_f_loss = now_node.f_loss
            if data_f_loss <= now_data_f_loss:
                # 如果在，但新情况的f值不会更小
                return False
            else:
                # 如果在，但是新情况的f值更小
                tmp_open[i] = now_node
                opened.queue = tmp_open
                return True
    # 如果不在open list，什么也不用判断直接加
    tmp_open.append(now_node)
    opened.queue = tmp_open
    return True

open list排序

排序时按$f$值排，如果$f$值相同就按步数小的优先。

def sorte_by_floss():
    tmp_open = opened.queue.copy()
    length = len(tmp_open)
    # 按f值冒泡排序
    for i in range(length):
        for j in range(length):
            if tmp_open[i].f_loss < tmp_open[j].f_loss:
                tmp = tmp_open[i]
                tmp_open[i] = tmp_open[j]
                tmp_open[j] = tmp
            if tmp_open[i].f_loss == tmp_open[j].f_loss:
                # 如果f值一样按步数排，找最优
                if tmp_open[i].step > tmp_open[j].step:
                    tmp = tmp_open[i]
                    tmp_open[i] = tmp_open[j]
                    tmp_open[j] = tmp
    opened.queue = tmp_open

回溯搜索路径（输出结果）

这一步中从最后一个节点依次往前找父节点指针直到达到初始节点：

def output_result(node):
    all_node = [node]
    for i in range(node.step):
        father_node = node.parent
        all_node.append(father_node)
        node = father_node
    return reversed(all_node)


node_list = list(output_result(result_node))
for node in node_list:
    num = node.data
	print(node.data) # 输出时只需要看状态即可

实验结果

写出代码之后做测试，由于在这个题目中，每增加一次“移动次数”，搜索次数就会指数级增加，所以在构造测试数据时尽量不要选太复杂的情况。

测试样例

样例一

start_data = np.array([[2, 8, 3], [1, 6, 4], [7, 0, 5]])
end_data = np.array([[1, 2, 6], [8, 4, 3], [0, 7, 5]])

样例二

start_data = np.array([[2, 8, 3], [1, 6, 4], [7, 0, 5]])
end_data = np.array([[2, 0, 3], [1, 6, 4], [8, 7, 5]])

样例三

start_data = np.array([[2, 8, 3], [1, 6, 4], [7, 0, 5]])
end_data = np.array([[1, 2, 3], [0, 6, 4], [8, 7, 5]])

测试结果

样例一

共花费861轮搜索，移动14步：

样例二

共花费56轮搜索，移动10步：

样例三

共花费15轮搜索，移动8步：

优化空间

既然限定了算法，优化就只有在启发函数上优化，找到一个更有效的启发函数，比如可以把$w$换成当前状态下所有数码距离目标的曼哈顿距离和。

实验心得

通过本次实验我对A*算法的理解不止停留在纸面或抽象的伪代码阶段，而是自己亲手把它实现出来并解决了实际问题。这使得我对A*算法这种人工智能基础算法的理解更加深入了，我相信这种理解能有助于我的后续学习。