espressione lambda ricorsiva per trovare il percorso (s) tramite un grafo orientato?

Question

Ho bisogno di trovare un percorso o percorsi lungo una complicata struttura di grafo. Il grafico è costruito utilizzando qualcosa di simile a questo:

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

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

Ciò che rende questo complicato è che i nodi possono fare riferimento ad un nodo precedente. Ad esempio,

  

A -> C -> E -> A

Che cosa devo fare è ottenere una lista di pile che rappresentano i percorsi attraverso i nodi fino a ottenere un nodo con un valore specifico. Dal momento che la sua possibile ci possono essere alcuni molto grandi percorsi a disposizione siamo in grado di avere un massimo di nodi da provare.

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

Qualcuno ha un modo per costruire questo (o qualcosa di simile)? Ho fatto la ricorsione in passato, ma sto avendo un peto totale del cervello a pensare a questo per qualche motivo. La mia domanda specifica un'espressione lambda ma utilizzando un lambda non è necessariamente richiesta. Sarei grato per qualsiasi soluzione.

Nota a margine: ho alzato la classe da ottima risposta di AKU per questo ricorsione domanda . Mentre la sua soluzione elegante mostrato sotto attraversa la struttura ad albero non sembra per consentire una flessibilità sufficiente per fare quello che mi serve (per esempio, respingere percorsi che sono circolari e tracciare i percorsi che hanno avuto successo).

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

Modifica :

Sulla base di input dai commenti e le risposte di seguito ho trovato una soluzione eccellente sopra in CodeProject. Esso utilizza il percorso A * algoritmo di ricerca. Ecco il link.

Answer 1

Se stai problema è legato alla Pathfinding, si consiglia di Google per "Una stella" o "A *". Il suo un algoritmo pathfinding comune ed efficiente. Vedere questo articolo per un esempio direttamente correlata al vostro problema.

Si potrebbe anche voler guardare Dijsktra Algoritmo il

Answer 2

Non sono sicuro se l'output previsto è tutti percorsi per il gol, il migliore percorso verso la meta (da qualche metrica, ad esempio lunghezza del percorso), o solo qualsiasi percorso verso l'obiettivo.

Supponendo che questi ultimi, mi piacerebbe iniziare con la strategia ricorsiva, tra cui il monitoraggio dei nodi visitati come sottolineato dal Brann, e apportare queste modifiche:

1. Aggiungi parametri per rappresentare l'obiettivo di essere ricercato, la raccolta di percorsi di successo, e il percorso corrente dall'inizio.

2. Quando si entra in un nodo che corrisponde l'obiettivo, aggiungere il percorso corrente (più il nodo corrente) per l'elenco dei percorsi di successo.

3. estendere il percorso corrente con il nodo corrente per creare il percorso trasmesso chiamate ricorsive.

4. Invoke chiamata ExploreGraph iniziale con un percorso vuoto e un elenco vuoto di percorsi di successo.

Al termine, il vostro algoritmo avranno attraversato l'intero grafico e percorsi distinti per l'obiettivo sarà stato catturato.

Questo è solo un rapido schizzo, ma si dovrebbe essere in grado di carne fuori per le vostre esigenze specifiche.

Answer 3

Non so esattamente che cosa si vuole raggiungere, ma questo problema di riferimento circolare è di solito risolto etichettando i nodi già visitati. Basta usare un Dictionnary per tenere traccia dei nodi che sono già stati visitati in modo che non si ciclo.

Esempio:

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