Rekursive Lambda-Ausdruck den Pfad (n) durch einen gerichteten Graphen zu finden?

Question

Ich brauche einen Pfad oder Pfade hinunter einer komplizierten Graphenstruktur zu finden. Die Grafik ist etwas ähnlich wie diese aufgebaut werden:

class Node
{
    public string Value { get; set;}
    public List<Node> Nodes { get; set;}

    public Node()
    {
        Nodes = new List<Node>();
    }
}

Was macht diese kompliziert ist, dass die Knoten zu einem früheren Knoten verweisen zurück kann. Zum Beispiel:

  

A -> C -> E -> A

Was ich tun muß, ist eine Liste des Stapels zu erhalten, die Pfade durch die Knoten darstellen, bis ich zu einem Knoten mit einem bestimmten Wert zu erhalten. Seit seiner möglich kann es einige sehr große Wege zur Verfügung stehen wir maximal Knoten haben kann, um zu versuchen.

List<Stack<Node>> paths = FindPaths(string ValueToFind, int MaxNumberNodes);

Hat jemand eine Möglichkeit, dies (oder so ähnlich) zu bauen? Ich habe Rekursion in der Vergangenheit getan, aber ich bin insgesamt Gehirn Furz darüber aus irgendeinem Grunde denken zu müssen. Meine Frage einen Lambda-Ausdruck angegeben, aber eine Lambda verwendet, ist nicht unbedingt erforderlich. Ich würde für jede Lösung dankbar sein.

Randbemerkung: Ich hob die Klasse von aku der ausgezeichneten Antwort diese Rekursion Frage . Während seine elegante Lösung unten durchquert die Baumstruktur angezeigt scheint es nicht genug Flexibilität zu ermöglichen, zu tun, was ich brauche (zB entlassen Pfade, die kreisförmig sind und verfolgen Pfade, die erfolgreich sind).

Action<Node> traverse = null;
traverse = (n) => { Console.WriteLine(n.Value); n.Nodes.ForEach(traverse);};
traverse(root);  // where root is the tree structure

Bearbeiten :

Aufgrund der Erfahrungen aus den Kommentaren und Antworten unter ich eine hervorragende Lösung über in Codeproject gefunden. Es nutzt die A * Pathfinding Algorithmus. Hier ist der Link.

Answer 1

Wenn Sie Problem Pathfinding verwandt ist, können Sie für „Ein Stern“ oder „A *“ to google wollen. Es ist eine gemeinsame und effiziente Wegfindung Algorithmus. Siehe dieser Artikel für ein Beispiel direkt im Zusammenhang mit Ihrem Problem.

Sie können auch auf die Dijsktra Algorithmus

Answer 2

Ich bin nicht sicher, ob Ihre beabsichtigte Ausgabe ist alle Wege zum Ziel, die am besten Weg zum Ziel (durch eine Metrik, zB Weglänge) oder nur jeder Weg zum Ziel.

letzteres Unter der Annahme, würde ich mit der rekursiven Strategie beginnen, von besuchten Knoten einschließlich Tracking, wie Brann skizzierte, und diese Änderungen vornehmen:

1. Parameter hinzufügen, das Ziel zu stellen gesucht, die Sammlung von erfolgreichen Pfaden und der Strompfad von Anfang an.

2. Wenn ein Knoten eintreten, die das Ziel übereinstimmt, fügen Sie den Strompfad (plus den aktuellen Knoten) in die Liste der erfolgreichen Pfade.

3. Erweitern Sie den Strompfad mit dem aktuellen Knoten den Pfad auf irgendwelchen rekursive Aufrufe.

übergeben erstellen

4. Rufen Sie die Anfangs ExploreGraph Anruf mit einem leeren Pfad und eine leere Liste der erfolgreichen Pfade.

Nach der Fertigstellung wird hat Ihr Algorithmus das gesamte Graphen durchlaufen, und verschiedene Wege zum Ziel werden erfaßt wurden.

Das ist nur eine schnelle Skizze, aber man sollte es um Fleisch aus der Lage sein, für Ihre spezifischen Bedürfnisse.

Answer 3

Ich weiß nicht genau, was Sie erreichen wollen, aber diese kreisförmige Referenz Problem in der Regel durch Tagging bereits besuchten Knoten gelöst. Verwenden Sie einfach ein Dictionnary Spur der Knoten zu halten, die bereits besucht wurden, so dass Sie nicht in einer Schleife zu tun.

Beispiel:

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