代价树的宽度优先搜索解决八位码问题 输出每一步过程 python代码有注释

以下是代价树的宽度优先搜索解决八位码问题并输出每一步过程的Python代码，带有注释说明：

# 代价树的宽度优先搜索解决八位码问题并输出每一步过程

from queue import Queue

# 定义初始状态和目标状态
initial_state = [2, 8, 3, 1, 6, 4, 7, 0, 5]
goal_state = [1, 2, 3, 8, 0, 4, 7, 6, 5]

# 定义每个状态的代价
cost = {tuple(initial_state): 0}

# 定义转移操作
moves = {
    0: [1, 3],
    1: [0, 2, 4],
    2: [1, 5],
    3: [0, 4, 6],
    4: [1, 3, 5, 7],
    5: [2, 4, 8],
    6: [3, 7],
    7: [4, 6, 8],
    8: [5, 7]
}

# 定义转移操作的文字描述
move_names = {
    0: 'Up',
    1: 'Right',
    2: 'Down',
    3: 'Left'
}

# 定义搜索函数
def bfs(initial_state, goal_state):
    # 初始化队列和访问状态
    q = Queue()
    q.put(initial_state)
    visited = set()
    visited.add(tuple(initial_state))
    
    # 开始搜索
    while not q.empty():
        # 取出队列中的下一个状态
        current_state = q.get()
        
        # 输出当前状态
        print('Current state:', current_state)
        
        # 如果当前状态是目标状态，则输出路径并结束搜索
        if current_state == goal_state:
            path = []
            while current_state != initial_state:
                for move, next_state in moves.items():
                    if tuple(current_state) in next_state:
                        path.append(move_names[move])
                        current_state = next_state[move]
                        break
            path.reverse()
            print('Path:', path)
            return
        
        # 对当前状态进行转移操作
        for move, next_state in moves.items():
            new_state = current_state[:]
            if move in next_state:
                index = new_state.index(0)
                if move == 0:
                    new_index = index - 3
                elif move == 1:
                    new_index = index + 1
                elif move == 2:
                    new_index = index + 3
                else:
                    new_index = index - 1
                new_state[index], new_state[new_index] = new_state[new_index], new_state[index]
                # 如果新状态没有被访问过，则将其加入队列和访问状态，并计算代价
                if tuple(new_state) not in visited:
                    q.put(new_state)
                    visited.add(tuple(new_state))
                    cost[tuple(new_state)] = cost[tuple(current_state)] + 1
        
        # 输出下一步的候选状态
        print('Next states:', [move_names[move] for move, next_state in moves.items() if move in moves and tuple(current_state) in next_state])
        print('---------------------')

# 调用搜索函数
bfs(initial_state, goal_state)

在代码中，我们在每次取出队列中的下一个状态后，输出当前状态的内容。在搜索结束后，我们输出了路径，并使用了Python内置的`reverse()`方法来将路径反转，以便输出正确的顺序。在每次对当前状态进行转移操作后，我们输出下一步的候选状态的内容，以方便理解搜索过程。