递归 lambda 表达式通过有向图查找路径？

StackOverflow https://stackoverflow.com/questions/396296

  •  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 概述的访问节点，并进行以下更改：

  1. 添加参数来表示正在寻求的目标、成功路径的集合以及从一开始的当前路径。

  2. 当输入与目标匹配的节点时，将当前路径（加上当前节点）添加到成功路径列表中。

  3. 使用当前节点扩展当前路径以创建在任何递归调用上传递的路径。

  4. 调用初始 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);
                }
            }
        }
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top