目录

前言

八数码难题，也被称为八数码拼图或滑动谜题，是一种经典的逻辑益智游戏。它由一个3x3的方格组成，其中包含编号为1到8的数字方块和一个空白方块。游戏的目标是通过移动数字方块，将它们按照正确的顺序排列，最终使得所有数字从左上角开始按照从左到右、从上到下的顺序排列，空白方块位于最后。

游戏规则很简单，每次只能将相邻的数字方块与空白方块交换位置，通过不断移动和交换，最终达到目标状态。然而，由于数字方块的位置限制和移动的限制，很多时候需要进行复杂的操作和策略才能完成拼图。

八数码难题看似简单，但实际上是一个具有挑战性的问题。对于某些初始状态，可能需要经过大量的移动才能找到解决方案。在某些情况下，可能会出现无解的情况，即无法通过合法的移动操作将数字方块排列成目标状态。

八数码难题不仅仅是一种有趣的游戏，还是一个经典的计算机科学问题。它涉及到搜索算法、优化算法和人工智能等领域的研究。许多算法和策略被开发出来，用于解决八数码难题，其中最著名的算法之一是A*算法。

一、解决方法

1.状态空间表示

在这个问题中，有一个3x3的方格，其中包含数字1到8和一个空格（用0表示）。目标是通过移动数字，将初始状态转变为目标状态。移动可以是上、下、左、右四个方向之一，但只能移动到空格的位置。我的状态空间表示思路如下：

创建一个状态空间StateSpace类，创建静态变量target来存储目标状态。构造函数__init__接受一个状态和一个父状态作为参数，并初始化了状态空间的各个属性。其中state表示当前状态，parent表示父状态，初始化为None，g表示从起始状态到当前状态的路径长度，h表示当前状态的启发式函数值。g和h使用在A*算法中，前者代表着路径长度代价，后者是估价函数。

类中还重写了__eq__方法，用于比较两个状态空间是否相等；同时__hash__方法1也需要重写，由于状态空间用二维列表表示，而list本身是不可哈希的，所以我使用map函数2映射成元组形式用于表示哈希状态空间；__lt__方法，下文解释。

除此之外，类中还定义了一些辅助方法。例如，getZeroPos()函数返回空格0的位置坐标；getMoveState()函数根据给定的坐标，返回移动后的状态空间；getDirection()函数返回可行的移动方向；Bingo()函数检查当前状态是否达到目标状态，达到则返回True。

# /-*-/ encoding: UTF-8 \-*-\
import math

class StateSpace:
    # 在Github中寻找的测试数据目标状态是这个排列
    target = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]

    # 构造状态空间
    def __init__(self, state, parent=None):
        self.state = state
        self.parent = parent
        self.g = 0
        self.h = self.getH()

    # 重写==以方便状态空间比较
    def __eq__(self, other):
        return self.state == other.state

    # 重写哈希，列表不可哈希，转换成元组
    def __hash__(self):
        return hash(tuple(map(tuple, self.state)))

    # 比较两个状态空间的启发式函数值
    def __lt__(self, other):
        return self.getF() < other.getF()

    # 返回'0'所在的位置
    def getZeroPos(self):
        count_row = 0
        for i in self.state:
            count_col = 0
            for j in i:
                if j == 0:
                    return count_row, count_col
                count_col += 1
            count_row += 1

    # 返回行动后的状态空间
    def getMoveState(self, r1, c1, r2, c2):
        # 复制原状态空间
        Move = [r[:] for r in self.state]
        # 元素与空格交换位置
        a = Move[r1][c1]
        Move[r1][c1] = Move[r2][c2]
        Move[r2][c2] = a
        tmp = StateSpace(Move)
        return tmp

    def getDirection(self):
        i, j = self.getZeroPos()
        # 以下存放向上下左右的坐标表示形式
        all_dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        possibleMove = []
        for delta_x, delta_y in all_dir:
            # ni, nj表示移动后的位置，判断有没有超过3*3数组范围
            ni, nj = i + delta_x, j + delta_y
            if 0 <= ni < 3 and 0 <= nj < 3:
                possibleMove.append((ni, nj))
        return possibleMove

    def Bingo(self):
        return self.state == self.target

以上为状态空间的基本属性和操作

对于BFS和DFS等无信息搜索算法，以上函数已经足够，而A*算法则需要构建启发式函数来高效搜索，故在类中创建getH和getF函数，下文做解释。

    def getH(self):
        h = 0
        for i in range(3):
            for j in range(3):
                if self.state[i][j] != -1:
                    temp = ((0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2))
                    di,dj = temp[self.state[i][j] - 1]
                    sub = (abs(i - di)) + (abs(j - dj))
                    h += sub
        return h

    def getF(self):
        return self.g + self.h

2.BFS (广度优先搜索算法)

  1. 导入StateSpace类和time模块3（计时需要）。
from StateSpace import StateSpace
import time

  1. 定义了一个bfs函数，它接受一个初始状态空间State作为参数。 其初始化了一个空的队列open，表示待搜索的状态空间。初始化了步数step为0。使用一个集合closed来存放已经访问过的状态空间，避免重复搜索。

    将初始状态空间和步数作为元组(State, step)加入到队列open中。初始化搜索次数Searchtime为-1。使用循环来进行搜索，只要队列open不为空就一直进行搜索。每次从队列open中弹出一个状态空间State和对应的步数step。并使旧状态赋值为新状态的父节点。

    如果当前状态空间State达到目标状态（通过调用Bingo函数判断），则找到解。通过回溯父节点的方式，将路径上的每个状态空间添加到path列表中。初始化步数step_count为0。不断将父节点的状态空间添加到path中，直至parent为空。由于path列表中子状态在前，父状态在后，故倒转path列表，使得状态空间按照从初始状态到目标状态的顺序排列。遍历path列表，输出每个状态空间的步数和状态。返回解的步数steps和搜索次数Searchtime。

def bfs(State):
    open = []
    step = 0
    closed = set()
    # 存放初始状态空间和步数
    open.append((State, step))
    Searchtime = -1
    while open:
        Searchtime += 1
        # 状态弹出队列
        State, step = open.pop(0)
        # 如果匹配成功，通过父节点回溯状态空间找到根结点
        if State.Bingo():
            steps = 0
            path = []
            while State.parent is not None:
                path.append(State.state)
                State = State.parent
                steps += 1
            # 记录step并初始化为0
            step_count = 0
            path.append(State.state)
            # 回溯列表中的状态空间是反向添加的，所以需要倒转列表
            path.reverse()
            # 将列表中的数据输出
            for Statetmp in path:
                print("步数:", step_count )
                print_state(Statetmp)
                step_count+=1
            return (steps,Searchtime)

        # 检查能够向哪个方向移动
        possible = State.getDirection()
        for x, y in possible:
            # 与空格交换位置
            newState = State.getMoveState(State.getZeroPos()[0], State.getZeroPos()[1], x, y)
            # 存储父节点
            newState.parent = State
            # 将未被遍历的当前节点存入closed表，并将新结点放入open表中，步数+1
            if newState not in closed:
                closed.add(newState)
                open.append((newState, step + 1))
    return (-1,Searchtime)
  1. 定义了一个辅助函数print_state，用于打印状态空间的矩阵形式。
def print_state(State):
    for row in State:
        print(row)
    print()

  1. 主程序中，我定义初始状态空间state0。创建初始状态空间的对象s，并传入初始状态。用变量t 记录当前时间。 调用bfs函数进行搜索，并将结果保存在result和Search变量中。并输出搜索所花费的时间。

    如果存在解，则输出解的步数和搜索次数。如果不存在解，则输出"不存在解"。

if __name__ == "__main__":
    state0 = [[2, 8, 5], [3, 6, 1], [7, 0, 4]]
    s = StateSpace(state0)
    t = time.time()
    result, Search = bfs(s)
    print("用时：" + str(time.time() - t) + "秒")
    if result > 0:
        print("所需步数为 " + str(result) + "\n搜索次数为: " + str(Search))
    else:
        print("不存在解")

3.DFS (深度优先搜索算法)

说明：大框架与BFS算法相同，变化的是队列换成了栈数据结构

  • 在BFS算法解释时做过详细解释，这里简要说明。

dfs函数使用一个栈stack来存储待搜索的状态空间，使用一个集合closed来存储已经访问过的状态空间，避免重复搜索。每次从栈stack中弹出一个状态空间State和对应的步数step，并检查能够向哪个方向移动。

如果当前状态空间State达到目标状态，则找到了正确解。通过回溯父节点的方式，将路径上的每个状态空间添加到path列表中，然后输出每个状态空间的步数和状态。最终，该算法输出解的步数和搜索次数。

def dfs(State):

    stack = []
    step = 0
    closed = set()
    Searchtime = -1
    # 存放初始状态空间和步数
    stack.append((State, step))

    while stack:
        Searchtime += 1
        # 状态弹出栈
        State, step = stack.pop()
        # 如果匹配成功，通过父节点回溯状态空间找到根结点
        if State.Bingo():
            steps = 0
            path = []
            while State.parent is not None:
                path.append(State.state)
                State = State.parent
                steps += 1
            # 记录step并初始化为1
            step_count = 0
            path.append(State.state)
            # 回溯列表中的状态空间是反向添加的，所以需要倒转列表
            path.reverse()
            # 将列表中的数据输出
            for Statetmp in path:
                print("步数:", step_count )
                print_state(Statetmp)
                step_count+=1
            return (steps, Searchtime)

        # 检查能够向哪个方向移动
        possible = State.getDirection()
        for x, y in possible:
            # 与空格交换位置
            newState = State.getMoveState(State.getZeroPos()[0], State.getZeroPos()[1], x, y)
            # 存储父节点
            newState.parent = State
            if newState not in closed:
                closed.add(newState)
                stack.append((newState, step + 1))
    return (-1, Searchtime)

3.A*算法

  • 在StateSpace类中添加getH和getF函数，其中getH()代表估价函数，getF()代表启发式函数。启发式函数设计为曼哈顿距离4中x、y方向分别平方。
    def getH(self):
        h = 0
        for i in range(3):
            for j in range(3):
                if self.state[i][j] != -1:
                    temp = ((0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2))
                    di,dj = temp[self.state[i][j] - 1]
                    sub = (abs(i - di)) + (abs(j - dj))
                    h += sub
        return h

    def getF(self):
        return self.g + self.h
  • 由于需要每一次迭代比较代价，我采用queue库中的PriorityQueue5优先队列来存放代价和状态（以元组形式）。内置的get方法会将其中代价较小的状态弹出，再进行搜索。
from StateSpace import StateSpace
from queue import PriorityQueue
import time
  • 因为有比较的过程，我们需重写类中的__lt__来比较状态代价函数的大小。
    # 比较两个状态空间的启发式函数值
    def __lt__(self, other):
        return self.getF() < other.getF()
  • 与上述两种搜索方式不同的是，我是把代价和状态放在一起作为元组，方便比较代价函数的值。同时在put新状态的时候，把g(x)加1，即走过的路径长了1。
def AStar(State):
    open = PriorityQueue()
    step = 0
    closed = set()
    Searchtime = -1
    # 存放初始状态空间和步数
    open.put((State.getF(), State))

    while open:
        Searchtime += 1
        # 状态弹出队列
        h,State = open.get()
        # 如果匹配成功，通过父节点回溯状态空间找到根结点
        if State.Bingo():
            steps = 0
            path = []
            while State.parent is not None:
                path.append(State.state)
                State = State.parent
                steps += 1
            # 记录step并初始化为1
            step_count = 0
            path.append(State.state)
            # 回溯列表中的状态空间是反向添加的，所以需要倒转列表
            path.reverse()
            # 将列表中的数据输出
            for Statetmp in path:
                print("步数:", step_count )
                print_state(Statetmp)
                step_count+=1
            return (steps, Searchtime)

        # 检查能够向哪个方向移动
        possible = State.getDirection()
        for x, y in possible:
            # 与空格交换位置
            newState = State.getMoveState(State.getZeroPos()[0], State.getZeroPos()[1], x, y)
            # 存储父节点
            newState.parent = State
            if newState not in closed:
                closed.add(newState)
                newState.g = State.g + 1
                open.put((newState.getF(), newState))
    return (-1, Searchtime)

二、结果分析

  • BFS

能够找到最优路径，但搜索次数过多，迭代时间较久，可能是因为队列pop函数是线性时间复杂度。

avatar

  • DFS

找不到最优路径，搜索次数高达17000次，迭代时间较短，说明了栈pop方法的时间复杂度为1。

avatar

  • A*

如果代价函数设计的好的话能够找到最优路径，搜索次数比二者都少，迭代时间短，体现了启发式信息的优越性。

avatar

三、改进与尝试

  • 我在设计 启发式函数 时，发现曼哈顿距离直接套用的话，搜索次数会变多且找不到最优解，我尝试修改成两个差值的平方后，性能有显著提升，可能是因为启发式信息要比路径长度的信息更有优势。

  • 由于BFS迭代时间过长，我把队列改成双端队列，采用leftpop的话，时间复杂度就会减少。

四、总结

总而言之，在解决八数码问题中，不同的搜索算法表现出不同的效率和性能。深度优先搜索具有较低的空间复杂度，但容易陷入局部最优解；广度优先搜索能够找到最短路径，但在搜索空间较大时可能会消耗大量时间和内存。A*搜索算法通过合适的估价函数，综合考虑路径长度和启发式信息，能够高效地找到最优解。

实验结果显示，A搜索算法在解决八数码问题中表现出较好的性能。它能够快速找到最短路径，并且在搜索空间较大时仍能保持较高的效率。然而，选择合适的 启发式函数 对A搜索算法的效果至关重要，一个好的 代价函数 应能够准确预测从当前状态到目标状态的代价。

对你有帮助的话，点个赞吧！

  1. 【Python面向对象编程】第13篇 特殊方法之__hash__ ↩︎

  2. 【一文看懂】python高级函数之 map ↩︎

  3. 【Python学习】计算函数执行时间（五种案例） ↩︎

  4. Python机器学习 - 【公式】欧式距离、曼哈顿距离、闵氏距离和余弦距离 ↩︎

  5. Python 优先级队列PriorityQueue 用法示例 ↩︎

# 算法 # 宽度优先 # python
Logo
腾讯云开发者社区

腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。

更多推荐

cover

基于《2023腾讯云容器和函数计算技术实践精选集》—探索腾讯云TKE的Docker容器、Serverless和微服务优势

avatar 腾讯云开发者社区
cover

一站式加速、安全防护，EdgeOne为金融行业数字化升级保驾护航

avatar 腾讯云开发者社区
cover

全球安全加速一站式底座，EdgeOne以极致玩家体验撬动游戏行业增长

avatar 腾讯云开发者社区