¿Expresión lambda recursiva para encontrar las rutas a través de un gráfico dirigido?

Question

Necesito encontrar una ruta o rutas a lo largo de una estructura gráfica complicada.El gráfico se construye usando algo similar a esto:

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

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

Lo que complica esto es que los nodos pueden hacer referencia a un nodo anterior.Por ejemplo,

A->C->E->A

Lo que necesito hacer es obtener una lista de pilas que representan rutas a través de los nodos hasta llegar a un nodo con un valor específico.Dado que es posible que haya rutas muy grandes disponibles, podemos tener un máximo de nodos para probar.

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

¿Alguien tiene una manera de construir esto (o algo similar)?He hecho recursividad en el pasado, pero por alguna razón me estoy volviendo loco al pensar en esto.Mi pregunta especificaba una expresión lambda, pero no es necesariamente necesario utilizarla.Agradecería cualquier solución.

Nota al margen:Levanté la clase de la excelente respuesta de aku para esta pregunta de recursividad.Si bien la elegante solución que se muestra a continuación atraviesa la estructura de árbol, no parece permitir suficiente flexibilidad para hacer lo que necesito (por ejemplo, descartar rutas circulares y rastrear rutas exitosas).

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

Editar:

Según los comentarios y respuestas a continuación, encontré una excelente solución en CodeProject.Utiliza el algoritmo de búsqueda de ruta A*. Aqui esta el link.

Answer 1

Si usted es problema está relacionado con Pathfinding, es posible que desee en Google de "Una estrella" o "A *". Su algoritmo de búsqueda de caminos comunes de una y eficiente. Ver este artículo para un ejemplo directamente relacionado con su problema.

También es posible que desee ver en la Dijsktra Algoritmo

Answer 2

No estoy seguro de si el resultado previsto es todo caminos hacia la meta, el mejor camino hacia la meta (por alguna métrica, p.e.longitud del camino), o simplemente cualquier camino hacia la meta.

Suponiendo esto último, comenzaría con la estrategia recursiva, incluido el seguimiento de los nodos visitados como lo describe Brann, y realizaría estos cambios:

1. Agregue parámetros para representar el objetivo que se busca, la colección de caminos exitosos y el camino actual desde el principio.

2. Al ingresar a un nodo que coincida con el objetivo, agregue la ruta actual (más el nodo actual) a la lista de rutas exitosas.

3. Extienda la ruta actual con el nodo actual para crear la ruta pasada en cualquier llamada recursiva.

4. Invocar la inicial ExploreGraph Llame con una ruta vacía y una lista vacía de rutas exitosas.

Al finalizar, su algoritmo habrá recorrido todo el gráfico y se habrán capturado distintos caminos hacia el objetivo.

Esto es sólo un boceto rápido, pero deberías poder desarrollarlo según tus necesidades específicas.

Answer 3

No sé exactamente lo que quiere lograr, pero este problema referencia circular suele ser resuelto mediante el etiquetado de los nodos ya visitados. Sólo tiene que utilizar un Dictionnary para realizar un seguimiento de los nodos que ya han sido visitados por lo que no lo hace bucle.

Ejemplo:

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