このメソッドを再帰的から反復的に変換する

Question

次のメソッドは再帰的ですが、リストが長すぎるためにStackOverflowが取得されています。経験を積んだ誰かがこのコードを反復的に変換できますか？

private List<Node> FindWayFrom(
     Node srcNode, 
     Node dstNode, 
     List<Node> way, 
     List<Node> visitedNodes) 
    { 
     if (visitedNodes.Contains(srcNode)) 
      return null; 

     visitedNodes.Add(srcNode); 
     way.Add(srcNode); 

     IList connectedNodes = GetConnectedNodes(srcNode); 

     if (connectedNodes == null || connectedNodes.Count == 0) 
      return null; 

     foreach (Node node in connectedNodes) 
     { 
      if (node == dstNode) return way; 
      List<Node> result = FindWayFrom(node, dstNode, way, visitedNodes); 

      if (result != null) 
       return result; 

      //It is not the correct way. Remove current changeset. 
      way.Remove(node); 
     } 
     return null; 
    } 

Answer 1

はこれを実装する簡単な試みです。私はそれを徹底的にテストしていませんが、パスが存在しない、パスが存在し、ループが存在し、すべてが有効な結果を返しました。

トリッキーな部分（概念的には）は、現在降りている子パスを追跡することです。私はこれをFrame.NextChildに保存します。

更新：コードをリファクタリングしました。メインループは非常にシンプルで、2つの主なコンセプト（下降とバックトラッキング）は別々のメソッドでうまくカプセル化されています。

Answer 2

これを行うための最も一般的な方法は、あなたが必要とする反復

Way to go from recursion to iteration

Answer 3

の内側には、関数呼び出しを作っていたかのように、スタックにオブジェクトをプッシュすると、そのスタック上で動作させることですルーチンを再帰的に呼び出す代わりにスタックを使用すること。

ルーチン全体にwhileループを配置して、ローカルスタックに項目がポップされているかどうかを確認します。

メソッドを呼び出している行が、その詳細をスタックにプッシュします。

ルーチンの開始時に、着信メソッドの詳細をプッシュします。

Answer 4

私はあなたのNodeクラス

public class Node 
{ 
    ...... 
    public Node PrevInPath{get;set;} 
    public bool Visited {get;set;} 
} 

と（私はあなたがソースから宛先へのパスを見つけたいと思います）に代を追加します、私は単にそれを見つけるためにキューを使用することをお勧め、また、あなたはあなたを向上させる必要がありますデータ構造は、現在お使いのデータ構造は非常に貧弱であり、あなたが関数型言語（ないC＃の）のコードようだ：

private List<Node> FindWayFrom(
     Node srcNode, 
     Node dstNode, 
     Graph graph) 
    { 

     foreach(var node in graph) 
     node.Visited = false; 

    Queue<Node> Q = new Queue<Node>(); 
    srcNode.PrevInPath = null; 
    srcNode.Visited = true; 
    Q.Enqueue(srcNode); 

    while(Q.Count()>0) 
    { 
     var currNode = Q.Dequeue(); 
     if (currNode == destNode) 
     break; 

     foreach(var node in currNode.Adjacent) 
     { 
      if (node.Visited == false) 
      { 
       node.Visited = true; 
       node.PrevInPath = currNode; 
      } 
     } 

    } 

    if (destNode.Visited) 
    { 
     var path = List<Node>(); 
     var currNode = destNode; 
     while (currNode != srcNode) 
     { 
      path.Add(currNode); 
      currNode = currNode.PrevInPath; 
     } 
     return path.Reverse().ToList(); 
    } 
    return null; 
} 

コードがテストされていないかもしれコンパイルエラーを持っているし、可能な限り効率的ではありませんが、単純に固定可能ですしかし、Ideaはキューを使用しており、vi現在の作成されたパスについての情報を持っているべきであるパスを追跡するために、そしてそれを出力するために逆方向に進むためにも、sitedノード。

public static class Router 
{ 
    private class Frame 
    { 
    public Frame(Node node) 
    { 
     Node = node; 
     NextChild = 0; 
    } 

    internal Node Node { get; private set; } 
    internal int NextChild { get; set; } 
    } 

    /// <summary> 
    /// Finds a (but not necessarily the shortest) route from <paramref name="source" /> 
    /// to <paramref name="destination" />. 
    /// </summary> 
    /// <param name="source"> Source node </param> 
    /// <param name="destination"> Destination node </param> 
    /// <returns> A list of nodes that represents the path from 
    /// <paramref name="source" /> to <paramref name="destination" /> , including both 
    /// <paramref name="source" /> and <paramref name="destination" /> . If no such path 
    /// exists, <c>null</c> is returned. 
    /// </returns> 
    public static IList<Node> FindFirstRoute(Node source, Node destination) 
    { 
    var visited = new HashSet<Node>(); 
    var path = new Stack<Frame>(); 
    path.Push(new Frame(source)); 
    var frame = path.Peek(); 

    while (frame != null) 
    { 
     if (frame.Node == destination) 
     { 
     return path.Select(x => x.Node).Reverse().ToList(); 
     } 

     if (!visited.Add(frame.Node) || !DescendToNextChild(path, out frame)) 
     { 
     frame = Backtrack(path); 
     } 
    } 

    return null; 
    } 

    /// <summary> 
    /// Attempts to move to the next child of the node on top of the stack. 
    /// </summary> 
    /// <param name="path"> Current path </param> 
    /// <param name="nextFrame"> Receives the new top frame in the path. If all children 
    /// have already been explored, <paramref name="nextFrame" /> is set to <c>null</c> 
    /// </param> 
    /// <returns> <c>true</c> if descending was successful, that is, if the current top 
    /// frame has any unexplored children left; otherwise, <c>false</c>. 
    /// </returns> 
    private static bool DescendToNextChild(Stack<Frame> path, out Frame nextFrame) 
    { 
    var topFrame = path.Peek(); 
    var children = topFrame.Node.Children; 
    if (children != null && children.Length > topFrame.NextChild) 
    { 
     var child = children[topFrame.NextChild++]; 
     path.Push(nextFrame = new Frame(child)); 
     return true; 
    } 
    nextFrame = null; 
    return false; 
    } 

    /// <summary> 
    /// Backtracks from the path until a frame is found where there is an unexplored 
    /// child left if such a frame exists. 
    /// </summary> 
    /// <param name="path"> The path to backtrack from. </param> 
    /// <returns> 
    /// The next frame to investigate, which is represents the first unexplored 
    /// child of the node closest to the top of the stack which has any unexplored 
    /// children left. If no such a frame exists <c>null</c> is returned and the search 
    /// should be stopped. 
    /// </returns> 
    private static Frame Backtrack(Stack<Frame> path) 
    { 
    Frame nextFrame = null; 
    do 
    { 
     path.Pop(); 
    } 
    while (path.Count > 0 && !DescendToNextChild(path, out nextFrame)); 

    return nextFrame; 
    } 
} 

それは素敵な脳の体操と歓迎気晴らしだった：ここ