为8-Puzzle的BFS算法添加已访问状态记录的实现困境

问题分析 #

你当前的BFS实现没有记录已访问的状态，导致大量重复状态被加入队列，严重影响算法效率。需要新增一个已访问状态集合，过滤掉已经处理过的状态，只扩展未访问的节点。

修改方案及代码实现 #

首先补充Node类的定义（原代码中未给出），然后新增visited集合，在生成子节点时检查状态是否已访问，仅将未访问的状态加入队列和已访问集合：

import copy

# 补充Node类定义，用于存储状态和父节点
class Node:
    def __init__(self, state, parent=None):
        self.state = state
        self.parent = parent

def bfs(puzzle):
    solution = []
    # 目标状态
    goal = [0,1,2,3,4,5,6,7,8]
    # 每个位置（索引）对应的可移动位置
    possible_move = [[1,3],[0,2,4],[1,5],[0,4,6],[1,3,5,7],[2,4,8],[3,7],[4,6,8],[5,7]]
    
    # 初始化队列和已访问集合（用元组存储状态，因为列表不可哈希）
    start_node = Node(puzzle)
    queue = [start_node]
    visited = set()
    # 将初始状态转成元组加入已访问集合
    visited.add(tuple(start_node.state))
    
    move = 0
    while queue:
        # 弹出队列头部节点（BFS核心：先进先出）
        current_node = queue.pop(0)
        print('\n当前游戏状态:\n ' + str(current_node.state))
        
        # 检查是否到达目标状态
        if current_node.state == goal:
            break
        
        # 找到空白块（8）的索引
        blank_idx = current_node.state.index(8)
        print('空白块索引: ' + str(blank_idx))
        possible_pos = possible_move[blank_idx]
        print('可移动位置: ' + str(possible_pos))
        
        # 遍历所有可移动位置，生成子节点
        for pos in possible_pos:
            # 复制当前状态，避免修改原状态
            new_state = current_node.state[:]
            # 交换空白块和目标位置
            new_state[blank_idx], new_state[pos] = new_state[pos], new_state[blank_idx]
            print('生成子节点状态: ' + str(new_state))
            
            # 将新状态转成元组，检查是否已访问
            new_state_tuple = tuple(new_state)
            if new_state_tuple not in visited:
                # 标记为已访问
                visited.add(new_state_tuple)
                # 创建子节点并加入队列
                queue.append(Node(new_state, current_node))
    
    # 回溯路径，生成移动步骤
    while current_node.parent:
        solution.append(current_node.state.index(8))
        current_node = current_node.parent
        move += 1
    
    print('总移动步数: ' + str(move))
    solution.reverse()
    print('移动步骤列表: ' + str(solution))
    
    return solution

关键修改说明 #

1. Node类补充：明确节点结构，存储当前状态和父节点，用于后续回溯路径。
2. visited集合：使用元组（可哈希类型）存储已访问状态，因为列表是可变类型，无法存入集合。
3. 状态检查逻辑：生成子节点后，先将状态转成元组，检查是否在visited中，只有未访问的状态才会被加入队列和标记为已访问，避免重复处理。
4. 循环条件优化：用while queue替代原代码的loop标志，逻辑更简洁。

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