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

私はあなたと同じ問題を抱えていました。ここに私のスレッドがあります。

基本的に、ハッシュテーブルを使用してこの問題を解決するには、ノードが以前にアクセスされたかどうかを確認するだけではなく、以前にアクセスされた深度も考慮する必要があります。調べようとしているノードに以前に見られなかった状態が含まれている場合、または以前に見られたがより深い深さで見られた場合でも、反復深化が想定していたより浅いソリューションにつながる可能性があるため、それを考慮する必要があります。実行すると、BFS が返すのと同じ解が返されますが、これは最も浅いものです。したがって、ハッシュテーブルでは、状態をキーとして、深さを値として持つことができます。ただし、より浅いノードを見つけた後、ハッシュテーブルの深さの値を更新し続ける必要があります。

サイクル チェックの別の解決策は、現在のノードからルートまでのパスをバックトラックすることです。調べようとしているノードが既にパスに表示されている場合は、サイクルが発生します。このアプローチはより一般的であり、あらゆる検索戦略で使用できます。ただし、d が深さである O(d) 時間の複雑さを持つため、ハッシュテーブル アプローチよりも遅くなりますが、メモリの複雑さは大幅に軽減されます。

于 2012-11-01T04:41:40.550 に答える
1

IDFS の各ステップで、実際には最短のパスを検索しているため、単純にhashSetを使用することはできません。HashSet は、長さが無制限のパスの存在を検索する場合にのみ役立ちます。

この場合、おそらくhashMapを使用して状態に到達するための最小ステップを保存し、マップ値を更新できない場合にのみブランチをプルーニングする必要があります。時間の複雑さは、対応して変更される場合があります。

しかし実際には、スペースが限られている場合、BFS の代わりに IDFS が使用されます。状態のハッシュには 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;
 }
于 2012-09-26T15:52:09.497 に答える
0

あなたが示すソリューションは完全に問題なく、DFSID（反復深化による深さ優先検索）で機能します。myHashSet深さを増やす前にクリアすることを忘れないでください。

于 2012-09-26T12:08:46.750 に答える