From: Mason Kelsey <masonkelsey@...>
Date: 2009-10-01T05:50:38+09:00
Subject: Control of Priority Queue Order? And size limits on queues?

--00032557b58ac66e0e0474d1ae60
Content-Type: text/plain; charset=ISO-8859-1

I've successfully used the Priority Queue to sort ascending items for
solving the 8-puzzle problem.  I noticed that the Priority Queue method had
a unique way of sorting items with matching keys.  It puts the newest items
furtherest from the top.  The older a matching item is, the further it is
towards the top.   That is OK by me as it essentially added a negative g(n)
node value to the h(n) heuristic value that aided in the A* best-first
algorithm.  If the newest matching item had been added at the top, it would
have slowed the program down by going down fruitless paths and
probably would create a less optimal path to the results.

The code I used was: open_queue = PQueue.new(proc{|x,y| x[0]<y[0]}), where I
was sorting on the first element of each item.

But for future use, is there a way to force the Priority Queue to always add
the newest matching item in front of the older matching items?  Please be
aware I am not asking for a descending sort, which I know how to do.

Also, related to unsolvable problems, is there a limit to the size of the
Priority Queue?  Or, perhaps a better way to ask is what would limit the
size of the Priority Queue.  I would have to guess that the same limits
would apply to any type of queue.  I've noticed that searching the Priority
Queue for a matching value item is very slow in Ruby.  I had over 1300 items
in my Priority Queue by the time I killed the run as it had run all night to
just get to that size.  Yes, I realize this is an interpreted language.  I'm
just trying to push Ruby to its limits to see if it breaks.

Does anyone know?

No Sam

--00032557b58ac66e0e0474d1ae60--