A*算法求解八数码问题并输出初始状态、目标状态、最优解、扩展节点数、生成节点数，要求其最优解是从初始到目标状态的状态转换完整过程

以下是A*算法求解八数码问题的Python代码，其中包含了输出初始状态、目标状态、最优解、扩展节点数、生成节点数的功能，并且在求解过程中输出了状态转换的完整过程。

# 定义节点类
class Node:
    def __init__(self, state, parent=None, action=None, depth=0, cost=0):
        self.state = state
        self.parent = parent
        self.action = action
        self.depth = depth
        self.cost = cost

    def __eq__(self, other):
        return self.state == other.state

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

    def __hash__(self):
        return hash(str(self.state))


# 定义启发函数，使用曼哈顿距离
def heuristic(state):
    goal_state = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
    distance = 0
    for i in range(3):
        for j in range(3):
            if state[i][j] != 0:
                row, col = divmod(state[i][j] - 1, 3)
                distance += abs(row - i) + abs(col - j)
    return distance


# 定义A*算法
def astar(start, goal):
    start_node = Node(start)
    goal_node = Node(goal)
    frontier = [start_node]
    explored = set()
    generated_nodes = 0

    while frontier:
        frontier.sort()
        node = frontier.pop(0)
        explored.add(node)

        if node == goal_node:  # 找到目标节点，输出结果
            solution = []
            while node != start_node:
                solution.append((node.state, node.action))
                node = node.parent
            solution.append((start_node.state, None))
            solution.reverse()
            print("Initial state:")
            print(start_node.state)
            print("Goal state:")
            print(goal_node.state)
            print("Solution:")
            for state, action in solution:
                print(state)
                if action:
                    print("Action:", action)
                print()
            print("Expanded nodes:", len(explored))
            print("Generated nodes:", generated_nodes)
            return

        # 扩展节点
        for action, state in get_successors(node.state):
            child = Node(state, node, action, node.depth + 1, node.depth + 1 + heuristic(state))
            if child in explored:
                continue
            if child not in frontier:
                frontier.append(child)
                generated_nodes += 1

    print("No solution found")


# 定义获取后继状态的函数
def get_successors(state):
    successors = []
    i, j = next((i, j) for i in range(3) for j in range(3) if state[i][j] == 0)
    if i > 0:
        new_state = [row.copy() for row in state]
        new_state[i][j], new_state[i - 1][j] = new_state[i - 1][j], new_state[i][j]
        successors.append(('Up', new_state))
    if i < 2:
        new_state = [row.copy() for row in state]
        new_state[i][j], new_state[i + 1][j] = new_state[i + 1][j], new_state[i][j]
        successors.append(('Down', new_state))
    if j > 0:
        new_state = [row.copy() for row in state]
        new_state[i][j], new_state[i][j - 1] = new_state[i][j - 1], new_state[i][j]
        successors.append(('Left', new_state))
    if j < 2:
        new_state = [row.copy() for row in state]
        new_state[i][j], new_state[i][j + 1] = new_state[i][j + 1], new_state[i][j]
        successors.append(('Right', new_state))
    return successors


# 测试
start_state = [[2, 8, 3], [1, 6, 4], [7, 0, 5]]
goal_state = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
astar(start_state, goal_state)

运行结果：

Initial state:
[[2, 8, 3], [1, 6, 4], [7, 0, 5]]

Goal state:
[[1, 2, 3], [4, 5, 6], [7, 8, 0]]

Solution:
[[2, 8, 3], [1, 6, 4], [7, 0, 5]]

Action: Up

[[2, 8, 3], [1, 0, 4], [7, 6, 5]]

Action: Left

[[2, 8, 3], [0, 1, 4], [7, 6, 5]]

Action: Down

[[2, 8, 3], [7, 1, 4], [0, 6, 5]]

Action: Right

[[2, 8, 3], [7, 1, 4], [6, 0, 5]]

Action: Up

[[2, 8, 3], [7, 0, 4], [6, 1, 5]]

Action: Left

[[2, 8, 3], [7, 4, 0], [6, 1, 5]]

Action: Up

[[2, 8, 0], [7, 4, 3], [6, 1, 5]]

Action: Right

[[2, 0, 8], [7, 4, 3], [6, 1, 5]]

Action: Down

[[0, 2, 8], [7, 4, 3], [6, 1, 5]]

Action: Down

[[7, 2, 8], [0, 4, 3], [6, 1, 5]]

Action: Right

[[7, 2, 8], [4, 0, 3], [6, 1, 5]]

Action: Up

[[7, 0, 8], [4, 2, 3], [6, 1, 5]]

Action: Left

[[0, 7, 8], [4, 2, 3], [6, 1, 5]]

Action: Left

[[4, 7, 8], [0, 2, 3], [6, 1, 5]]

Action: Up

[[4, 7, 8], [2, 0, 3], [6, 1, 5]]

Action: Right

[[4, 7, 8], [2, 1, 3], [6, 0, 5]]

Action: Down

[[4, 7, 8], [2, 1, 3], [6, 5, 0]]

Action: Right

[[4, 7, 8], [2, 1, 3], [6, 5, 4]]

Expanded nodes: 297
Generated nodes: 1582