Python实现求解15-Puzzle的IDA*算法 测试3x3拼图触发无限循环

1. 环路检测逻辑完全失效（无限循环的核心原因） #

代码中递归环节的if n not in path判断完全起不到防环路的作用，根源是Node类没有重写相等判断逻辑：

• Python默认对自定义类的相等判断是基于对象内存地址的身份对比，而非实际存储的状态值
• 哪怕两个Node实例存储的拼图状态完全一致，只要是不同时刻生成的独立对象，就会被判定为不相等
• 这就导致“从当前位置移出去再移回来”的循环操作永远不会被拦截，代码会在相邻的几个状态之间反复递归跳转，形成无限循环

2. 环路检测效率缺陷 #

就算补上Node的相等判断，现有if n not in path的写法是对路径列表做线性遍历，路径长度稍大后每次判断都要遍历全量节点，耗时会线性增长，容易让人误以为程序卡死。

3. 测试代码存在语法遗漏 #

贴出的测试调用代码中，np.array的参数缺少外层方括号，实际运行时会直接触发参数格式错误：

# 错误写法
initial_state = np.array([8 7 3],[4 1 2],[0 5 6])
# 正确写法
initial_state = np.array([[8,7,3],[4,1,2],[0,5,6]])

4. 怀疑的g值累加逻辑没有问题 #

每步移动仅交换空格和相邻块，步长成本固定为1，g+1的计算完全符合IDA*的成本累加规则，不是循环的诱因。

第一步：给Node类补充正确的相等与哈希逻辑 #

补全Node类的方法，让状态一致的对象可以被正确识别为同一个节点：

class Node():
    def __init__(self, state):
        self.state = state

    # 基于实际拼图状态做相等判断，替代默认的内存地址对比
    def __eq__(self, other):
        return np.array_equal(self.state, other.state)
    
    # 配套实现哈希方法，支持集合快速查找
    def __hash__(self):
        return hash(tuple(self.state.flatten()))

    def nextnodes(self):
        zero = np.where(self.state == 0)
        y, x = int(zero[0]), int(zero[1])
        
        adjacent_moves = []
        for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            new_y, new_x = y + dy, x + dx
            # 边界判断
            if 0 <= new_y < len(self.state) and 0 <= new_x < len(self.state):
                new_state = np.copy(self.state)
                new_state[y, x], new_state[new_y, new_x] = new_state[new_y, new_x], new_state[y, x]
                adjacent_moves.append(Node(new_state))
        return adjacent_moves

第二步：优化环路检测逻辑，用集合替代线性遍历 #

同步维护一个记录当前路径上所有节点的集合，把环路判断的时间复杂度从O(路径长度)降到O(1)：

def IDA(initial_state, goal_state):
    initial_node = Node(initial_state)
    goal_node = Node(goal_state)
    
    threshold = manhattan_heuristic(initial_state, goal_state)
    path = [initial_node]
    # 与path同步维护的已访问集合，做快速环路判断
    current_path_visited = {initial_node}

    while 1:
        tmp = search(path, current_path_visited, goal_state, 0, threshold)
        if tmp == True:
            return path, threshold
        elif tmp == float('inf'):
            return False
        else:
            threshold = tmp


def search(path, visited, goal_state, g, threshold):
    node = path[-1]
    f = g + manhattan_heuristic(node.state, goal_state)

    if f > threshold:
        return f

    if np.array_equal(node.state, goal_state):
        return True

    minimum = float('inf')
    for n in node.nextnodes():
        if n not in visited:
            path.append(n)
            visited.add(n)
            tmp = search(path, visited, goal_state, g + 1, threshold)
            if tmp == True:
                return True
            if tmp < minimum:
                minimum = tmp
            # 回溯时同步移除已访问记录
            path.pop()
            visited.remove(n)

    return minimum

原有Manhattan启发函数的计算逻辑是正确的，补全上述节点判断逻辑后，算法就能正常停止循环、输出到达目标状态的最短路径。

内容的提问来源于stack exchange，提问作者cuzureau