Python对象唯一标识：八数码A*算法无限循环问题排查

问题核心分析 #

• __eq__方法不规范：虽逻辑上比较状态元素，但缺少类型判断，冗余拷贝可能引入潜在问题；重写__eq__后未同步重写__hash__，导致Python无法正确识别等价对象的哈希标识，即使当前用线性遍历，也不符合语言规范，可能引发对象识别异常。
• 手动实现优先队列缺陷：每次遍历队列查找最小f值节点，效率极低；且当队列中节点g值更新后，无法自动调整顺序，可能导致更优节点无法被优先处理，间接引发循环。
• explored列表查询低效：线性遍历检查节点是否已探索，节点数量增多时会大幅拖慢速度，且易因遍历遗漏导致重复加入节点。
• 逆序数启发式局限性：逆序数并非八数码问题的可采纳启发式（可能高估所需步数），会导致A*无法保证最优解，但这不是无限循环的直接原因。

修复方案 #

1. 规范__eq__与__hash__方法：
   • __eq__中加入类型判断，直接比较状态元素，移除冗余拷贝。
   • __hash__将二维状态转换为不可变的元组元组，确保状态相同的节点哈希值一致。
2. 改用heapq实现优先队列：利用Python标准库的heapq模块自动维护最小堆结构，每次弹出f值最小的节点，提升效率并避免手动排序错误。
3. 优化explored存储：使用set存储已探索节点（依赖正确的__hash__方法），将查询时间从O(n)降至O(1)。
4. 修复返回值与目标判断逻辑：统一AStar函数返回节点类型，避免布尔值与节点类型混用导致的报错；isGoal方法复用__eq__逻辑，简化判断。
5. 优化状态拷贝：使用深拷贝确保每个节点的状态独立，避免引用共享导致的状态意外修改。

完整修正代码 #

import random
import heapq

cols = 3
rows = 3

# 生成随机初始状态
l = list(range(9))
random.shuffle(l)
initial = [[0 for _ in range(cols)] for _ in range(rows)]
k = 0
for i in range(rows):
    for j in range(cols):
        initial[i][j] = l[k]
        k += 1
print("初始状态:")
for row in initial:
    print(row)

# 定义目标状态
arr = [[3*i + j for j in range(cols)] for i in range(rows)]

class Node:
    def __init__(self, s, p, d):
        # 深拷贝状态，避免引用共享
        self.state = [row.copy() for row in s]
        self.parent = p
        self.g = p.g + 1 if p is not None else 0
        self.isDummy = d
    
    def __eq__(self, other):
        if not isinstance(other, Node):
            return False
        for i in range(rows):
            for j in range(cols):
                if self.state[i][j] != other.state[i][j]:
                    return False
        return True
    
    def __hash__(self):
        # 将二维状态转为不可变的元组元组，用于哈希计算
        return hash(tuple(tuple(row) for row in self.state))
    
    def __lt__(self, other):
        # 用于heapq排序，比较f值
        return self.f() < other.f()
    
    def checkInversion(self):
        invert = 0
        flat_state = []
        for i in range(rows):
            flat_state.extend(self.state[i])
        for i in range(len(flat_state)):
            for j in range(i+1, len(flat_state)):
                if flat_state[j] != 0 and flat_state[i] > flat_state[j]:
                    invert += 1
        return invert
    
    def isViable(self):
        return self.checkInversion() % 2 == 0 
    
    def createChild(self, move1, move2, index):
        # 找到0的位置
        x, y = -1, -1
        for i in range(rows):
            for j in range(cols):
                if self.state[i][j] == 0:
                    x, y = i, j
                    break
            if x != -1:
                break
        
        new_x = x + move1[index]
        new_y = y + move2[index]
        
        # 检查是否越界
        if new_x < 0 or new_x >= rows or new_y <0 or new_y >= cols:
            return Node(self.state, self, True)
        
        # 生成新状态
        new_state = [row.copy() for row in self.state]
        new_state[x][y], new_state[new_x][new_y] = new_state[new_x][new_y], new_state[x][y]
        return Node(new_state, self, False)
    
    def h(self):
        return self.checkInversion()
    
    def f(self):
        return self.g + self.h()
    
    def isGoal(self):
        return self == Goal
    
    def show(self):
        for row in self.state:
            print(row)

Goal = Node(arr, None, False)

def AStar(source):
    if source.isGoal():
        return source
    
    # 初始化优先队列，存储( f值, 节点 )
    heap = []
    heapq.heappush(heap, (source.f(), source))
    explored = set()
    
    move1 = [1, 0, -1, 0]
    move2 = [0, 1, 0, -1]
    
    while heap:
        current_f, current_node = heapq.heappop(heap)
        
        # 如果已探索过，跳过
        if current_node in explored:
            continue
        
        current_node.show()
        print("---")
        
        if current_node.isGoal():
            return current_node
        
        explored.add(current_node)
        
        # 生成四个方向的子节点
        for i in range(4):
            child = current_node.createChild(move1, move2, i)
            if child.isDummy:
                continue
            
            # 如果子节点未被探索，加入队列
            if child not in explored:
                heapq.heappush(heap, (child.f(), child))

# 初始化起始节点
start_node = Node(initial, None, False)
print(f"初始状态逆序数: {start_node.checkInversion()}")

if start_node.isViable():
    result = AStar(start_node)
    print("\n找到解:")
    result.show()
else:
    print("该初始状态无解")

关键修复说明 #

• eq__与__hash：确保状态相同的节点被视为等价对象，set和heapq能正确识别重复节点，从根源避免重复处理。
• heapq优先队列：自动维护最小f值节点，避免手动遍历的低效和排序错误，保证A*算法的核心逻辑正确。
• explored集合：快速判断节点是否已处理，彻底避免重复加入相同节点导致的无限循环。
• 状态深拷贝：确保每个节点的状态独立，避免引用共享导致的状态意外修改，保证节点状态的准确性。

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