A*算法求解8数码问题python代码实现

以下是使用Python实现A*算法求解8数码问题的代码：

from queue import PriorityQueue

class Puzzle:
    def __init__(self, start, goal):
        self.start = start
        self.goal = goal

    def get_manhattan_distance(self, state):
        distance = 0
        for i in range(3):
            for j in range(3):
                value = state[i][j]
                if value != 0:
                    goal_position = self.get_goal_position(value)
                    distance += abs(i - goal_position[0]) + abs(j - goal_position[1])
        return distance

    def get_goal_position(self, value):
        if value == 0:
            return (2, 2)
        else:
            return divmod(value - 1, 3)

    def get_successors(self, state):
        successors = []
        zero_position = self.get_zero_position(state)
        for move in ["up", "down", "left", "right"]:
            new_state = self.get_new_state(state, zero_position, move)
            if new_state is not None:
                successors.append(new_state)
        return successors

    def get_zero_position(self, state):
        for i in range(3):
            for j in range(3):
                if state[i][j] == 0:
                    return (i, j)

    def get_new_state(self, state, zero_position, move):
        new_state = [row[:] for row in state]
        i, j = zero_position
        if move == "up" and i > 0:
            new_state[i][j], new_state[i - 1][j] = new_state[i - 1][j], new_state[i][j]
            return new_state
        elif move == "down" and i < 2:
            new_state[i][j], new_state[i + 1][j] = new_state[i + 1][j], new_state[i][j]
            return new_state
        elif move == "left" and j > 0:
            new_state[i][j], new_state[i][j - 1] = new_state[i][j - 1], new_state[i][j]
            return new_state
        elif move == "right" and j < 2:
            new_state[i][j], new_state[i][j + 1] = new_state[i][j + 1], new_state[i][j]
            return new_state
        else:
            return None

    def solve(self):
        start_node = Node(self.start, None, None, 0, self.get_manhattan_distance(self.start))
        open_list = PriorityQueue()
        open_list.put(start_node)
        closed_list = set()

        while not open_list.empty():
            current_node = open_list.get()
            if current_node.state == self.goal:
                return self.get_path(current_node)
            closed_list.add(current_node.state)
            for successor in self.get_successors(current_node.state):
                if successor not in closed_list:
                    successor_node = Node(successor, current_node, None, current_node.g + 1, self.get_manhattan_distance(successor))
                    if self.add_to_open_list(successor_node, open_list):
                        open_list.put(successor_node)

        return None

    def add_to_open_list(self, successor_node, open_list):
        for node in open_list.queue:
            if node.state == successor_node.state and node.f <= successor_node.f:
                return False
        return True

    def get_path(self, node):
        path = []
        while node is not None:
            path.append(node.state)
            node = node.parent
        return path[::-1]

class Node:
    def __init__(self, state, parent, move, g, h):
        self.state = state
        self.parent = parent
        self.move = move
        self.g = g
        self.h = h
        self.f = g + h

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

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

puzzle = Puzzle(start_state, goal_state)
path = puzzle.solve()

if path is None:
    print("No solution found.")
else:
    print("Solution found in", len(path) - 1, "moves:")
    for state in path:
        print(state)

在此代码中，`Puzzle`类表示一个8数码问题，`Node`类表示搜索中的一个节点。`get_manhattan_distance`方法计算给定状态的曼哈顿距离，`get_goal_position`方法返回给定数字在目标状态中的位置，`get_successors`方法返回给定状态的所有后继状态，`get_zero_position`方法返回给定状态中数字0的位置，`get_new_state`方法返回给定状态中进行给定移动后的新状态，`solve`方法使用A*算法解决问题，`add_to_open_list`方法用于将节点添加到开放列表中，`get_path`方法返回从起始状态到给定节点状态的路径。在主函数中，我们创建一个`Puzzle`对象并调用`solve`方法来解决问题。如果找到了解决方案，则打印出路径；否则，打印“No solution found.”。