M
Mason Kelsey
[Note: parts of this message were removed to make it a legal post.]
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
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