python写出A*算法求解八数码问题

好的，下面是Python实现的A*算法求解八数码问题的代码：

import heapq

class PuzzleNode:
    def __init__(self, state, g, h, parent):
        self.state = state
        self.g = g
        self.h = h
        self.parent = parent

    def f(self):
        return self.g + self.h

    def __lt__(self, other):
        return self.f() < other.f()

def get_blank_pos(state):
    for i in range(3):
        for j in range(3):
            if state[i][j] == 0:
                return (i, j)

def get_manhattan_dist(state):
    dist = 0
    for i in range(3):
        for j in range(3):
            if state[i][j] != 0:
                target_i = (state[i][j] - 1) // 3
                target_j = (state[i][j] - 1) % 3
                dist += abs(i - target_i) + abs(j - target_j)
    return dist

def get_neighbors(state):
    i, j = get_blank_pos(state)
    neighbors = []
    if i > 0:
        new_state = [row[:] for row in state]
        new_state[i][j], new_state[i-1][j] = new_state[i-1][j], new_state[i][j]
        neighbors.append(new_state)
    if i < 2:
        new_state = [row[:] for row in state]
        new_state[i][j], new_state[i+1][j] = new_state[i+1][j], new_state[i][j]
        neighbors.append(new_state)
    if j > 0:
        new_state = [row[:] for row in state]
        new_state[i][j], new_state[i][j-1] = new_state[i][j-1], new_state[i][j]
        neighbors.append(new_state)
    if j < 2:
        new_state = [row[:] for row in state]
        new_state[i][j], new_state[i][j+1] = new_state[i][j+1], new_state[i][j]
        neighbors.append(new_state)
    return neighbors

def a_star(initial_state):
    start_node = PuzzleNode(initial_state, 0, get_manhattan_dist(initial_state), None)
    heap = [start_node]
    visited = set()

    while heap:
        curr_node = heapq.heappop(heap)
        if curr_node.state == [[1, 2, 3], [4, 5, 6], [7, 8, 0]]:
            return curr_node

        visited.add(tuple(map(tuple, curr_node.state)))

        for neighbor_state in get_neighbors(curr_node.state):
            if tuple(map(tuple, neighbor_state)) not in visited:
                neighbor_node = PuzzleNode(neighbor_state, curr_node.g+1, get_manhattan_dist(neighbor_state), curr_node)
                heapq.heappush(heap, neighbor_node)

    return None

def print_solution(node):
    if node is None:
        print("No solution found.")
    else:
        path = []
        while node:
            path.append(node.state)
            node = node.parent
        path.reverse()
        for state in path:
            for row in state:
                print(row)
            print()

initial_state = [[1, 2, 3], [4, 0, 6], [7, 5, 8]]
solution_node = a_star(initial_state)
print_solution(solution_node)

在上面的代码中，`PuzzleNode`类表示八数码问题中的状态节点，包含当前状态、从起始状态到当前状态的代价`g`、从当前状态到目标状态的估价`h`和父节点。`get_blank_pos`函数返回当前状态中空白格子的位置，`get_manhattan_dist`函数计算当前状态到目标状态的曼哈顿距离，`get_neighbors`函数返回当前状态的所有合法后继状态。`a_star`函数实现A*算法，使用堆来维护状态节点的优先级队列。`print_solution`函数输出找到的解路径。在程序中，我们使用目标状态是`[[1, 2, 3], [4, 5, 6], [7, 8, 0]]`来表示八数码问题的目标状态。最后，我们以`[[1, 2, 3], [4, 0, 6], [7, 5, 8]]`作为初始状态调用`a_star`函数来求解八数码问题，并输出解路径。