将Node（）添加到优先级Queu时发生Python错误

Question

我正在编写一个A*算法（使用错位瓷砖启发式算法）来解决8个难题。当我试图将Node()对象添加到优先级队列时，它会给我一个错误“TypeError:unordered types:Node（）<；Node（）”。为什么会这样？在

import collections
import queue
import time

class Node:

    def __init__(self, puzzle, last=None):
        self.puzzle = puzzle
        self.last = last

    @property
    def seq(self): # to keep track of the sequence used to get to the goal
        node, seq = self, []
        while node:
            seq.append(node)
            node = node.last
        yield from reversed(seq)

    @property
    def state(self):
        return str(self.puzzle.board) # hashable so it can be compared in sets

    @property
    def isSolved(self):
        return self.puzzle.isSolved

    @property
    def getMoves(self):
        return self.puzzle.getMoves

    def getMTcost(self):
        """
        A* Heuristic where the next node to be expanded is chosen based upon how 
        many misplaced tiles (MT) are in the state of the next node 
        """
        totalMTcost = 0
        b = self.puzzle.board[:]
        # simply +1 if the tile isn't in the goal position
        # the zero tile doesn't count
        if b[1] != 1:
            totalMTcost += 1
        if b[2] != 2:
            totalMTcost += 1
        if b[3] != 3:
            totalMTcost += 1
        if b[4] != 4:
            totalMTcost += 1
        if b[5] != 5:
            totalMTcost += 1
        if b[6] != 6:
            totalMTcost += 1
        if b[7] != 7:
            totalMTcost += 1
        if b[8] != 8:
            totalMTcost += 1

        return totalMTcost

class Solver:

    def __init__(self, Puzzle):
        self.puzzle = Puzzle

    def FindLowestMTcost(NodeList):
        print(len(NodeList))
        lowestMTcostNode = NodeList[0]
        lowestMTcost = lowestMTcostNode.getMTcost()
        for i in range(len(NodeList)):
            if NodeList[i].getMTcost() < lowestMTcost:
                lowestMTcostNode = NodeList[i]
        return lowestMTcostNode # returns Node object

    def AStarMT(self):
        visited = set()
        myPQ = queue.PriorityQueue(0)
        myPQ.put((0, Node(self.puzzle))) # Accepted here???
        while myPQ:
            closetChild = myPQ.get()[1]
            visited.add(closetChild.state)
            for board in closetChild.getMoves:
                newChild = Node(board, closetChild)
                if newChild.state not in visited:
                    if newChild.getMTcost() == 0:
                        return newChild.seq
                    priority_num = newChild.getMTcost()
                    myPQ.put((priority_num, newChild)) # ERROR HERE

Answer 1

我猜你在推两个具有相同优先级的节点。由于您的PriorityQueue项是priority, Node元组，因此比较元组将首先检查优先级，并且只有当它们相等时，才会比较Nodes

解决这个问题的一个方法是在元组中提供一个附加的中断值。一个稳定增加的计数器是一个常见的中断（但是如果你想让新的节点比旧的节点排序，请考虑一个递减数）：

myPQ = queue.PriorityQueue()
count = 0

# later, when you add to the queue:
myPQ.put((priority_num, count, newChild))
count += 1

如果您不想手动递增计数器，可以使用itertools.count，它提供一个无限的递增值生成器。只要使用count = itertools.count()，然后在需要新值时使用next(count)。在

最后一点：您使用的是queue模块中的PriorityQueue类。该模块是为线程间通信而设计的，而不是一般用途的数据结构。它会做很多你根本不在乎的锁东西。更好的方法是使用heapq模块从列表中生成优先级队列：

^{pr2}$