提问人:Rieder 提问时间:9/11/2023 最后编辑:NimanthaRieder 更新时间:10/29/2023 访问量:91
python3 TypeError: '<' not supported 错误,当尝试实现 A* algo use python heapq 时出现错误
python3 TypeError: '<' not supported error when try to implement A* algo use python heapq
问:
我正在尝试通过利用 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'
我很困惑。我尝试运行代码并打印解决方案。似乎代码在失败之前可以很好地工作。
答:
2赞
ShadowRanger
9/11/2023
#1
问题的症结在于:
- 你的 s 不是唯一的(这意味着堆中的条目必须回退到比较 s 本身),并且
path_cost
Node
- 您的类未定义小于的比较(导致 对于不可比较的类型)。
Node
TypeError
有两种可能的解决方案:
将东西推到堆上,保证成本和本身之间具有唯一可比价值。这种有保证的唯一可比值的一个很好的来源是
itertools.count()
的实例。一旦你做了一个,你就会要求插入,确保永远不会比较实例。node
hq.heappush(self.pri_que, (node.path_cost, next(counter), node))
node
通过对类进行一些有意义的比较来使你的 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 起作用的原因;即使成本是并列的,通过确保第二个比较总是不相等的,比较也永远不会比较(不可比较的)第三个要素。heappush
tuple
tuple
tuple
评论
Node
Node
Nodes
Nodes
tuple
Node