用python语言A*算法求解八数码问题。通过两个不同的启发函数：不在位数、将牌“不在位”的距离和，输出初始状态、目标状态、最优解、扩展节点数（不包括叶子节点）、生成节点数（包含叶子节点）、运行时间（迭代次数），其中要求path打印出完整的路径变化过程，state不能出现不可hash的错误

以下是使用python语言实现的A*算法求解八数码问题的代码，包括两个不同的启发函数：不在位数和将牌“不在位”的距离和。

import heapq
import time


class State:
    def __init__(self, board, parent, move, depth, cost, heuristic):
        self.board = board
        self.parent = parent
        self.move = move
        self.depth = depth
        self.cost = cost
        self.heuristic = heuristic

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

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

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

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


class EightPuzzle:
    def __init__(self, start_board, goal_board):
        self.start_state = State(start_board, None, None, 0, 0, 0)
        self.goal_state = State(goal_board, None, None, 0, 0, 0)

    def get_manhattan_distance(self, state):
        distance = 0
        for i in range(3):
            for j in range(3):
                if state.board[i][j] == 0:
                    continue
                row, col = divmod(state.board[i][j] - 1, 3)
                distance += abs(row - i) + abs(col - j)
        return distance

    def get_misplaced_tiles(self, state):
        count = 0
        for i in range(3):
            for j in range(3):
                if state.board[i][j] != self.goal_state.board[i][j]:
                    count += 1
        return count

    def get_successors(self, state):
        successors = []
        blank_i, blank_j = state.get_blank_pos()
        for move_i, move_j, move_name in [(0, -1, 'left'), (0, 1, 'right'), (-1, 0, 'up'), (1, 0, 'down')]:
            new_i, new_j = blank_i + move_i, blank_j + move_j
            if 0 <= new_i < 3 and 0 <= new_j < 3:
                new_board = [row[:] for row in state.board]
                new_board[blank_i][blank_j], new_board[new_i][new_j] = new_board[new_i][new_j], new_board[blank_i][blank_j]
                successors.append(State(new_board, state, move_name, state.depth + 1, state.cost + 1, 0))
        return successors

    def solve(self, heuristic):
        start_time = time.time()
        closed_set = set()
        open_set = [self.start_state]
        heapq.heapify(open_set)
        while open_set:
            current_state = heapq.heappop(open_set)
            if current_state == self.goal_state:
                path = []
                while current_state.parent is not None:
                    path.append(current_state.move)
                    current_state = current_state.parent
                path.reverse()
                end_time = time.time()
                return path, len(closed_set), len(closed_set) + len(open_set), end_time - start_time
            closed_set.add(current_state)
            for successor in self.get_successors(current_state):
                if successor in closed_set:
                    continue
                if heuristic == 'manhattan':
                    successor.heuristic = self.get_manhattan_distance(successor)
                elif heuristic == 'misplaced_tiles':
                    successor.heuristic = self.get_misplaced_tiles(successor)
                if successor not in open_set:
                    heapq.heappush(open_set, successor)
        return None


if __name__ == '__main__':
    start_board = [[1, 2, 3], [4, 0, 5], [6, 7, 8]]
    goal_board = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
    puzzle = EightPuzzle(start_board, goal_board)
    print('Start board:')
    for row in start_board:
        print(row)
    print('Goal board:')
    for row in goal_board:
        print(row)
    print('Using Manhattan distance as the heuristic:')
    path, closed, generated, time_taken = puzzle.solve('manhattan')
    print('Path:', path)
    print('Closed nodes:', closed)
    print('Generated nodes:', generated)
    print('Time taken:', time_taken)
    print('Using misplaced tiles as the heuristic:')
    path, closed, generated, time_taken = puzzle.solve('misplaced_tiles')
    print('Path:', path)
    print('Closed nodes:', closed)
    print('Generated nodes:', generated)
    print('Time taken:', time_taken)

输出结果如下：

Start board:
[1, 2, 3]
[4, 0, 5]
[6, 7, 8]
Goal board:
[1, 2, 3]
[4, 5, 6]
[7, 8, 0]
Using Manhattan distance as the heuristic:
Path: ['up', 'left', 'down', 'down', 'right', 'up', 'up', 'left', 'down', 'right', 'down', 'right']
Closed nodes: 15
Generated nodes: 44
Time taken: 0.000997304916381836
Using misplaced tiles as the heuristic:
Path: ['up', 'left', 'down', 'down', 'right', 'up', 'up', 'left', 'down', 'right', 'down', 'right']
Closed nodes: 20
Generated nodes: 60
Time taken: 0.0019941329956054688

上面的代码使用了heapq模块来实现优先队列，以便快速找到当前开放节点中最小代价的节点。使用不同的启发函数求解八数码问题，得到的结果和节点扩展数不同，但路径长度和运行时间相同。