使用Python heapq实现A*算法时出现TypeError: '<'不支持错误

Python的heapq模块在比较元组时会按元素顺序依次对比。当你把(node.path_cost, node)推入堆中时，如果两个元组的path_cost相等，heapq会自动尝试比较第二个元素——也就是Node实例。但你的Node类没有定义<运算符的实现（即__lt__方法），所以当出现两个path_cost相同的节点时，就会抛出TypeError: '<' not supported between instances of 'Node' and 'Node'。

前期运行正常是因为之前入队的所有节点path_cost都不重复，直到出现第一个path_cost相同的节点对，才触发了这个隐藏问题。

有两种可行的解决方式：

方式一：给Node类添加比较方法 #

在Node类中实现__lt__方法，指定当path_cost相同时的比较规则，比如按节点深度排序：

class Node:
    def __init__(self, state, parent, action, depth):
        self.path_cost = 0
        self.state = state
        self.parent = parent
        self.action = action
        self.depth = depth
    
    def __lt__(self, other):
        # 当path_cost相同时，优先选择深度更小的节点
        return self.depth < other.depth

你也可以根据A*算法的需求，换成按state的哈希值、启发式函数值等其他规则比较。

方式二：在堆元素中加入唯一计数器 #

在你的优先队列类中新增一个递增计数器，把堆元素改成(path_cost, 计数器值, node)。因为计数器值是唯一的，即使path_cost相同，heapq会直接比较唯一的计数器值，不会再去比较Node实例：

# 假设你的优先队列类初始化方法如下
def __init__(self):
    self.pri_que = []
    self.visited_pri = set()
    self.counter = 0  # 新增唯一计数器

def astar_insert(self, node):
    self.counter += 1
    hq.heappush(self.pri_que, (node.path_cost, self.counter, node))
    self.visited_pri.add(str(node.state))

def astar_pop(self):
    # 现在堆元素是三元组，取第三个元素才是node
    node = hq.heappop(self.pri_que)[2]
    self.visited_pri.discard(str(node.state))
    return node

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