CODEWITHSUNDEEP
pythonpython-3.x
James Rolfe
James Rolfe

Reputation: 77

Python Error Adding Node() to Priority Queue

I am coding an A* algorithm (using the Misplaced Tiles heuristic) to solve the 8 puzzle problem. When I try to add a Node() object to the priority queue it gives me a error of "TypeError: unorderable types: Node() < Node()". Why is this? 

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

Upvotes: 0

Views: 1895

Answers (1)

Blckknght
Blckknght

Reputation: 104832

I'd guess that you're pushing two nodes with the same priority. Since your PriorityQueue items are priority, Node tuples, a comparison of the tuple will first check the priority, and only if they are equal will it compare the Nodes.

A fix for this is to provide an additional tie-breaking value in the tuple. A steadily increasing counter is a common tie breaker (but consider a descreasing number if you want newer nodes to sort before older ones):

myPQ = queue.PriorityQueue()
count = 0

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

If you don't want to be manually incrementing the counter, you could use itertools.count which gives an infinite generator of increasing values. just use count = itertools.count() and then next(count) whenever you need a new value.

One final note: You're using the PriorityQueue class from the queue module. That module is designed for inter-thread communication, not really for general purpose data structures. It will be doing a bunch of locking stuff that you really don't care about. A better way is to use the heapq module to make a priority queue out of a list:

import heapq

# create the queue (a regular list)
my_queue = []

# push to the queue
heapq.heappush(my_queue, (priority, tie_breaker, value))

# pop from the queue
result_priority, _, result_value = heapq.heappop(my_queue)

Upvotes: 3

Related Questions