Message6790

Author manuel
Recipients jendrik, malte, manuel
Date 2018-02-07.12:57:38
Content
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
number).

If no, then we should document the non-deterministic behavior of AdaptiveQueue
and affected classes.
History
Date User Action Args
2018-02-07 12:57:38manuelsetrecipients: + manuel, malte, jendrik
2018-02-07 12:57:38manuelsetmessageid: <1518004658.64.0.805315936194.issue760@unibas.ch>
2018-02-07 12:57:38manuellinkissue760 messages
2018-02-07 12:57:38manuelcreate