Преобразование этого метода из рекурсивного в итеративный

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

Вот быстрая попытка осуществить это:

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; 
    } 
} 

Это был хороший тизер мозга и желанным развлечением. Хотя я не тестировал его полностью, я запускал разные сценарии: нет пути, существует путь, существует цикл, все они вернули действительный результат.

Трудная часть (концептуально) заключается в том, чтобы отслеживать, к какому пути ребенка вы входите. Я храню это в Frame.NextChild.

Обновление: я переработал код. Основной цикл теперь очень прост, и две основные концепции (спуск и возврат) теперь прекрасно инкапсулированы отдельными методами.

Answer 2

Самый распространенный способ сделать это, чтобы толкать объекты в стек, как если бы вы делали вызов функции, и работать на этом стеке внутри итерации

Way to go from recursion to iteration

Answer 3

Вам нужно использовать стек вместо вызова процедуры recusivly.

Поместите цикл while вокруг всей процедуры, чтобы проверить, есть ли у вашего локального стека элементы, если он всплывает.

Линия, в которой вы вызываете метод, снова вставляет эти данные в стек.

В начале процедуры введите данные входящего метода.

Answer 4

Я добавлю Somethings к вашему 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 node, также для отслеживания пути, который должен иметь некоторую информацию о текущем созданном пути, а затем назад, чтобы вывести его.