Suppressing Repeated State Generation
There appears to be interesting interaction between depth-limited search (and, by extension, iterative deepening) and the suppression of repeated state generation. If option 3 is used for suppressing repeated states, it may be necessary to set the depth limit higher than the depth of the shallowest goal in order to reach that goal. Though I have not read of this in the literature, I have observed it empirically.
If the shortest path(s) to the goal G are at depth N and the depth limit is set to N, the following problem may occur. Suppose that on each path to G, some state S on that path at depth M is reached in greater than M steps purely because the optimal path to S was not the first path explored. You miss the goal because this suboptimal path through S is longer than the depth limit. But the real problem is that repeated state suppression prevents you from getting past S (and on to the goal) later when you do explore the optimal path to S. You are stopped at S because it has already been seen.
This problem brings to light the fundamental difference between options 2 and 3 for repeated state suppression. Option 2 only prevents cycles, whereas option 3 prevents both cycles and the exploration past S through two different paths (of potentially different length) leading to S.
—D.T.
