c# - 完全な反復深化深さ優先探索

Question

その瞬間、私はこのようなオブジェクトを持っています。

C#
public class Step {
  int id;
  List<Step> nextSteps;
}

そして、ループを許可しないという事実を除けば、非常によく似た別のオブジェクトに変換しようとしています。

すでにより深い位置に出現しているノードの子を拡張しないことにより、ループを処理する必要があります。反復深化はこれを解決します（深さ優先探索の実装ですが、幅優先探索の順序）が、次の構造を使用した実装に苦労しています。

私が見つけたすべての実装は、ある種のゴールノードを見つけることに依存していますが、ツリー全体を拡張する必要があります。

どんな助けでもいただければ幸いです。：D

Answer 1

を追加Dictionary<Step, int>し、ノードを展開するたびに、その深さでノードを追加します。

void ExpandStep(Step s, int d)
{
    int prevDepth;
    if (lookup.TryGetValue(s, out prevDepth) && prevDepth <= d)
      return;
    lookup.Add(s, d);
    ... 
}