个人中心
gpt4 book ai didi

python3 TypeError: '<' not supported error when try to implement A* algo use python heapq(Python3TypeError：尝试使用pythonheapq实现A*ALGO时出现‘<’不支持错误)

转载 作者：bug小助手 更新时间：2023-10-25 09:27:56 24 4
gpt4 key购买 nike



I am trying to implement A* algorithm using pri_que by leveraging python library heapq. In general, all the state of will be stored as a Node instance

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


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

The code is too long to paste here, but the error locates in the following block.

代码太长，无法粘贴到此处，但错误位于以下块中。


    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

The full error is:

完整的错误是：


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

I am very very confused. I try to run the code and print the solution. It seems like the code works for a well before failing. Anyway has any ideas? Thanks!

我非常非常困惑。我尝试运行代码并打印解决方案。似乎代码在失败之前对油井起作用了。不管怎样，你有什么主意吗？谢谢!


更多回答

Can you provide the full definition of Node? How do you expect two Node instances to be compared?

您能提供Node的完整定义吗？您希望如何比较两个节点实例？

@Brian61354270 Just revise the post. The Node is defined above. I honestly didn't make any comparison between two nodes. Which is why I am so confused.

@Brian61354270只需修改帖子。节点已在上面定义。老实说，我没有对两个节点进行任何比较。这就是我如此困惑的原因。

For example, in my code, I only use node.state without making any operations such as <, ==, or >

例如，在我的代码中，我只使用node.State，而没有执行任何操作，如<、==或>

You make comparisons between Nodes by putting them into a heap queue. That's how the heap algorithm works. If you can't compare Nodes, they can't be used in a heap

您可以通过将节点放入堆队列来进行节点之间的比较。这就是堆算法的工作方式。如果不能比较节点，就不能在堆中使用它们

@Brian61354270: They can be used in a heap if you guarantee that the comparison of the tuples will never fall back to comparing the Node instances. But comparing on costs alone is highly unlikely to achieve that (and clearly didn't, in the OP's case).

@Brian61354270：如果你保证元组的比较永远不会回到比较Node实例，它们可以在堆中使用。但是仅仅比较成本是不太可能实现这一点的（在OP的情况下，显然没有）。

优秀答案推荐

With a proper MRE I can't give a complete solution, but the crux of your problem is:

有了适当的MRE，我不能给出一个完整的解决方案，但你的问题的症结是：



  1. Your path_costs aren't unique (meaning entries in the heap must fall back to comparing the Nodes themselves), and

  2. Your Node class doesn't define a comparison for less-than (causing the TypeError for incomparable types).


There are two possible solutions:

有两种可能的解决方案：



  1. Push stuff on the heap with a guaranteed unique comparable value between the cost and the node itself. A good source of such guaranteed unique comparable values would be an instance of itertools.count(). Once you've made one, you'd call hq.heappush(self.pri_que, (node.path_cost, next(counter), node)) for the insertion, ensuring the node instance would never be compared.



  2. Make your Nodes comparable by defining __lt__ on the class with some meaningful comparison. You'd also want to define __eq__ and use the @functools.total_ordering decorator to ensure it's comparable for all purposes (not just the __lt__ that Python uses for ordering comparisons in the built-ins, but for other purposes where > or <= or >= are used).




更多回答

I find the issue. Turns out you guys are right. ```__lt__`` solve the problem

我发现了问题所在。事实证明你们是对的。`__lt__``解决问题

I think what heappush does is if the first element in the tuple is the same, it will compare the second element

我认为Heappush所做的是如果元组中的第一个元素相同，它会比较第二个元素

@Rieder: It's not heappush doing it at all. That's how all tuple comparisons work. It's called lexicographic ordering; the heap utilities are type-agnostic, they just ask whether the "instance" (in this case, a 2-tuple) is less than the other instance. tuple itself is checking left-to-right until it finds an unequal element, then basing the overall result on the result of comparing the unequal elements. That's why solution #1 works; even when costs are tied, by ensuring the second comparison is always unequal, the tuple comparison never compares the (non-comparable) third elements.

@Rieder：做这件事一点也不丢人。这就是所有元组比较的工作方式。这称为词典排序；堆实用程序与类型无关，它们只询问“实例”(在本例中为二元组)是否小于另一个实例。元组本身从左到右进行检查，直到找到一个不相等的元素，然后根据比较不相等的元素的结果得出总体结果。这就是解决方案1有效的原因；即使在成本相同的情况下，通过确保第二个比较总是不相等，元组比较也永远不会比较(不可比较的)第三个元素。

24 4 0
文章推荐： Spark cluster - read network shared directory(Spark群集-读取网络共享目录)
文章推荐： How to perform a wildcard search in PostgreSQL(如何在PostgreSQL中执行通配符搜索)
文章推荐： How to use separated load balancers for frontend and backend in ECS?(如何在ECS中使用前端和后端分开的负载均衡？)
文章推荐： Github New line missing end of file: Negative consequences(GitHub新行缺少文件结尾：负面后果)
bug小助手
个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章
滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com