...

This is especially true for the 15-puzzle with its cheap operator cost.

...

This is just a partial re-ordering, not a total sort. Nodes are sorted to the average size of all subtrees in the last iteration, .

...

While in the `first-solution-case' node expansion can be stopped after a first solution is found, all processors must finish searching their current subtree in the `all-solutions-case'. Due to different work packet sizes, which vary most in the last iteration, some processors might get idle while others are still expanding their last tree. Most of the overheads in

can be reduced by implementing a stack-splitting strategy as in [Kumar and Rao, 1990].

...

avg. values: Manhattan distance h = 46, solution path length g = 67.5, 11.8 iterations, 56.2 billion nodes