I finally found out what was the reason that the number of iterations
exceeded the expectations, at least for some of the boards. Apparently,
some of the DFS scans recursed into a state, which had children that were
found in their recursion stacks. Since the scan-specific visited flag was
set for them, they could not recurse into them further, and they
eventually back-tracked.
When back-tracking, they marked the state as a dead end, and so scans who
entered this state before entering its child (or in the original scan
case, forefather), could not go there in the first place.
Note that the multi-scanning model is still correct, but it no longer can
ensure that solutions will be found in a time that is lesser or equal to
the sum of its parts. The easiest solution would be to avoid scan
interoperation altogether, but I'd like to investigate or think of
other models.
Regards,
Shlomi Fish
----------------------------------------------------------------------
Shlomi Fish shlomif_at_vipe.technion.ac.il
Home Page:
http://t2.technion.ac.il/~shlomif/
Home E-mail: shlomif_at_iglu.org.il
He who re-invents the wheel, understands much better how a wheel works.
Received on Tue Jun 18 2002 - 06:54:28 IDT