Title Non-deterministic behavior of AdaptiveQueue
Priority bug Status unread
Superseder Nosy List jendrik, malte, manuel, silvan
Assigned To Keywords
Optional summary

Created on 2018-02-07.12:57:38 by manuel, last changed by silvan.

msg6790 (view) Author: manuel Date: 2018-02-07.12:57:38
The AdaptiveQueue starts with a BucketQueue and changes to a HeapQueue after a
given condition is fulfilled.

While the BucketQueue does tie-breaking (among values that are assigned to the
same key) in a lifo manner, the tie-breaking of HeapQueue is undefined and
non-deterministic, resulting in a non-deterministic behavior of AdaptiveQueue.

AdaptiveQueue is used for the computation of FF heuristic, which I expected to
assign deterministic values to states.

Is AdaptiveQueue generally expected to be deterministic?

If yes, there could be two different solutions:
1. We could pass an comparison function for values to AbstractQueue (from which
AdaptiveQueue is derived).
2. We could assign a number to each key/value pair that is inserted to
HeapQueue. The number increases with each inserted key/value pair, which allows
to store values in a fifo manner (likewise to BucketQueue) within the HeapQueue.

Both solutions result in a disadvantage for either BucketQueue (additional time
for sorting a vector) or HeapQueue (additional memory for storing the insertion

If no, then we should document the non-deterministic behavior of AdaptiveQueue
and affected classes.
Date User Action Args
2018-02-08 12:11:10silvansetnosy: + silvan
2018-02-07 12:57:38manuelcreate