A*算法求解8数码问题 Python实现

8数码问题是经典的搜索问题，也是A*算法的经典应用之一。以下是一个简单的Python实现，具体实现细节可以参考注释。

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

# 定义启发函数，这里选择曼哈顿距离
def heuristic(state):
    distance = 0
    for i in range(9):
        if state[i] == 0:
            continue
        distance += abs((state[i]-1)%3 - i%3) + abs((state[i]-1)//3 - i//3)
    return distance

# 定义搜索函数
def astar(start_state):
    # 定义开放列表和关闭列表
    open_list = [(heuristic(start_state), start_state)]
    closed_list = set()
    # 定义父节点字典，用于回溯路径
    parents = {tuple(start_state): None}
    
    while open_list:
        # 从开放列表中选择最小代价节点
        current_node = min(open_list)
        current_state = current_node[1]
        open_list.remove(current_node)
        closed_list.add(tuple(current_state))
        
        # 判断是否达到目标状态
        if current_state == goal_state:
            path = [current_state]
            while parents[tuple(path[0])] != None:
                path.insert(0, parents[tuple(path[0])])
            return path
        
        # 扩展节点
        zero_index = current_state.index(0)
        for move in [-3, -1, 1, 3]:
            new_index = zero_index + move
            # 判断是否越界
            if new_index < 0 or new_index > 8:
                continue
            # 判断是否跨行或跨列
            if (zero_index // 3 != new_index // 3) != (zero_index % 3 != new_index % 3):
                continue
            new_state = current_state[:]
            new_state[zero_index], new_state[new_index] = new_state[new_index], new_state[zero_index]
            
            # 判断是否已经在关闭列表中
            if tuple(new_state) in closed_list:
                continue
            
            # 更新父节点字典和代价
            parents[tuple(new_state)] = current_state
            cost = heuristic(new_state) + len(parents) - 1
            
            # 加入开放列表
            open_list.append((cost, new_state))
    
    # 没有找到解法
    return None

# 测试
start_state = [2, 8, 3, 1, 6, 4, 7, 0, 5]
path = astar(start_state)
if path == None:
    print('No solution found.')
else:
    print('Solution found with length', len(path)-1)
    for state in path:
        print(state[0], state[1], state[2])
        print(state[3], state[4], state[5])
        print(state[6], state[7], state[8])
        print()