a*算法实现八数码python

下面是使用Python实现A*算法解决八数码问题的示例代码：

import heapq

def manhattan_distance(state):
    """
    计算当前状态和目标状态之间的曼哈顿距离
    """
    distance = 0
    for i in range(3):
        for j in range(3):
            if state[i][j] != 0:
                x, y = divmod(state[i][j]-1, 3)
                distance += abs(x-i) + abs(y-j)
    return distance

def get_neighbors(state):
    """
    获取当前状态的所有邻居
    """
    neighbors = []
    x, y = next((i, j) for i in range(3) for j in range(3) if state[i][j] == 0)
    for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        new_x, new_y = x + dx, y + dy
        if 0 <= new_x < 3 and 0 <= new_y < 3:
            new_state = [row[:] for row in state]
            new_state[x][y], new_state[new_x][new_y] = new_state[new_x][new_y], new_state[x][y]
            neighbors.append(new_state)
    return neighbors

def a_star(start, goal):
    """
    使用A*算法解决八数码问题
    """
    heap = [(0, start)]
    g = {str(start): 0}
    f = {str(start): manhattan_distance(start)}
    while heap:
        _, current = heapq.heappop(heap)
        if current == goal:
            path = []
            while str(current) in g:
                path.append(current)
                current = g[str(current)]
            path.append(current)
            return path[::-1]
        for neighbor in get_neighbors(current):
            tentative_g = g[str(current)] + 1
            if str(neighbor) not in g or tentative_g < g[str(neighbor)]:
                g[str(neighbor)] = tentative_g
                f[str(neighbor)] = tentative_g + manhattan_distance(neighbor)
                heapq.heappush(heap, (f[str(neighbor)], neighbor))
    return None

start_state = [[2, 8, 3], [1, 6, 4], [7, 0, 5]]
goal_state = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]
path = a_star(start_state, goal_state)
if path:
    for state in path:
        print(state)
else:
    print("No solution found.")

在上述示例代码中，首先定义了一个计算曼哈顿距离的函数manhattan_distance和一个获取当前状态所有邻居的函数get_neighbors。然后定义了A*算法的主函数a_star，其中使用了堆（heapq）来存储待搜索的状态，并使用字典（g和f）来存储已经搜索过的状态的g值和f值。最后，将初始状态和目标状态作为参数调用a_star函数，输出最优路径。