A*算法求解15数码问题的程序

以下是使用A*算法求解15数码问题的Python程序。

import heapq

class Puzzle:
    def __init__(self, state, parent, move, depth, cost):
        self.state = state
        self.parent = parent
        self.move = move
        self.depth = depth
        self.cost = cost
        self.id = self.create_id()

    def create_id(self):
        id = ""
        for i in range(16):
            id += str(self.state[i])
        return id

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

class Solver:
    def __init__(self, initial_state):
        self.initial_state = initial_state
        self.goal_state = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0]
        self.goal_id = self.create_id(self.goal_state)

    def create_id(self, state):
        id = ""
        for i in range(16):
            id += str(state[i])
        return id

    def solve(self):
        open_list = []
        closed_list = {}
        state = self.initial_state
        puzzle = Puzzle(state, None, None, 0, 0)
        heapq.heappush(open_list, puzzle)
        while open_list:
            puzzle = heapq.heappop(open_list)
            closed_list[puzzle.id] = puzzle
            if puzzle.state == self.goal_state:
                return self.get_path(puzzle)
            moves = self.get_moves(puzzle)
            for move in moves:
                new_state = self.get_new_state(puzzle.state, move)
                new_puzzle = Puzzle(new_state, puzzle, move, puzzle.depth+1, self.get_cost(new_state))
                new_id = new_puzzle.id
                if new_id in closed_list:
                    continue
                heapq.heappush(open_list, new_puzzle)
        return None

    def get_moves(self, puzzle):
        moves = []
        blank_index = puzzle.state.index(0)
        if blank_index > 3:
            moves.append(-4)
        if blank_index < 12:
            moves.append(4)
        if blank_index % 4 > 0:
            moves.append(-1)
        if blank_index % 4 < 3:
            moves.append(1)
        return moves

    def get_new_state(self, state, move):
        new_state = state[:]
        blank_index = new_state.index(0)
        swap_index = blank_index + move
        new_state[blank_index], new_state[swap_index] = new_state[swap_index], new_state[blank_index]
        return new_state

    def get_cost(self, state):
        cost = 0
        for i in range(16):
            if state[i] == 0:
                continue
            goal_index = self.goal_state.index(state[i])
            if i != goal_index:
                cost += 1
        return cost

    def get_path(self, puzzle):
        path = []
        while puzzle:
            path.append(puzzle.move)
            puzzle = puzzle.parent
        return path[::-1]

# Example usage
initial_state = [1, 2, 3, 4, 5, 6, 0, 7, 8, 9, 10, 11, 12, 13, 14, 15]
solver = Solver(initial_state)
path = solver.solve()
if path:
    print(path)
else:
    print("No solution found")

在上面的程序中，`Puzzle`类表示一个15数码问题的状态，包含了状态、父状态、移动方向、深度和代价。`Solver`类表示一个15数码问题的求解器，包含了初始状态、目标状态和目标状态的ID。`solve()`方法使用A*算法来求解问题，`get_moves()`方法获取当前状态可以进行的移动方向，`get_new_state()`方法根据移动方向得到新的状态，`get_cost()`方法计算代价，`get_path()`方法获取求解的路径。

在上面的例子中，初始状态是[1, 2, 3, 4, 5, 6, 0, 7, 8, 9, 10, 11, 12, 13, 14, 15]，表示一个已经被打乱的15数码问题，程序会输出一个求解路径。