TypeError: unorderable types: Node() < Node()
TypeError: unorderable types: Node() < Node()
在 Python 中，我正在实施 A* 搜索算法来解决拼贴问题。
我有以下节点 class，它将状态保存为元组的元组。例如初始状态是：
initial= ((7,2,4),(5,0,6),(8,3,1));#empty tile is marked with value 0
下面是节点class,
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 class，它包含 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如下，
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()
我不明白这个问题的原因。为什么分类要关心这些项目。我只希望它推送项目并按 "priority" 值排序，在我的例子中这是一个整数（累积的曼哈顿距离）。我怎么解决这个问题？谢谢。
您在队列中有同等优先级的节点。 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() class 的其余部分以在索引 2 处查找项目（或者更好的是，在索引 -1 处）。更新 updatePriorityValue() 方法中的列表推导式，将队列项解包为 (v, c, i) 并将它们再次包含在左侧表达式中。
计数器（由itertools.count()产生）插入一个不断增加的整数，所以永远不会有两个元组 (priority, counter, item) 其中优先级和计数器都相等；因此永远不会比较这些项目。
这意味着对于同等优先级，稍后 插入的项目赢得平局。如果您希望 较早 插入的项目取而代之，请改用 -next(self._counter)。
在 Python 中，我正在实施 A* 搜索算法来解决拼贴问题。 我有以下节点 class，它将状态保存为元组的元组。例如初始状态是：
initial= ((7,2,4),(5,0,6),(8,3,1));#empty tile is marked with value 0
下面是节点class,
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 class，它包含 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如下，
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()
我不明白这个问题的原因。为什么分类要关心这些项目。我只希望它推送项目并按 "priority" 值排序，在我的例子中这是一个整数（累积的曼哈顿距离）。我怎么解决这个问题？谢谢。
您在队列中有同等优先级的节点。 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() class 的其余部分以在索引 2 处查找项目（或者更好的是，在索引 -1 处）。更新 updatePriorityValue() 方法中的列表推导式，将队列项解包为 (v, c, i) 并将它们再次包含在左侧表达式中。
计数器（由itertools.count()产生）插入一个不断增加的整数，所以永远不会有两个元组 (priority, counter, item) 其中优先级和计数器都相等；因此永远不会比较这些项目。
这意味着对于同等优先级，稍后 插入的项目赢得平局。如果您希望 较早 插入的项目取而代之，请改用 -next(self._counter)。