ТипError: unorderable types: Node() <Node()

Question

В Python я реализую алгоритм поиска A * для решения проблемы с черепицей. У меня есть следующий класс Node, который содержит состояние как кортеж кортежа. Например, начальное состояние:

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

Ниже приведен класс узла,

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() 

я не делаю понять причину этой проблемы. Зачем нужно, чтобы косметика заботилась о предметах. Я только ожидаю, что он подтолкнет элемент и отсортируется по значению «приоритет», которое является целым числом в моем случае (накопленное расстояние Манхэттена). Как я могу решить эту проблему? Благодарю.

Answer 1

У вас есть узлы с равным приоритетом в очереди. Затем Python пытается упорядочить кортеж (priority, node) путем сравнения узлов. Это связано с тем, что кортежи сравниваются в лексикографическом порядке, так же, как и сортировать имена. С двумя именами, если совпадают первые буквы, вы сравниваете вторую букву и т. Д., Пока у вас не будет разных букв, и можете заказать их, так же сравнивая кортежи. Если приоритеты совпадают, узлы сравниваются.

Либо сделать ваши узлы упорядочиваемы (вы можете использовать functools.total_ordering() decorator плюс __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), если вы хотите, чтобы вставляемые предметы раньше вместо этого выиграли.