3

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

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

    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

4

3 回答 3

2

我遇到了和你一样的问题，这是我的线程Iterative deeping in common lisp

基本上要使用哈希表解决这个问题，你不能只检查一个节点之前是否被访问过，你还必须考虑它之前访问过的深度。如果您要检查的节点包含以前未见过的状态，或者以前曾见过但在更高的深度，那么您仍然应该考虑它，因为它可能会导致更浅的解决方案，而这正是迭代加深应该做到的确实，它返回的解决方案与 BFS 将返回的解决方案相同，这将是最浅的。因此，在哈希表中，您可以将状态作为键，将深度作为值。不过，在找到较浅的节点后，您将需要不断更新哈希表中的深度值。

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

于 2012-11-01T04:41:40.550 回答
1

在 IDFS 的每一步中，你实际上是在寻找一条最短的路径，你不能简单地使用hashSet。HashSet 仅在您搜索是否存在长度不受限制的路径时才有帮助。

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

但实际上，在空间有限的情况下，使用 IDFS 代替了 BFS。由于散列状态可能占用几乎与 BFS 一样多的空间，通常您不能将所有状态都存储在 IDFS 中。

wiki 中的 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;
 }
于 2012-09-26T15:52:09.497 回答
0

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

于 2012-09-26T12:08:46.750 回答