expressão lambda recursiva para encontrar o caminho (s) através de um grafo orientado?

Question

Eu preciso encontrar um caminho ou caminhos para baixo uma estrutura gráfico complicado. O gráfico é construído usando algo semelhante a isto:

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

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

O que torna este complicado é que os nós podem referenciar de volta um nó anterior. Por exemplo,

-> C -> E -> A

O que eu preciso fazer é obter uma lista de pilhas que representam caminhos através dos gânglios até eu chegar a um nó com um valor específico. Desde a sua possível pode haver algumas muito grandes caminhos disponíveis que podem ter um máximo de nós para tentar.

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

Alguém tem uma maneira de construir este (ou algo similar)? Eu fiz a recursividade no passado, mas eu estou tendo um pensamento total de peido de cérebro sobre isso por algum motivo. A minha pergunta especificada uma expressão lambda, mas usando um lambda não é necessariamente obrigatório. Eu ficaria grato por qualquer solução.

Nota lateral: Eu levantei a classe de excelente resposta das aku para este recursão questão . Enquanto sua solução elegante mostrado abaixo atravessa a estrutura da árvore não parece permitir a flexibilidade suficiente para fazer o que eu preciso (por exemplo, descartar caminhos que são circular e seguir caminhos que são bem sucedidos).

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

Editar :

Com base nas informações dos comentários e respostas abaixo eu achei uma excelente solução sobre em CodeProject. Ele usa o algoritmo A * Encontrando o trajeto. Aqui está o link.

Answer 1

Se você é problema está relacionado com Pathfinding, você pode querer google para "estrela Um" ou "A *". É um comum e algoritmo de pathfinding eficiente. Consulte este artigo para um exemplo diretamente relacionada ao seu problema.

Você também pode querer olhar para o Dijsktra Algoritmo

Answer 2

Eu não tenho certeza se o seu resultado pretendido é todas caminhos para a meta, o melhor caminho para o gol (por alguma métrica, por exemplo, comprimento do caminho), ou apenas qualquer caminho para o gol.

Assumindo que o último, eu começaria com a estratégia recursivo, incluindo rastreamento de nós visitados conforme descrito pelo Brann, e fazer essas alterações:

1. Adicionar parâmetros para representar a meta a ser procurado, a coleção de caminhos de sucesso, e o caminho atual desde o início.

2. Ao entrar em um nó que corresponde à meta, adicione o caminho atual (mais o nó atual) para a lista de caminhos de sucesso.

3. Estender o caminho atual com o nó atual para criar o caminho repassado todas as chamadas recursivas.

4. invocar a chamada ExploreGraph inicial com um caminho vazio e uma lista vazia de caminhos de sucesso.

Após a conclusão, o algoritmo irá ter atravessado o gráfico inteiro e caminhos distintos para a meta terá sido capturado.

Isso é apenas um esboço rápido, mas você deve ser capaz de completá-lo para as suas necessidades específicas.

Answer 3

Eu não sei exatamente o que você quer alcançar, mas este problema de referência circular normalmente é resolvido por marcação nós já visitados. Basta usar um Dictionnary para acompanhar os nós que já foram visitados para que você não fazer loop.

Exemplo:

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