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

以下是代价树的宽度优先搜索解决八位码问题并输出每一步状态的Python代码：

from queue import Queue

# 判断当前状态是否为目标状态
def is_goal(state):
    return state == [1, 2, 3, 8, 0, 4, 7, 6, 5]

# 交换数组中两个元素的位置
def swap(state, i, j):
    state[i], state[j] = state[j], state[i]

# 获取当前状态的所有可能子状态
def get_next_states(state):
    next_states = []
    zero_index = state.index(0) # 找到空格的位置
    if zero_index == 0:
        next_states.append(state[:zero_index] + [state[1], state[0]] + state[2:])
        next_states.append(state[:zero_index] + [state[3], state[0], state[2]] + state[4:])
    elif zero_index == 1:
        next_states.append(state[:zero_index-1] + [state[1], state[0], state[2]] + state[3:])
        next_states.append(state[:zero_index] + [state[2], state[1], state[0]] + state[3:])
        next_states.append(state[:zero_index] + [state[4], state[1], state[2]] + state[5:])
    elif zero_index == 2:
        next_states.append(state[:zero_index-2] + [state[2], state[0], state[1], state[3]] + state[4:])
        next_states.append(state[:zero_index-1] + [state[1], state[0], state[2], state[3]] + state[4:])
        next_states.append(state[:zero_index] + [state[5], state[1], state[2], state[3], state[4], state[6], state[7], state[8]])
    elif zero_index == 3:
        next_states.append(state[:zero_index-2] + [state[3], state[0], state[2], state[1]] + state[4:])
        next_states.append(state[:zero_index-1] + [state[0], state[4], state[2], state[1]] + state[5:])
        next_states.append(state[:zero_index] + [state[6], state[4], state[2], state[1], state[0], state[5], state[7], state[8]])
    elif zero_index == 4:
        next_states.append(state[:zero_index-3] + [state[4], state[1], state[2], state[0]] + state[5:])
        next_states.append(state[:zero_index-2] + [state[0], state[4], state[2], state[3]] + state[6:])
        next_states.append(state[:zero_index-1] + [state[8], state[4], state[2], state[1], state[5], state[0], state[7], state[3]])
        next_states.append(state[:zero_index] + [state[1], state[4], state[2], state[3], state[0], state[5], state[7], state[8]])
    elif zero_index == 5:
        next_states.append(state[:zero_index-3] + [state[4], state[0], state[2], state[3]] + state[6:])
        next_states.append(state[:zero_index-2] + [state[4], state[1], state[0], state[3]] + state[7:])
        next_states.append(state[:zero_index-1] + [state[4], state[1], state[2], state[6]] + state[8:])
    elif zero_index == 6:
        next_states.append(state[:zero_index-3] + [state[4], state[1], state[2], state[3], state[6], state[5]] + state[7:])
        next_states.append(state[:zero_index-2] + [state[4], state[1], state[0], state[3], state[6], state[8]] + state[7:])
        next_states.append(state[:zero_index-1] + [state[4], state[1], state[2], state[7], state[6], state[8]] + state[5:])
    elif zero_index == 7:
        next_states.append(state[:zero_index-3] + [state[4], state[1], state[2], state[3], state[7], state[8]] + state[6:])
        next_states.append(state[:zero_index-2] + [state[4], state[1], state[2], state[0], state[7], state[6]] + state[8:])
        next_states.append(state[:zero_index-1] + [state[4], state[1], state[2], state[6], state[7], state[5], state[3], state[8]] + state[0:])
    elif zero_index == 8:
        next_states.append(state[:zero_index-3] + [state[4], state[1], state[2], state[3], state[8], state[7]] + state[5:])
        next_states.append(state[:zero_index-2] + [state[4], state[1], state[2], state[5], state[8], state[6]] + state[7:])
    return next_states

# 宽度优先搜索算法
def bfs(start_state):
    visited = set() # 用于记录已访问过的状态
    q = Queue() # 存放待访问的状态的队列
    q.put((start_state, [])) # 将起始状态加入队列
    while not q.empty():
        cur_state, path = q.get() # 取出队列中的第一个状态
        if is_goal(cur_state): # 判断是否为目标状态
            return path
        visited.add(tuple(cur_state))
        for next_state in get_next_states(cur_state): # 获取当前状态的所有可能子状态
            if tuple(next_state) not in visited:
                next_path = path + [next_state] # 记录路径
                q.put((next_state, next_path)) # 将新状态加入队列
    return None

# 测试
start_state = [2, 8, 3, 1, 6, 4, 7, 0, 5]
path = bfs(start_state)
for state in path:
    print(state)
    print('---')

其中，`start_state`表示八位码的初始状态，`path`表示到达目标状态的路径。函数`is_goal`用于判断当前状态是否为目标状态，函数`swap`用于交换数组中两个元素的位置，函数`get_next_states`用于获取当前状态的所有可能子状态，函数`bfs`是宽度优先搜索算法的实现。