0

Looking for some logic advice. I am running a depth limited search in order to get from a start state to an end state. I am expanding all possible moves from each node which at depths > 0 includes the source node (this is the problem).

I have tried storing previous states and including it as a condition for not expanding. However, this also negates the ability of other expansion branches to pass through this state.

From a logic perspective, how can I avoid this problem and at the same time avoid back-peddling?

@acelent comment (here) gave me an idea to create a configDepth class which stores each visited state and its corresponding depth. Then in the next recursion - 

IF newState(depth) == state(depth-1) THEN !expand

What are your thoughts on this solution? I have gone down many blind alleys and need fresh opinions and ideas.

Thank you.

Community
  • 1
  • 1
Shooresh
  • 105
  • 1
  • 11

1 Answers1

1

Since recursion is a good way to implement a depth search you can create another recursion which will receive a maximum depth where it can reach. If this depth is reached it would break the recursion an it would go back to the previous node which still have elements which haven't reached this depth.

For this you would need to to either have the vertexes known their depth from the creation of the tree or you can just calculate it as you are going down with the recursion.

Wald
  • 1,063
  • 7
  • 13