首页 文章

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

提问于
浏览 次
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

algorithm artificial-intelligence depth-first-search iterative-deepening

3 回答

  • 2

    我和你的问题一样，这是我的主题Iterative deepening in common lisp

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

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

    回复于
  • 1

    在IDFS的每一步中，您实际上都在搜索 shortest 的路径，您不能简单地使用 hashSet . 只有当您搜索长度无限制的路径时，HashSet才有帮助 .

    在这种情况下，您应该使用 hashMap 来存储 minimum step 以达到状态并仅在无法更新 Map 值时修剪分支 . 时间复杂度可以相应地改变 .

    但实际上，当空间有限时，IDFS用于代替BFS . 作为散列，状态可能占用的空间几乎与BFS一样多，通常您无法将所有状态存储在IDFS中 .

    wiki中的IDFS也没有哈希值 . http://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search

    那么让我们摒弃空间的哈希和交易时间吧！

    Update

    将状态存储在当前的dfs堆栈中是值得的，然后搜索路径不会导致琐碎的循环 . 实现此功能的psudocode将是：

    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;
 }
    回复于
  • 0

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

    回复于

相关问题