将此方法从递归转换为迭代
本文关键字:迭代 转换 递归 此方法 | 更新日期: 2023-09-27 18:27:05
我有以下递归方法,但由于列表太长,我得到了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;
}
以下是实现此功能的快速尝试:
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
中。
更新:我已经重构了代码。主循环现在非常简单,两个主要概念(下降和回溯)现在被很好地封装在单独的方法中。
我会为您的Node
类添加一些内容
public class Node
{
......
public Node PrevInPath{get;set;}
public bool Visited {get;set;}
}
而且(我认为你想找到一条从源到目的地的路径),我建议使用Queue简单地找到它,你也应该改进你的数据结构,目前你的数据架构很差,似乎你用函数语言(而不是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正在使用队列,并标记访问的节点,也用于跟踪路径。您应该有一些关于当前创建的路径的信息,然后返回输出。
最常见的方法是像调用函数一样将对象推送到堆栈中,并在迭代中对该堆栈进行操作
从递归到迭代的方法
您需要使用堆栈,而不是调用例程recisivly。
在整个例程周围放置一个while循环,以检查本地堆栈是否有项目(如果它确实弹出了项目)。
再次调用该方法的行将这些细节推送到堆栈中。
在例程开始时,推送传入的方法详细信息。