如何在迭代加深/深度限制搜索中存储已访问的状态？

Question

更新：搜索第一个解决方案。

对于普通的深度优先搜索，很简单，只需使用哈希集合。

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

然而，当它受到深度限制时，我不能简单地这样做。

    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之前，它不会进行完整的搜索（从某种意义上说，总能找到解决方案），应该如何修复它？这会增加算法的空间复杂度吗？还是根本不需要记忆状态。

更新：例如，一个决策树如下：

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

从状态 A 开始，G 是目标状态。很明显，在深度 3 下有解决方案。

然而，在深度 4 下使用我的实现时，如果搜索方向恰好为

A(0) -> B(1) -> C(2) -> D(3) -> E(4) -> F(5) 超出深度，则会返回到 A，但 E 已被访问，它将忽略检查方向 A - E - F - G。

- colinfang

---

为什么它不会进行完整的搜索？ - Shahbaz

你应该意识到你的解决方案和DFS一样存在问题，对吧？在两种解决方案中，最后都不是DFS(child)，而应该是for (each child) DFS(child)。否则，你永远无法回溯。 - Shahbaz

@Shahbaz 是的，我忘记添加整个分支了。已更新。 - colinfang

现在，如果你仔细观察，由于DFS从F回溯到E后继续使用A，max_depth也会这样做。关键是，在底部的for循环中进行回溯并继续到下一个子节点，在每次回溯后不会检查myHashSet.Contains(E)。 - Shahbaz

@Shahbaz 在这里，myHashSet.Contains(E) 将被检查，因为它是在 currentState = A 下的 for 循环中从 DFS(E,maxDepth-1) 调用的。所以，当它回溯到 A 并检查其子节点 E 时，由于它已经被访问过了，它将自动被忽略。 - colinfang

哦，抱歉我没有注意到你的图中有一个循环。 - Shahbaz

Answer 1

我遇到了与您相同的问题，这是我的线程 Iterative deepening in common lisp。

基本上，要使用哈希表解决此问题，您不能仅仅检查节点以前是否被访问过，还必须考虑之前访问的深度。如果您即将检查的节点包含以前未见过的状态，或者以前看到但深度更大的状态，则仍应该考虑它，因为它可能会导致更浅的解决方案，这就是迭代加深法的目的，它返回与BFS相同的解决方案，即最浅的解决方案。因此，在哈希表中，您可以将状态作为键，深度作为值。您需要在找到更浅的节点后不断更新哈希表中的深度值。

另一种循环检查的替代解决方案是回溯当前节点到根节点的路径，如果您即将检查的节点已经出现在路径上，则会导致循环。这种方法更通用，可以与任何搜索策略一起使用。它比哈希表方法慢，时间复杂度为O(d)，其中d为深度，但内存复杂度将大大降低。

- turingcomplete

Answer 2

在IDFS的每个步骤中，实际上是在寻找一条最短的路径，你不能简单地使用HashSet。只有当你正在搜索长度无限的路径存在时，HashSet才有用。

在这种情况下，你应该使用HashMap来存储到达状态的最小步数，并且仅在无法更新映射值时修剪分支。时间复杂度可能会相应改变。

但事实上，当空间有限时，IDFS被用于代替BFS。由于哈希状态可能占用与BFS几乎相同的空间，通常你不能轻易地将所有状态存储在IDFS中。

维基百科中的IDFS也没有哈希。http://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search 因此，让我们放弃哈希，用时间换空间！

更新：

将状态存储在当前dfs堆栈中是值得的，这样搜索路径就不会导致一个微不足道的循环。实现此功能的伪代码如下：

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;
      }
      myHashSet.Remove(currentState); //the state is pop out from the stack
      return false;
 }

- chyx

---

值得在每个状态下添加一个哈希集合的副本吗？这样子状态的哈希集合将包括其所有的前任，以便进一步搜索不会导致循环。因此，空间复杂度将为O(深度的平方)。 - colinfang

Answer 3

你展示的解决方案非常好，适用于深度优先搜索（迭代加深）。只需在增加深度之前不要忘记清除myHashSet。

- Ivaylo Strandjev