Encontre todos os caminhos possíveis de um vértice em um grafo cíclico direcionado em Erlang

StackOverflow https://stackoverflow.com/questions/7834702

Pergunta

Eu gostaria de implementar uma função que encontre todos os caminhos possíveis para todos os vértices possíveis de um vértice de origem V em um grafo cíclico direcionado G.

O desempenho não importa agora, eu só gostaria de entender o algoritmo. Eu li a definição do algoritmo de pesquisa de profundidade, mas não tenho total compreensão do que fazer.

Não tenho nenhum pedaço de código completo para fornecer aqui, porque não tenho certeza de como:

  • armazene os resultados (junto com A-> B-> C-> devemos também armazenar A-> B e A-> B-> C);
  • representa o gráfico (dígrafo? lista de tuplas?);
  • quantas recursões usar (trabalhar com cada vértice adjacente?).

Como posso encontrar todos os caminhos possíveis de um determinado vértice de origem em um grafo cíclico direcionado em Erlang?

UPD: com base nas respostas até agora, tenho que redefinir a definição do gráfico: é um gráfico não acíclico. Eu sei que se minha função recursiva atinge um ciclo, é um loop indefinido. Para evitar isso, posso apenas verificar se um vértice atual está na lista do caminho resultante - se sim, paro de percorrer e retorno o caminho.

UPD2: Obrigado por comentários instigantes! Sim, preciso encontrar todos os caminhos simples que não têm loops de um vértice de origem para todos os outros.

Em um gráfico como este:

Non-acyclic graph

com o vértice de origem A, o algoritmo deve encontrar os seguintes caminhos:

  • A, B
  • A, B, C
  • A, B, C, D
  • A, D
  • A, D, C
  • A, D, C, B

O código a seguir faz o trabalho, mas não pode ser usado em gráficos com mais de 20 vértices (acho que é algo errado com a recursão - ocupa muita memória, nunca termina): 

dfs(Graph,Source) ->
    ?DBG("Started to traverse graph~n", []),
            Neighbours = digraph:out_neighbours(Graph,Source),
    ?DBG("Entering recursion for source vertex ~w~n", [Source]),
            dfs(Neighbours,[Source],[],Graph,Source),
ok.


dfs([],Paths,Result,_Graph,Source) ->
    ?DBG("There are no more neighbours left for vertex ~w~n", [Source]),
    Result;

dfs([Neighbour|Other_neighbours],Paths,Result,Graph,Source) ->
    ?DBG("///The neighbour to check is ~w, other neighbours are: ~w~n",[Neighbour,Other_neighbours]),
    ?DBG("***Current result: ~w~n",[Result]),
    New_result = relax_neighbours(Neighbour,Paths,Result,Graph,Source),

        dfs(Other_neighbours,Paths,New_result,Graph,Source).


relax_neighbours(Neighbour,Paths,Result,Graph,Source) ->
     case lists:member(Neighbour,Paths) of 
        false ->
            ?DBG("Found an unvisited neighbour ~w, path is: ~w~n",[Neighbour,Paths]),
            Neighbours = digraph:out_neighbours(Graph,Neighbour),
            ?DBG("The neighbours of the unvisited vertex ~w are ~w, path is:
                ~w~n",[Neighbour,Neighbours,[Neighbour|Paths]]),
                dfs(Neighbours,[Neighbour|Paths],Result,Graph,Source);
            true ->
                [Paths|Result]

        end.

O problema é que o algoritmo regular de pesquisa em profundidade primeiro irá um dos caminhos para primeiro: (A, B, C, D) ou (A, D, C, B) e nunca irá para o segundo caminho.

Em qualquer dos casos, será o único caminho - por exemplo, quando o DFS regular retrocede de (A, B, C, D), ele volta para A e verifica se D (o segundo vizinho de A) é visitado . E uma vez que o DFS regular mantém um estado global para cada vértice, D teria o estado "visitado".

Portanto, temos que introduzir um estado dependente da recursão - se voltarmos de (A, B, C, D) até A, devemos ter (A, B, C, D) na lista de resultados e devemos marcar D como não visitado no início do algoritmo.

Eu tentei otimizar a solução para a cauda recursiva, mas ainda assim o tempo de execução do algoritmo é inviável - leva cerca de 4 segundos para percorrer um pequeno gráfico de 16 vértices com 3 arestas por vértice: 

dfs(Graph,Source) ->
    ?DBG("Started to traverse graph~n", []),
            Neighbours = digraph:out_neighbours(Graph,Source),
    ?DBG("Entering recursion for source vertex ~w~n", [Source]),
    Result = ets:new(resulting_paths, [bag]),
Root = Source,
            dfs(Neighbours,[Source],Result,Graph,Source,[],Root).


dfs([],Paths,Result,_Graph,Source,_,_) ->
    ?DBG("There are no more neighbours left for vertex ~w, paths are ~w, result is ~w~n", [Source,Paths,Result]),
    Result;

dfs([Neighbour|Other_neighbours],Paths,Result,Graph,Source,Recursion_list,Root) ->
    ?DBG("~w *Current source is ~w~n",[Recursion_list,Source]),
    ?DBG("~w Checking neighbour _~w_ of _~w_, other neighbours are: ~w~n",[Recursion_list,Neighbour,Source,Other_neighbours]),



?    DBG("~w Ready to check for visited: ~w~n",[Recursion_list,Neighbour]),

 case lists:member(Neighbour,Paths) of 
        false ->
            ?DBG("~w Found an unvisited neighbour ~w, path is: ~w~n",[Recursion_list,Neighbour,Paths]),
New_paths = [Neighbour|Paths],
?DBG("~w Added neighbour to paths: ~w~n",[Recursion_list,New_paths]),
ets:insert(Result,{Root,Paths}),

            Neighbours = digraph:out_neighbours(Graph,Neighbour),
            ?DBG("~w The neighbours of the unvisited vertex ~w are ~w, path is: ~w, recursion:~n",[Recursion_list,Neighbour,Neighbours,[Neighbour|Paths]]),
                dfs(Neighbours,New_paths,Result,Graph,Neighbour,[[[]]|Recursion_list],Root);
            true -> 
            ?DBG("~w The neighbour ~w is: already visited, paths: ~w, backtracking to other neighbours:~n",[Recursion_list,Neighbour,Paths]),
ets:insert(Result,{Root,Paths})

end,

        dfs(Other_neighbours,Paths,Result,Graph,Source,Recursion_list,Root).

Alguma ideia para executar isso em um tempo aceitável?

Foi útil?

Solução

Editar: Ok, eu entendo agora, você deseja encontrar todos os caminhos simples de um vértice em um gráfico direcionado. Portanto, uma pesquisa em profundidade com retrocesso seria adequada, como você percebeu. A ideia geral é ir a um vizinho, depois ir a outro (não aquele que você já visitou) e continuar até chegar a um beco sem saída. Em seguida, volte ao último vértice em que você estava e escolha um vizinho diferente, etc. Você precisa acertar as partes complicadas, mas não deve ser muito difícil. Por exemplo. a cada etapa, você precisa rotular os vértices como 'explorados' ou 'inexplorados', dependendo se você já os visitou antes. O desempenho não deve ser um problema, um algoritmo implementado corretamente deve levar talvez O (n ^ 2) tempo. Então eu não sei o que você está fazendo de errado, talvez você esteja visitando muitos vizinhos? Por exemplo. talvez você esteja revisitando vizinhos que já visitou e dando voltas ou algo assim.

Na verdade, não li seu programa, mas a página do Wiki em Pesquisa em profundidade tem um programa em pseudocódigo simples e curto que você pode tentar copiar em seu idioma. Armazene os gráficos como listas de adjacências para facilitar.

Editar: Sim, desculpe, você está certo, a pesquisa DFS padrão não funcionará como está, você precisa ajustá-la ligeiramente para revisitar os vértices que visitou antes. Portanto, você tem permissão para visitar qualquer vértice, exceto aqueles que você já armazenou no caminho atual. Isso, é claro, significa que meu tempo de execução estava completamente errado, a complexidade do seu algoritmo aumentará. Se a complexidade média de seu gráfico for d + 1, haverá aproximadamente d * d * d * ... * d= d ^ n caminhos possíveis. Portanto, mesmo que cada vértice tenha apenas 3 vizinhos, ainda haverá alguns caminhos quando você passar de 20 vértices. Na verdade, não há maneira de contornar isso, porque se você quiser que seu programa produza todos os caminhos possíveis, então, de fato, você terá que dar saída a todos eles.

Estou interessado em saber se você precisa disso para uma tarefa específica ou se está apenas tentando programar por interesse. Se for o último, você apenas terá que se contentar com gráficos pequenos e esparsamente conectados.

Outras dicas

Não entendo a pergunta. Se eu tiver o gráfico G= (V, E)= ({A, B}, {(A, B), (B, A)}), há caminhos infinitos de A para B {[A, B], [ A, B, A, B], [A, B, A, B, A, B], ...}. Como posso encontrar todos os caminhos possíveis para qualquer vértice no grafo cíclico?

Editar:

Você ao menos tentou calcular ou adivinhar o crescimento de caminhos possíveis para alguns gráficos? Se você tiver o gráfico totalmente conectado, você obterá

  • 2 - 1
  • 3 - 4
  • 4 - 15
  • 5 - 64
  • 6 - 325
  • 7 - 1956
  • 8 - 13699
  • 9 - 109600
  • 10 - 986409
  • 11 - 9864100
  • 12 - 108505111
  • 13 - 1302061344
  • 14 - 16926797485
  • 15 - 236975164804
  • 16 - 3554627472075
  • 17 - 56874039553216
  • 18 - 966858672404689
  • 19 - 17403456103284420
  • 20 - 330665665962403999

Tem certeza de que deseja encontrar todos os caminhos para todos os nós? Isso significa que se você computar um milhão de caminhos em um segundo, levaria 10750 anos para computar todos os caminhos para todos os nós em um grafo totalmente conectado com 20 nós. É o limite superior para sua tarefa, então acho que você não gostaria de fazê-lo. Acho que você quer outra coisa.

Não é uma solução algorítmica aprimorada de forma alguma, mas você pode frequentemente melhorar o desempenho gerando vários threads de trabalho, potencialmente aqui um para cada nó de primeiro nível e, em seguida, agregando os resultados.Isso muitas vezes pode melhorar algoritmos ingênuos de força bruta com relativa facilidade.

Você pode ver um exemplo aqui: Algumas funções da matriz Erlang , na função maximise_assignment (comentários começando na linha 191 a partir de hoje).Novamente, o algoritmo subjacente é bastante ingênuo e força bruta, mas a paralelização acelera muito bem para muitas formas de matrizes.

Usei uma abordagem semelhante no passado para encontrar o número de caminhos hamiltonianos em um gráfico.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top