python3 TypeError: '<' not supported 错误,当尝试实现 A* algo use python heapq 时出现错误

python3 TypeError: '<' not supported error when try to implement A* algo use python heapq

提问人:Rieder 提问时间:9/11/2023 最后编辑:NimanthaRieder 更新时间:10/29/2023 访问量:91

问:

我正在尝试通过利用 python 库 heapq 使用 pri_que 实现 A* 算法。通常,所有状态都将存储为一个 Node 实例

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 astar_insert(self, node):
        hq.heappush(self.pri_que, (node.path_cost, node))
        self.visited_pri.add(str(node.state))
    
 
    def astar_pop(self):
        
        node = hq.heappop(self.pri_que)[1] # <-------------------- this line

        self.visited_pri.discard(str(node.state))
        return node

完整的错误是:

TypeError: '<' not supported between instances of 'Node' and 'Node'

我很困惑。我尝试运行代码并打印解决方案。似乎代码在失败之前可以很好地工作。

python-3.x 优先级队列 a-star

评论

0赞 Brian61354270 9/11/2023
您能提供 的完整定义吗?您期望如何比较两个实例?NodeNode
0赞 Rieder 9/11/2023
@Brian61354270 只需修改帖子即可。节点在上面定义。老实说,我没有在两个节点之间进行任何比较。这就是为什么我如此困惑。
0赞 Rieder 9/11/2023
例如,在我的代码中,我只使用 node.state,而不进行任何操作,例如 <、== 或 >
0赞 Brian61354270 9/11/2023
您可以通过将它们放入堆队列中来进行比较。这就是堆算法的工作原理。如果不能比较,它们就不能在堆中使用NodesNodes
0赞 ShadowRanger 9/11/2023
@Brian61354270:如果你保证 s 的比较永远不会回退到比较实例,它们就可以在堆中使用。但是,仅靠成本比较是极不可能实现这一点的(在OP的案例中,显然没有)。tupleNode

答:

2赞 ShadowRanger 9/11/2023 #1

问题的症结在于:

  1. 你的 s 不是唯一的(这意味着堆中的条目必须回退到比较 s 本身),并且path_costNode
  2. 您的类未定义小于的比较(导致 对于不可比较的类型)。NodeTypeError

有两种可能的解决方案:

  1. 将东西推到堆上,保证成本和本身之间具有唯一可比价值。这种有保证的唯一可比值的一个很好的来源是 itertools.count() 的实例。一旦你做了一个,你就会要求插入,确保永远不会比较实例。nodehq.heappush(self.pri_que, (node.path_cost, next(counter), node))node

  2. 通过对类进行一些有意义的比较来使你的 s 具有可比性。您还需要定义和使用装饰器,以确保它在所有用途上都具有可比性(不仅仅是 Python 用于在内置中对比较进行排序的用途,而是用于使用或或使用的其他目的)。Node__lt____eq__@functools.total_ordering__lt__><=>=

评论

0赞 Rieder 9/11/2023
我找到了问题。事实证明,你们是对的。'''__lt__''解决问题
0赞 Rieder 9/11/2023
我认为 heappush 的作用是,如果元组中的第一个元素相同,它将比较第二个元素
1赞 ShadowRanger 9/11/2023
@Rieder:它根本没有这样做。这就是所有比较的工作方式。这称为词典排序;堆实用程序与类型无关,它们只询问“实例”(在本例中为 2 元组)是否小于另一个实例。 它本身是从左到右检查,直到找到一个不相等的元素,然后根据比较不相等元素的结果来获得整体结果。这就是解决方案 #1 起作用的原因;即使成本是并列的,通过确保第二个比较总是不相等的,比较也永远不会比较(不可比较的)第三个要素。heappushtupletupletuple