In my attempt to implement a simple version of A* Search, I am trying to enqueue the following in a priority queue:
- Priority: sum of heuristic value and cost from source to current element
- Queue Node: Object of class queue node with data members point and cost The code goes something like this: '''s = queueNode(start, 0) q.put((s.dist + heuristics[s.pt[0]][s.pt[1]],s)) # Enqueue source cell'''
However, it gives the following error: in _put heappush(self.queue, item) TypeError: '<' not supported between instances of 'queueNode' and 'queueNode'
Here is the code for class Queue Node
class queueNode:
def __init__(self, pt, dist: int):
self.pt = pt # The cordinates of the cell
self.dist = dist # Cell's distance from the source
update: I tried to make the classes comparable by these two Implementations
First
class queueNode:
def __init__(self, pt, dist):
self.pt = pt # The cordinates of the cell
self.dist = dist # Cell's distance from the source
def __it__(self,other):
return self.dist < other.dist
Second
class queueNode:
def __init__(self, pt, dist):
self.pt = pt # The cordinates of the cell
self.dist = dist # Cell's distance from the source
def __it__(self,other):
return id(self) < id(other)
it still gives the same error
Update: A workaround to this is to use a list object instead of priority queue and sort it everytime you enter a new element. CODE q=[] APPENDING q.append((heuristics[i][j],queueNodeObject)) SORTING ON BASIS OF COST
def sort(q):
#start stop step
for i in range(0,q.__len__(),1):
for j in range(i+1,q.__len__()-1,1):
if q[i][0]<q[j][0]:
#q[i] returns the element in queue list i.e tuple=(cost, object) q[i][0] returns #the cost
temp=q[i]
q[i]=q[j]
q[j]=temp
