代价树的深度优先搜索算法解决八位码问题 输出每一步的状态 python代码有注释

以下是代价树的深度优先搜索算法解决八位码问题的 Python 代码，每一步都会输出状态：

# 定义八位码问题的初始状态和目标状态
start_state = [3, 1, 2, 0, 4, 5, 6, 7, 8]
goal_state = [0, 1, 2, 3, 4, 5, 6, 7, 8]

# 定义状态节点类
class StateNode:
    def __init__(self, state, parent=None):
        self.state = state
        self.parent = parent

    # 获取空格位置
    def get_blank_pos(self):
        return self.state.index(0)

    # 获取状态的所有可能的子状态
    def get_child_states(self):
        blank_pos = self.get_blank_pos()
        child_states = []

        # 交换空格和上方的数字
        if blank_pos not in [0, 1, 2]:
            child_state = self.state.copy()
            child_state[blank_pos], child_state[blank_pos - 3] = child_state[blank_pos - 3], child_state[blank_pos]
            child_states.append(StateNode(child_state, self))

        # 交换空格和下方的数字
        if blank_pos not in [6, 7, 8]:
            child_state = self.state.copy()
            child_state[blank_pos], child_state[blank_pos + 3] = child_state[blank_pos + 3], child_state[blank_pos]
            child_states.append(StateNode(child_state, self))

        # 交换空格和左边的数字
        if blank_pos not in [0, 3, 6]:
            child_state = self.state.copy()
            child_state[blank_pos], child_state[blank_pos - 1] = child_state[blank_pos - 1], child_state[blank_pos]
            child_states.append(StateNode(child_state, self))

        # 交换空格和右边的数字
        if blank_pos not in [2, 5, 8]:
            child_state = self.state.copy()
            child_state[blank_pos], child_state[blank_pos + 1] = child_state[blank_pos + 1], child_state[blank_pos]
            child_states.append(StateNode(child_state, self))

        return child_states

    # 判断状态是否为目标状态
    def is_goal_state(self):
        return self.state == goal_state

# 定义深度优先搜索函数
def depth_first_search(start_node):
    # 初始化已访问的节点集合
    visited = set()
    # 初始化待访问的节点栈
    stack = [start_node]

    while stack:
        # 取出栈顶节点
        node = stack.pop()

        # 如果节点为目标状态，则返回
        if node.is_goal_state():
            return node

        # 将节点标记为已访问
        visited.add(tuple(node.state))

        # 获取所有可能的子状态
        child_states = node.get_child_states()

        # 将未访问的子状态入栈
        for child_state in child_states:
            if tuple(child_state.state) not in visited:
                stack.append(child_state)

    # 如果没有找到目标状态，则返回 None
    return None

# 测试深度优先搜索函数
start_node = StateNode(start_state)
goal_node = depth_first_search(start_node)

# 输出每一步的状态
path = []
while goal_node:
    path.append(goal_node.state)
    goal_node = goal_node.parent

for state in reversed(path):
    print(state)

注意，这个算法并不保证找到最优解，因为它只会沿着一条路径一直深入到底，直到找到目标状态或者无法继续搜索为止。如果有多条路径可以到达目标状态，它可能会找到其中的一条，但不一定是最短的路径。