TypeError:unorderable类型:Node()<Node()

Question

在Python中,我正在实现用于解决Tile问题的A*搜索算法.我有以下Node类,它将状态保存为元组的元组.例如,初始状态是:

initial= ((7,2,4),(5,0,6),(8,3,1));#empty tile is marked with value 0

下面是Node类,

class Node:
    def __init__(self, state, parent=None, action=None, pathCost=0, emptyTileI=1,emptyTileJ=1):
        self.state = state
        self.parent = parent
        self.action = action
        self.pathCost = pathCost
        self.emptyTileI=emptyTileI;#row index of empty tile
        self.emptyTileJ=emptyTileJ;#column index of empty tile
    def expand(self, problem):
        children=[];#empty list of children nodes initially.
        #after doing some work....
        return children #a list of Node objects, one for each successor states, parent of the created nodes is self
    def getState(self):
        return self.state;
    def getPathCost(self):
        return self.pathCost;
    def getParent(self):
        return self.parent;

我还有一个TileProblem类,它包含将由A*使用的启发式,如下所示,

## very generic Problem superclass, subclasses can overwrite the goal test and the constructor, and should also add a successors function
class Problem:
    def __init__(self, initial, goal=None):
        self.initial = initial
        self.goal = goal
    def goalTest(self, state):
        return state == self.goal

class TileProblem(Problem):
    def __init__(self, initial, goal=None):
        self.initial = initial
        self.goal = goal
    #used in priority queue
    "(Uses Accumulated Manhattan Distance heuristic)"
    def fAMD(self,element):
        return self.g(element)+self.hAMD(element)
    "(Uses Number of Misplaced Tiles heuristic)"
    def fMT(self,element):
        return self.g(element)+self.hMT(element)

    #backward cost. #When this function is executed, the parent of the element has been already updated (by expand function in parent Node)
    def g(self,element):
        return element.pathCost
    #forward cost 
    "(Accumulated Manhattan Distance heuristic)"
    def hAMD(self,element):
        goalState=self.goal
        elementState=element.getState()
        "We will calculate the accumulated Manhattan distance between goal state and element state"
        accumulatedSum=0;
        for i,tgoal in enumerate(goalState):
            for j,vGoal in enumerate(tgoal):
                for m, tElement in enumerate(elementState):
                    for n, vElement in enumerate(tElement):
                        if vGoal==vElement:
                            accumulatedSum=accumulatedSum + abs(i-m)+abs(j-n);#Manhattan distance

        return accumulatedSum

    #forward cost 
    "(Number of Misplaced Tiles heuristic)"
    def hMT(self,element):
        goalState=self.goal
        elementState=element.getState()
        "We will calculate the number of misplaced tiles between goal state and element state"
        misplacedTileSum=0;
        for m, tElement in enumerate(elementState):
            for n, vElement in enumerate(tElement):
                if(vElement!=goalState[m][n]):
                    misplacedTileSum=misplacedTileSum+1;
        return misplacedTileSum;

优先级队列类如下,

class PriorityQueue:
    def __init__(self, f):
        self.f = f ## save the function for later, when we apply it to incoming items (nodes)
        self.q = []#defaultdict(list)
        self.maximal_size=0
    def push(self, item):
        insort(self.q, (self.f(item), item))
        self.updateMaximalSize();
    def pop(self):
        return self.q.pop(0)[1]
    def empty(self):
        return self.q==[];
    def getMaximalSize(self):
        return self.maximal_size
    def updateMaximalSize(self):
        if(len(self.q)>self.maximal_size):
            self.maximal_size=len(self.q)
    def getF(self):
        return self.f;
   # def printQ(self):
    #    for t in self.q:
     #       print("("+repr(t[0])+","+repr(t[1].getState())+")");

    #returns the priority value of an element if it exists or None otherwise
    #Needed in A* to judge whether to push an element to the queue or not by comparing its current priority to the updated one
    def getPriorityValue(self,item):
        for e in self.q:
            if e[1].getState()==item.getState():
                return e[0];
        return None

    #updates the priority value of an element in the queue. Needed in A* to decrease the priority value of an element
    def updatePriorityValue(self,item):
        self.q = [(v,i) if (i.getState() != item.getState()) else (self.f(item),item) for (v, i) in self.q]
        self.updateMaximalSize();

我的A*算法,

def aStarSearch(problem,frontier):
    closed=[];#explored set
    frontier.push(Node(problem.initial))
    print("In A* Search, Popping The Following Nodes (States) in-order:")
    while not frontier.empty():
        node=frontier.pop();
        print(node.getState()), #printing the history of popped nodes(states)
        closed.append(node.getState()); # add it to closed state to prevent processing it again
        if problem.goalTest(node.getState()): #if this is a goal node
            return node; #just return it
        children=node.expand(problem); #otherwise, lets expand it
        for c in children: #looping over the children
            if(c.getState() in closed): #already popped from the queue and closed
                continue; #ignore it
            priorityValue=frontier.getPriorityValue(c); #the child priority value in the queue
            if(priorityValue==None): #not in the queue
                frontier.push(c) #add it to the queue
            elif (frontier.getF(c) < priorityValue): #in the queue but this is a better path
                frontier.updatePriorityValue(c); #decrease the priority in the queue
        #frontier.printQ();        
    return None;

最后,在我的主要,

initial= ((7,2,4),(5,0,6),(8,3,1));#empty tile is marked with value 0
goal=((1,2,3),(4,5,6),(7,8,0));

"A* Graph Search using Accumulated Manhattan Distance heuristic"
print("A* Graph Search using Accumulated Manhattan Distance heuristic:")
tileAStarSearch = TileProblem(initial,goal); 
frontier= PriorityQueue(tileAStarSearch.fAMD); #accumulated Manhattan distance heuristic
aStarResult=aStarSearch(tileAStarSearch, frontier);

当我运行代码时,我收到以下错误:

    aStarResult=aStarSearch(tileAStarSearch, frontier);
  File "C:\Users\zjalmahmoud\workspace\Tile_Problem\search.py", line 211, in aStarSearch
    frontier.push(c) #add it to the queue
  File "C:\Users\zjalmahmoud\workspace\Tile_Problem\utilsSimple.py", line 61, in push
    insort(self.q, (self.f(item), item))
TypeError: unorderable types: Node() < Node()

我不明白这个问题的原因.为什么insort会关心这些物品.我只希望它推送项目并按"优先级"值排序,在我的情况下,这是一个整数(累积的曼哈顿距离).我怎么解决这个问题？谢谢.

Answer 1

您在队列中具有相同优先级的节点.然后,Python尝试(priority, node)通过比较节点来对元组进行排序.这是因为元组按字典顺序进行比较,就像你对名字进行排序一样.使用两个名称,如果第一个字母匹配,则比较第二个字母等,直到您有不同的字母并可以对它们进行排序,比较元组的工作方式相同.如果优先级匹配,则比较节点.

要么让你的节点可以订购(你可以使用functools.total_ordering()装饰器加一个__eq__和一个__lt__方法)或者将一个计数器值插入优先级队列元组来打破平局:

# at the top
from itertools import count

class PriorityQueue:
    def __init__(self, f):
        self.f = f ## save the function for later, when we apply it to incoming items (nodes)
        self.q = []#defaultdict(list)
        self.maximal_size=0
        self._counter = count()
    def push(self, item):
        insort(self.q, (self.f(item), next(self._counter), item))
        self.updateMaximalSize()

并更新PriorityQueue()类的其余部分以在索引处查找项目2(或者更好地在索引处查找-1).更新方法中的列表updatePriorityValue()解析以将队列项解压缩到(v, c, i)并在左侧表达式中再次包含它们.

计数器(由...产生itertools.count())插入一个不断增加的整数,因此永远不会有两个元组,(priority, counter, item)其中优先级和计数器都相等; 因此,物品永远不会被比较.

这意味着,对于相同的优先级,稍后插入的项目将赢得平局.使用-next(self._counter),如果你想插入的项目,而不是更早,而不是取胜.