Trouver tous les chemins possibles d'un sommet dans un graphe cyclique dirigé en Erlang

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

Question

Je souhaite mettre en oeuvre une fonction qui trouve tous les chemins possibles pour tous les sommets possibles à partir d'un sommet de la source V d'un graphe orienté G cyclique.

La performance n'a pas d'importance maintenant, je voudrais juste comprendre l'algorithme. J'ai lu la définition de l'algorithme de recherche en profondeur d'abord, mais je n'ai pas pleine compréhension de ce qu'il faut faire.

Je n'ai pas complété morceau de code pour fournir ici, parce que je ne suis pas sûr de savoir comment:

  • stocker les résultats (avec A> B> C> nous devons aussi stocker A> B et A> B> C);
  • représentent le graphique (digraph liste des tuples?);
  • combien de récurrences à l'utilisation (travail à chaque sommet adjacent?).

Comment puis-je trouver tous les chemins possibles forment un sommet de source donnée dans un graphe cyclique dirigé en Erlang?

UPD: Sur la base des réponses à ce jour je dois redéfinir la définition du graphe: il est un graphique non-acyclique. Je sais que si ma fonction récursive frappe un cycle, il est une boucle indéfinie. Pour éviter cela, je peux vérifier si un sommet est en cours dans la liste du chemin résultant - si oui, je me arrête et retourner le déplacement chemin

.

UPD2: Merci pour la pensée provoquant des commentaires! Oui, je dois trouver tous les chemins simples qui ne sont pas des boucles d'un sommet source à tous les autres.

Dans un graphique comme celui-ci:

graphe non-acyclique

avec la source sommet A l'algorithme doit trouver les chemins suivants:

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

Le code suivant fait le travail, mais il est inutilisable avec des graphiques qui ont plus de 20 sommets (je suppose qu'il est quelque chose de mal avec la récursivité - prend trop de mémoire, jamais extrémités): 

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.

UPD3:

Le problème est que l'algorithme de recherche en profondeur d'abord régulière sera l'un des aux chemins d'abord: (A, B, C, D) ou (A, D, C, B) et ne sera jamais le deuxième chemin.

Dans les deux cas, il sera le seul chemin - par exemple, lorsque les backtracks réguliers de DFS de (A, B, C, D), il remonte à A et vérifie si D (le deuxième voisin de A) est visité . Et puisque le DFS maintient régulièrement un état global pour chaque sommet, D aurait état « visité ».

Alors, nous devons présenter un état de dépendance récursivité - si nous backtrack de (A, B, C, D) jusqu'à A, nous devrions avoir (A, B, C, D) dans la liste des résultats et nous devrions avoir marqué comme D unvisited au début de l'algorithme.

I ont tenté d'optimiser la solution à une récursive, mais encore le temps d'exécution de l'algorithme est irréalisable - il faut environ 4 secondes pour traverser un petit graphique de 16 sommets avec 3 bords par sommet: 

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).

Toutes les idées pour exécuter ce temps acceptable?

Était-ce utile?

La solution

Edit: D'accord, je comprends maintenant, vous voulez trouver tous les chemins simples d'un sommet dans un graphe orienté. Ainsi, une recherche en profondeur d'abord avec retours en arrière serait approprié, comme vous l'avez réalisé. L'idée générale est d'aller à un voisin, puis passez à un autre (pas celui que vous avez visités), et continuer jusqu'à ce que vous frappez une impasse. Puis remonter la piste jusqu'au dernier sommet vous étiez à choisir et un voisin différent, etc. Vous devez obtenir les bits fiddly droit, mais il ne devrait pas être trop difficile. Par exemple. à chaque étape, vous devez étiqueter les sommets « exploré » ou « inexploré » selon que vous les avez déjà visité auparavant. La performance ne devrait pas être un problème, un algorithme correctement mis en œuvre devrait peut-être prendre O (n ^ 2) temps. Je ne sais pas ce que vous faites mal, peut-être que vous visitez trop de voisins? Par exemple. peut-être vous revisitez les voisins que vous avez déjà visité, et faire le tour dans les boucles ou quelque chose.

Je ne l'ai pas vraiment lu votre programme, mais la page Wiki sur profondeur d'abord la recherche a un programme de pseudocode court, simple que vous pouvez essayer de copier dans votre langue. Conserver les graphiques sous forme de listes Adjacence pour le rendre plus facile.

Edit: Oui, désolé, vous avez raison, la recherche standard DFS ne fonctionnera pas tel qu'il est, vous devez ajuster légèrement pour ne sommets revisiter a visité avant. Donc, vous êtes autorisé à visiter tous les sommets sauf ceux que vous avez déjà stockés dans votre chemin en cours. Bien sûr, cela signifie que mon temps d'exécution était complètement faux, la complexité de votre algorithme sera par le toit. Si la complexité moyenne de votre graphique est d + 1, alors il y aura environ d * d * d * ... * d = d ^ n chemins possibles. Donc, même si tous les sommets seulement 3 voisins, il y a encore pas mal de chemins quand vous arrivez au-dessus de 20 sommets. Il n'y a pas moyen de contourner cela vraiment, parce que si vous voulez que votre programme de sortie tous les chemins possibles alors en effet, vous aurez à la sortie tout d ^ n d'entre eux.

Je suis intéressé de savoir si vous en avez besoin pour une tâche spécifique, ou essayez juste de programmer hors d'intérêt. Dans ce dernier cas, vous devez juste être heureux avec de petits graphiques peu connectés.

Autres conseils

Je ne comprends pas la question. Si j'ai graphe G = (V, E) = ({A, B}, {(A, B), (B, A)}), il y a des chemins infinis de A à B {[A, B], [ A, B, A, B], [A, B, A, B, A, B], ...}. Comment puis-je trouver tous les chemins possibles à tout sommet dans le graphique cyclique?

Edit:

Avez-vous même essayé Compute ou deviner de plus en plus de chemins possibles pour certains graphiques? Si vous avez graphique entièrement connecté, vous obtiendrez

  • 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

Êtes-vous sûr que vous souhaitez trouver tous les chemins pour tous les nœuds? Cela signifie que si vous calculez un milion chemins en une seconde, il faudrait 10750 années pour calculer tous les chemins vers tous les nœuds dans le graphique entièrement connecté à 20 noeuds. Il est majorant votre tâche donc je pense que vous ne voudriez le faire. Je pense que vous voulez autre chose.

Pas une solution algorithmique améliorée par tout moyen, mais vous pouvez souvent améliorer les performances en fraie threads de travail multiples, potentiellement ici un pour chaque premier nœud de niveau, puis l'agrégation des résultats. Cela peut souvent améliorer les algorithmes de force brute naïve relativement facilement.

Vous pouvez voir un exemple ici: Certaines fonctions Erlang matrice , dans la fonction maximise_assignment (commentaires à partir de la ligne 191 à partir d'aujourd'hui). Encore une fois, l'algorithme sous-jacent, il est assez naïve et la force brute, mais la parallélisation l'accélère très bien pour de nombreuses formes de matrices.

Je l'ai utilisé une approche similaire dans le passé pour trouver le nombre de chemins hamiltonien dans un graphe.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top