4

我需要在复杂的图形结构中找到一条或多条路径。该图是使用与此类似的东西构建的：

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* 路径查找算法。 链接在这里。

4

3 回答 3

5

如果您的问题与寻路有关，您可能需要在 Google 上搜索“A 星”或“A*”。它是一种通用且高效的寻路算法。有关与您的问题直接相关的示例，请参阅本文。

您可能还想查看Dijsktra 算法

于 2008-12-28T20:48:40.873 回答
1

我不确定您的预期输出是通向目标的所有路径、通向目标的最佳路径（通过某些度量，例如路径长度），还是通向目标的任何路径。

假设是后者，我将从递归策略开始，包括跟踪 Brann 概述的访问节点，并进行以下更改：

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

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

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

  4. ExploreGraph使用空路径和成功路径的空列表调用初始调用。

完成后，您的算法将遍历整个图，并且将捕获到目标的不同路径。

这只是一个速写，但您应该能够根据您的特定需求对其进行充实。

于 2008-12-28T20:50:59.043 回答
0

我不确切知道你想要实现什么，但是这个循环引用问题通常是通过标记已经访问过的节点来解决的。只需使用字典来跟踪已经访问过的节点，这样您就不会循环。

例子 ：

  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);
                }
            }
        }
于 2008-12-28T17:19:53.803 回答