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

誰かがこれを構築する方法を持っていますか (または同様のもの)? 私は過去に再帰を行ったことがありますが、何らかの理由でこれについて考えて、完全に脳のおならをしています。私の質問はラムダ式を指定しましたが、ラムダの使用は必ずしも必要ではありません。どんな解決策にも感謝します。

補足:この再帰の質問に対する 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

問題がパスファインディングに関連している場合は、「A star」または「A*」でググることができます。これは、一般的で効率的な経路探索アルゴリズムです。問題に直接関連する例については、この記事を参照してください。

Dijsktra Algorithmも参照してください。

于 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 に答える