Récursive expression lambda pour trouver le chemin (s) par un graphe orienté?

Question

Je dois trouver un chemin ou les chemins vers le bas d'une structure graphique compliquée. Le graphique est construit en utilisant quelque chose de similaire à ceci:

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

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

Ce qui rend ce complexe est que les noeuds peuvent faire référence à nouveau à un nœud plus tôt. Par exemple,

  

A -> C -> E -> A

Ce que je dois faire est d'obtenir une liste des piles qui représentent des chemins à travers les nœuds jusqu'à ce que je à un nœud avec une valeur spécifique. Depuis son possible, il peut y avoir des chemins très importants disponibles, nous pouvons avoir un maximum de nœuds pour essayer.

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

Quelqu'un at-il un moyen de construire ce (ou quelque chose de similaire)? Je l'ai fait récursion dans le passé mais je vais avoir un fart total du cerveau penser à cela pour une raison quelconque. Ma question a spécifié une expression lambda mais en utilisant un lambda est pas forcément nécessaire. Je serais reconnaissant de toute solution.

Side note: Je relevai la classe d'une excellente réponse pour aku cette question récursion . Alors que sa solution élégante ci-dessous traverse la structure de l'arbre, il ne semble pas permettre une flexibilité suffisante pour faire ce que je dois (par exemple, rejeter les chemins qui sont des chemins circulaires et le suivi qui réussissent).

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

Modifier :

D'après les commentaires des commentaires et réponses ci-dessous j'ai trouvé une excellente solution plus dans CodeProject. Il utilise le chemin A * algorithme de recherche. Voici le lien.

Answer 1

Si vous êtes problème est lié à pathfinding, vous pouvez google pour « Une étoile » ou « A * ». Son un algorithme de pathfinding commun et efficace. Voir cet article un exemple directement lié à votre problème.

Vous pouvez également regarder le Dijkstra algorithme

Answer 2

Je ne suis pas sûr que votre sortie prévue est tous chemins vers le but, le meilleur chemin vers l'objectif (par une mesure, par exemple, la longueur du trajet), ou juste tout chemin à l'objectif.

En supposant que ce dernier, je commencerai par la stratégie récursive, y compris le suivi des nœuds visités comme indiqué par Brann, et faire ces changements:

1. Ajouter des paramètres pour représenter le but recherché, la collection de chemins réussis, et le chemin courant depuis le début.

2. Lorsque vous entrez dans un nœud qui correspond à l'objectif, ajoutez le chemin courant (plus le nœud courant) à la liste des chemins réussis.

3. Elargir le trajet de courant avec le noeud courant pour créer le chemin d'accès transmis tous les appels récursifs.

4. Invoque l'appel ExploreGraph initial avec un chemin vide et une liste vide de chemins réussis.

Une fois terminé, votre algorithme aura traversé le graphe entier et chemins distincts à l'objectif aura été capturé.

C'est juste un croquis rapide, mais vous devriez être en mesure de l'étoffer pour vos besoins spécifiques.

Answer 3

Je ne sais pas exactement ce que vous voulez atteindre, mais ce problème de référence circulaire est habituellement résolu par le marquage des noeuds déjà visités. Il suffit d'utiliser un Dictionnary pour garder la trace des noeuds qui ont déjà été visités afin que vous ne boucle pas.

Exemple:

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