八数码问题a*算法python

八数码问题是一种经典的搜索问题，可以使用 A* 算法来求解。A* 算法是一种启发式搜索算法，可以在保证搜索最优解的同时尽可能减少搜索的时间和空间成本。下面是一个使用 Python 实现的八数码问题 A* 算法的示例代码：

from queue import PriorityQueue

class Puzzle:
    def __init__(self, board):
        self.board = board
        self.moves = []
        self.cost = 0

    def get_distance(self, target_board):
        distance = 0
        for i in range(3):
            for j in range(3):
                value = self.board[i][j]
                if value != 0 and value != target_board[i][j]:
                    target_i, target_j = divmod(value - 1, 3)
                    distance += abs(i - target_i) + abs(j - target_j)
        return distance

    def get_next_puzzles(self):
        next_puzzles = []
        i, j = next((i, j) for i in range(3) for j in range(3) if self.board[i][j] == 0)
        for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            if 0 <= i + di < 3 and 0 <= j + dj < 3:
                next_board = [row[:] for row in self.board]
                next_board[i][j], next_board[i + di][j + dj] = next_board[i + di][j + dj], next_board[i][j]
                next_puzzle = Puzzle(next_board)
                next_puzzle.moves = self.moves + [(i + di, j + dj)]
                next_puzzle.cost = len(next_puzzle.moves) + next_puzzle.get_distance(target_board)
                next_puzzles.append(next_puzzle)
        return next_puzzles

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

def solve_puzzle(start_board, target_board):
    start_puzzle = Puzzle(start_board)
    start_puzzle.cost = start_puzzle.get_distance(target_board)
    queue = PriorityQueue()
    queue.put(start_puzzle)
    visited = set()
    while not queue.empty():
        puzzle = queue.get()
        if puzzle.board == target_board:
            return puzzle.moves
        for next_puzzle in puzzle.get_next_puzzles():
            if tuple(map(tuple, next_puzzle.board)) not in visited:
                visited.add(tuple(map(tuple, next_puzzle.board)))
                queue.put(next_puzzle)
    return None

start_board = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
target_board = [[1, 2, 3], [4, 5, 6], [7, 0, 8]]
moves = solve_puzzle(start_board, target_board)
if moves:
    for move in moves:
        print(move)
else:
    print("No solution found.")

在这个示例代码中，我们首先定义了一个 `Puzzle` 类来表示每个状态，其中包含了当前的棋盘状态以及移动序列和代价（即移动序列的长度加上当前状态到目标状态的估计距离）。然后我们使用 A* 算法来搜索最优解，其中使用了一个优先队列来进行状态的扩展，以保证每次扩展的状态都是代价最小的。最后，我们输出找到的移动序列，或者在无解的情况下输出提示信息。