Python实现A*算法求解滑块谜题运行缓慢问题排查

你的代码能运行但速度慢，核心问题出在数据结构选择和启发函数效率上，以下是具体优化点：

1. 替换线性查找的列表为优先队列（最小堆） #

当前Unchecked用普通列表，每次调用findMatrixWithMinWeight需要遍历整个列表找f值最小的元素，时间复杂度是O(n)，随着搜索空间增大，这一步会越来越慢。

改用Python的heapq模块实现最小堆，堆顶始终是f值最小的状态，取出操作时间复杂度O(logn)，大幅提升效率。

修改示例：

import heapq

# 初始化堆，每个元素是(f值, g值, 状态)
Unchecked = []
heapq.heappush(Unchecked, (initial_f, initial_g, initial_state))

2. 用集合替代列表存储已访问状态 #

Checked是列表，neighbour in Checked的查找操作是O(n)，当已访问状态增多时，这一步会拖慢整个循环。

把Checked改成集合，存储状态的不可变哈希类型（比如元组的元组），查找操作变为O(1)。

修改示例：

Checked = set()
# 处理完当前状态后，将其加入集合
Checked.add(current_state)
# 检查邻居是否已访问
if neighbour_state in Checked:
    continue

3. 优化状态表示，使用不可变哈希类型 #

当前用列表表示矩阵，作为字典键需要转字符串，且列表的比较、哈希效率低。建议把矩阵转换成元组的元组（比如((5,3,4),(6,0,7),(8,2,1))），这种类型不可变且可直接哈希，既能作为字典键，也能直接存进集合，比字符串转换更高效。

4. 替换启发函数为曼哈顿距离 #

你当前用的calculateMisplacedTiles（错位数）是可采纳的启发函数，但曼哈顿距离（每个数字到目标位置的曼哈顿距离之和）的引导性更强，能更有效地剪枝搜索空间，减少不必要的遍历步骤。

曼哈顿距离计算示例：

def calculateManhattanDistance(current, goal_pos):
    distance = 0
    for i in range(3):
        for j in range(3):
            num = current[i][j]
            if num != 0:
                target_i, target_j = goal_pos[num]
                distance += abs(i - target_i) + abs(j - target_j)
    return distance

5. 避免重复处理状态 #

当前逻辑中，同一个状态可能被多次加入Unchecked列表，导致重复处理。用优先队列时，可以允许重复，但处理时先检查该状态是否已经被访问过（在Checked集合里），如果已访问就直接跳过，避免无效计算。

完整优化后的核心代码片段 #

import heapq

initialMatrix = ((5, 3, 4),
                 (6, 0, 7),
                 (8, 2, 1))

goalMatrix = ((1, 2, 3),
              (8, 0, 4),
              (7, 6, 5))

# 提前建立目标位置映射，避免重复计算
goal_pos = {}
for i in range(3):
    for j in range(3):
        if goalMatrix[i][j] != 0:
            goal_pos[goalMatrix[i][j]] = (i,j)

Checked = set()
Unchecked = []
parent = {}
g = {}

# 初始化状态
initial_g = 0
initial_h = calculateManhattanDistance(initialMatrix, goal_pos)
initial_f = initial_g + initial_h
heapq.heappush(Unchecked, (initial_f, initial_g, initialMatrix))
parent[initialMatrix] = None
g[initialMatrix] = initial_g

step = 0

while Unchecked:
    current_f, current_g, current = heapq.heappop(Unchecked)
    step += 1

    if current == goalMatrix:
        break

    # 跳过已处理过的状态
    if current in Checked:
        continue
    Checked.add(current)

    emptyPos = findEmpty(current)  # 需适配元组类型的状态
    neighbours = []
    # 生成邻居状态（返回元组类型）
    if emptyPos[0] > 0:
        neighbours.append(UpRule(current, emptyPos))
    if emptyPos[0] < 2:
        neighbours.append(DownRule(current, emptyPos))
    if emptyPos[1] > 0:
        neighbours.append(LeftRule(current, emptyPos))
    if emptyPos[1] < 2:
        neighbours.append(RightRule(current, emptyPos))

    for neighbour in neighbours:
        tentative_g = current_g + 1
        # 如果已访问且新g值不更优，跳过
        if neighbour in Checked and tentative_g >= g.get(neighbour, float('inf')):
            continue
        # 更新更优路径
        if tentative_g < g.get(neighbour, float('inf')):
            parent[neighbour] = current
            g[neighbour] = tentative_g
            neighbour_h = calculateManhattanDistance(neighbour, goal_pos)
            neighbour_f = tentative_g + neighbour_h
            heapq.heappush(Unchecked, (neighbour_f, tentative_g, neighbour))

额外说明 #

• 你的初始案例确实有一定复杂度，但主要性能瓶颈还是代码实现中的数据结构和启发函数问题，优化后步骤数和执行时间会大幅降低。
• 辅助函数（findEmpty、UpRule等）需要适配元组类型的状态，比如复制元组时可以用list(map(list, current))转成列表修改，再转回元组。

内容的提问来源于stack exchange，提问作者Fertiwer