How to store visited states in iterative deepening / depth limited search?
- by colinfang
Update: Search for the first solution.
for a normal Depth First Search it is simple, just use a hashset
bool DFS (currentState) =
{
if (myHashSet.Contains(currentState))
{
return;
}
else
{
myHashSet.Add(currentState);
}
if (IsSolution(currentState) return true;
else
{
for (var nextState in GetNextStates(currentState))
if (DFS(nextState)) return true;
}
return false;
}
However, when it becomes depth limited, i cannot simply do this
bool DFS (currentState, maxDepth) =
{
if (maxDepth = 0) return false;
if (myHashSet.Contains(currentState))
{
return;
}
else
{
myHashSet.Add(currentState);
}
if (IsSolution(currentState) return true;
else
{
for (var nextState in GetNextStates(currentState))
if (DFS(nextState, maxDepth - 1)) return true;
}
return false;
}
Because then it is not going to do a complete search (in a sense of always be able to find a solution if there is any) before maxdepth
How should I fix it? Would it add more space complexity to the algorithm?
Or it just doesn't require to memoize the state at all.
Update:
for example, a decision tree is the following:
A - B - C - D - E - A
|
F - G (Goal)
Starting from state A. and G is a goal state. Clearly there is a solution under depth 3.
However, using my implementation under depth 4, if the direction of search happens to be
A(0) -> B(1) -> C(2) -> D(3) -> E(4) -> F(5) exceeds depth, then it would do back track to A, however E is visited, it would ignore the check direction A - E - F - G
