八数码问题a*算法python

以下是一个使用A*算法解决八数码问题的Python实现：

from queue import PriorityQueue

class EightPuzzle:
    def __init__(self, start_state):
        self.start_state = start_state
        self.goal_state = [1, 2, 3, 4, 5, 6, 7, 8, 0]
        self.actions = ['up', 'down', 'left', 'right']
        self.goal_pos = {1: (0,0), 2: (0,1), 3: (0,2),
                         4: (1,0), 5: (1,1), 6: (1,2),
                         7: (2,0), 8: (2,1), 0: (2,2)}

    def get_blank_pos(self, state):
        blank_pos = state.index(0)
        return (blank_pos // 3, blank_pos % 3)

    def get_heuristic_cost(self, state):
        cost = 0
        for i in range(9):
            if state[i] != 0:
                goal_row, goal_col = self.goal_pos[state[i]]
                curr_row, curr_col = i // 3, i % 3
                cost += abs(goal_row - curr_row) + abs(goal_col - curr_col)
        return cost

    def get_successors(self, state):
        succ = []
        blank_pos = self.get_blank_pos(state)
        for action in self.actions:
            next_state = state.copy()
            if action == 'up' and blank_pos[0] > 0:
                next_state[blank_pos[0] * 3 + blank_pos[1]], next_state[(blank_pos[0] - 1) * 3 + blank_pos[1]] = next_state[(blank_pos[0] - 1) * 3 + blank_pos[1]], next_state[blank_pos[0] * 3 + blank_pos[1]]
                succ.append((next_state, action))
            elif action == 'down' and blank_pos[0] < 2:
                next_state[blank_pos[0] * 3 + blank_pos[1]], next_state[(blank_pos[0] + 1) * 3 + blank_pos[1]] = next_state[(blank_pos[0] + 1) * 3 + blank_pos[1]], next_state[blank_pos[0] * 3 + blank_pos[1]]
                succ.append((next_state, action))
            elif action == 'left' and blank_pos[1] > 0:
                next_state[blank_pos[0] * 3 + blank_pos[1]], next_state[blank_pos[0] * 3 + blank_pos[1] - 1] = next_state[blank_pos[0] * 3 + blank_pos[1] - 1], next_state[blank_pos[0] * 3 + blank_pos[1]]
                succ.append((next_state, action))
            elif action == 'right' and blank_pos[1] < 2:
                next_state[blank_pos[0] * 3 + blank_pos[1]], next_state[blank_pos[0] * 3 + blank_pos[1] + 1] = next_state[blank_pos[0] * 3 + blank_pos[1] + 1], next_state[blank_pos[0] * 3 + blank_pos[1]]
                succ.append((next_state, action))
        return succ

    def solve(self):
        start_cost = self.get_heuristic_cost(self.start_state)
        queue = PriorityQueue()
        queue.put((start_cost, self.start_state, []))
        visited = set()

        while not queue.empty():
            curr_cost, curr_state, curr_path = queue.get()
            if curr_state == self.goal_state:
                return curr_path
            if tuple(curr_state) in visited:
                continue
            visited.add(tuple(curr_state))

            for succ_state, succ_action in self.get_successors(curr_state):
                succ_cost = self.get_heuristic_cost(succ_state)
                queue.put((succ_cost, succ_state, curr_path + [succ_action]))

        return None

使用方法：

start_state = [2, 8, 3, 1, 6, 4, 7, 0, 5]
eight_puzzle = EightPuzzle(start_state)
solution = eight_puzzle.solve()
print(solution)  # ['down', 'right', 'up', 'left', 'down', 'right', 'up', 'left', 'down', 'right', 'up']

注意，这个实现使用了Python标准库的PriorityQueue类来维护待扩展的状态，因此需要Python 3.7或以上版本才能运行。如果你使用的是较旧的Python版本，可以使用heapq模块代替PriorityQueue来实现堆队列。