对于正常的深度优先搜索很简单，只需要使用HashSet的

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;
     }

由于那么它是不会做一个完整的搜索（在某种意义上总是能够找到一个解决方案，如果有的话）之前， MAXDEPTH

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?

或者，它只是不要求memoize的状态都没有。

Or it just doesn't require to memoize the state at all.

例如，决策树如下：

   A - B - C - D - E - A
                   |
                   F - G (Goal)

从国家A.启动和G为目标状态。很明显，有下深度3的溶液中。

Starting from state A. and G is a goal state. Clearly there is a solution under depth 3.

然而，使用根据深度4我的实现中，如果搜索的方向恰好是

However, using my implementation under depth 4, if the direction of search happens to be

A（0） - ＆GT; B（1） - ＆GT; C（2） - ＆GT; D（3） - ＆GT; E（4） - ＆GT; F（5）超过了深度的话，那就做回轨道 A ，但电子被访问，它会忽略检查方向 A - 电子 - F - 摹

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

推荐答案

我有同样的问题，因为你的，这是我的线程的迭代深化Common Lisp中

I had the same problem as yours, here's my thread Iterative deepening in common lisp

基本上解决使用哈希表这个问题，你不能只检查一个节点是以前还是没有参观过，你也必须考虑到深度，它是previously访问。如果你要检查节点包含的状态，这不是previously看到，或之前已见过，但在更高的深度，那么你还是应该考虑它，因为它可能会导致一个较浅的解决方案，而这正是迭代深化应该做的，它返回相同的解决方案，BFS将返回，这将是最浅的。所以在哈希表，你可以有国家为重点，深度的价值。你需要不断寻找一个较浅的结点，虽然之后更新哈希表中的深度值。

Basically to solve this problem using hashtables, you can't just check if a node was visited before or not, you have to also consider the depth at which it was previously visited. If the node you're about to examine contains a state that was not previously seen, or it was seen before but at a higher depth, then you should still consider it since it may lead to a shallower solution which is what iterative deepening supposed to do, it returns the same solution that BFS would return, which would be the shallowest. So in the hashtable you can have the state as the key, and the depth as the value. You will need to keep updating the depth value in the hashtable after finding a shallower node though.

有关循环检查另一种解决办法是原路返回路径上从当前节点到根，如果你要检查已结点出现在路径上，那么这将导致一个循环。这种方法将是更通用的，并且可以与任何搜索策略中使用。它比散列表的办法，虽然慢，具有O（四）的时间复杂度，其中d是深度，但存储器的复杂性将大大降低。

An alternative solution for cycle checking would be to backtrack on the path from the current node up to the root, if the node you're about to examine already appears on the path, then it will lead to a cycle. This approach would be more generic, and can be used with any search strategy. It is slower than the hashtable approach though, having O(d) time complexity where d is the depth, but the memory complexity will be greatly reduced.