A*算法求解八数码难题(python实现)

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

import heapq

# 定义状态类
class PuzzleState:
    def __init__(self, board, goal, moves=0):
        self.board = board
        self.goal = goal
        self.moves = moves

    # 计算当前状态的哈曼顿距离
    def manhattan_distance(self):
        distance = 0
        for i in range(3):
            for j in range(3):
                if self.board[i][j] == 0:
                    continue
                distance += abs(i - (self.board[i][j] - 1) // 3) + abs(j - (self.board[i][j] - 1) % 3)
        return distance

    # 定义状态比较函数，用于堆排序
    def __lt__(self, other):
        return self.moves + self.manhattan_distance() < other.moves + other.manhattan_distance()

    # 判断当前状态是否为目标状态
    def is_goal(self):
        return self.board == self.goal

    # 生成当前状态的所有合法后继状态
    def generate_successors(self):
        successors = []
        i, j = next((i, j) for i in range(3) for j in range(3) if self.board[i][j] == 0)
        for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
            if 0 <= x < 3 and 0 <= y < 3:
                successor = [row[:] for row in self.board]
                successor[i][j], successor[x][y] = successor[x][y], successor[i][j]
                successors.append(PuzzleState(successor, self.goal, self.moves + 1))
        return successors

# 定义A*搜索函数
def solve_puzzle(start, goal):
    frontier = [start]
    heapq.heapify(frontier)
    explored = set()
    while frontier:
        state = heapq.heappop(frontier)
        if state.is_goal():
            return state.moves, explored
        explored.add(str(state.board))
        for successor in state.generate_successors():
            if str(successor.board) not in explored:
                heapq.heappush(frontier, successor)
    return None

# 测试代码
start = [[2, 8, 3], [1, 6, 4], [7, 0, 5]]
goal = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]
start_state = PuzzleState(start, goal)
moves, explored = solve_puzzle(start_state, goal)
print("Minimum number of moves:", moves)
print("Number of explored states:", len(explored))

其中，`PuzzleState`类表示八数码难题的一个状态，包含当前棋盘状态`board`、目标状态`goal`和已经移动的步数`moves`。`manhattan_distance`方法计算当前状态和目标状态之间的哈曼顿距离，用于A*算法的估价函数。`__lt__`方法定义状态比较函数，用于堆排序。`is_goal`方法判断当前状态是否为目标状态。`generate_successors`方法生成当前状态的所有合法后继状态。`solve_puzzle`函数实现A*算法的搜索过程，返回最少移动步数和搜索过的状态数量。测试代码给出了一个初始状态和目标状态，可以根据需要修改。