递归 lambda 表达式通过有向图查找路径?
-
29-08-2019 - |
题
我需要在复杂的图形结构中找到一条或多条路径。该图是使用与此类似的东西构建的:
class Node
{
public string Value { get; set;}
public List<Node> Nodes { get; set;}
public Node()
{
Nodes = new List<Node>();
}
}
使事情变得复杂的是节点可以引用回较早的节点。例如,
A -> C -> E -> A
我需要做的是获取一个堆栈列表,这些堆栈表示通过节点的路径,直到到达具有特定值的节点。由于可能存在一些非常大的路径可用,因此我们可以尝试最多的节点。
List<Stack<Node>> paths = FindPaths(string ValueToFind, int MaxNumberNodes);
有谁有办法构建这个(或类似的东西)?我过去曾做过递归,但出于某种原因,我在思考这个问题时脑子里全是放屁。我的问题指定了 lambda 表达式,但不一定需要使用 lambda。我将不胜感激任何解决方案。
边注:我从 aku 的优秀答案中提升了课程 这道递归题. 。虽然他下面显示的优雅的解决方案遍历了树结构,但它似乎没有足够的灵活性来完成我需要的操作(例如,忽略圆形路径并跟踪成功的路径)。
Action<Node> traverse = null;
traverse = (n) => { Console.WriteLine(n.Value); n.Nodes.ForEach(traverse);};
traverse(root); // where root is the tree structure
编辑:
根据下面的评论和答案,我在 CodeProject 中找到了一个出色的解决方案。它使用A*寻路算法。 链接在这里。
解决方案
如果你的问题是关系到寻路,你可能想谷歌的“造星”或“A *”。 它是一种常见的,高效的寻路算法。请参见这篇文章直接关系到你的问题的例子。
您可能也想看看 Dijsktra算法
其他提示
我不确定你的预期输出是否是 全部 通往目标的路径, 最好的 实现目标的路径(通过某些指标,例如路径长度),或者只是 任何 通往目标的道路。
假设是后者,我将从递归策略开始,包括跟踪 Brann 概述的访问节点,并进行以下更改:
添加参数来表示正在寻求的目标、成功路径的集合以及从一开始的当前路径。
当输入与目标匹配的节点时,将当前路径(加上当前节点)添加到成功路径列表中。
使用当前节点扩展当前路径以创建在任何递归调用上传递的路径。
调用初始
ExploreGraph
使用空路径和空的成功路径列表进行调用。
完成后,您的算法将遍历整个图表,并且将捕获到达目标的不同路径。
这只是一个快速的草图,但您应该能够根据您的特定需求充实它。
我不知道到底要达到什么样的,但这种循环引用问题通常是通过标记已访问节点解决。 只需使用一个Dictionnary保持已访问过的节点的轨道,让你不循环。
示例:
public void ExploreGraph(TreeNode tn, Dictionary<TreeNode, bool> visitednodes)
{
foreach (Treenode childnode in tn.Nodes)
{
if (!visitedNodes.ContainsKey(childnode))
{
visitednodes.Add(childnode);
ExploreGraph(childnode, visitednodes);
}
}
}