[next] [prev] [up] Date: Sun, 08 Jan 95 16:25:34 -0500
[next] [prev] [up] From: michael reid <mreid@ptc.com >
[next] [prev] [up] Subject: Re: two stage filtration

dik writes:

>run times were improved significantly by using a simple trick that i hadn't
>used in earlier programs. during the first few depth levels, i use
>"forward searching", i.e. i examine the neighbors of each configuration
>found at the previous depth. however, after at least half the search space
>has been found, i switch to "backward searching", i.e. examine the
>configurations (and their neighbors) that haven't yet been found.

>(have others been using this same idea when running similar search programs?)

>closer analysis of this technique suggests that the switch from forward to
>backward searching should occur even before half the space has been found.

Here I am a bit surprised. I would think the time needed for a phase is
entirely dependend on the number of neighbo(u)rs you have to examine. This
appears to be 6 times the number of configurations you visit. So I would
think that going the other way pays when the number of configurations not
yet decided is less than the number of configurations found in the previous

except that when searching backward, you need not visit all the neighbors
of a configuration. you only need to find one neighbor at the previous
distance; after that, the other neighbors don't need to be examined.

i did not realize this until implementing this technique.


[next] [prev] [up] [top] [help]