J'ai environ 70k nœuds, et des bords de 250 km, et le graphique n'est pas nécessairement connecté. Évidemment en utilisant un algorithme efficace est crucial. Que recommandez-vous?
Note latérale, j'apprécierais des conseils sur la manière de diviser la tâche entre plusieurs machines - est-ce que même possible avec ce type de problème?
merci
4 Réponses :
Mapreduce est un excellent algorithme distribué pour cela, bien que cela puisse être un peu trop élevé. Si vous êtes intéressé par cela, jetez un coup d'œil à Conférence ou peut-être que ce blog post pour l'inspiration. (En fait, quand on m'a appris Mapreduce, c'était l'un des premiers exemples.)
Pour les bords 250K et 70k, il semble que le graphique soit relativement rare, algorithme de dijkstra Exécute dans Vous pouvez également jeter un coup d'œil à ALGORITHM'S JOHNSON Si votre problème traite négatif poids, mais pas cycles négatifs. Spécifiquement, il peut également être distribué, car il prend le graphique repondéré et exécute l'algorithme de Dijkstra de chaque nœud. O (E + V Log V) Pour chaque nœud, pour une heure d'exécution complète (toutes les sources) de O (VE + V ^ 2 LOG V) . Cela devrait être assez rapide, mais les réserves habituelles s'appliquent à Dijkstra. (Bords négatifs.)
Les derniers liens ne s'affichent pas: EN.Wikipedia.org/wiki/dijkstra's_algorithm et en.wikipedia.org/wiki/johnson's_algorithm
Vous devriez lire sur la syntaxe de Markdown pour formater votre message. +1 De toute façon de moi.
Je veux dire, il semble qu'il y ait une limite de liaison.
Vous pouvez utiliser le algorithme Floyd-Warshall . Cela résout exactement ce problème.
La complexité est O (v ^ 3).
Il y a aussi Algorithme de Johnson avec une complexité de O (v ^ 2 * journal v + ve). Ce dernier est également facile à distribuer, car il exécute l'algorithme de Dijkstra V Times, qui peut être fait en parallèle.
Hm. Mais a o (n ^ 3) complexité. Cela peut ne pas être très efficace.
@Dircrange: En fait, la complexité serait quelque chose comme o (v ^ 2 + v * e). Ce n'est pas une fusée rapide, mais vous ne pouvez probablement pas obtenir beaucoup plus si vous voulez des sorties V ^ 2.
@jpalecek: Je faisais appelé le poste original et Floyd Warshall en particulier.
WOW, Floyd-Warshall est un algorithme concis. Si je n'avais pas autant de nœuds, je le choisirais certainement.
Il y a deux façons naïves de paralléliser ce problème:
1) Identifiez les sous-composants et distribuez-les sur différents ordinateurs. La longueur du chemin entre deux nœuds de deux composants différents est indéfinie.
2) Chargez le graphique dans différents ordinateurs et donnez à tous les ordinateurs une liste de nœuds pour calculer tous les chemins les plus courts. Les résultats pour un nœud ne dépendent pas des résultats d'un autre nœud afin que vous puissiez parallémenter ce problème.
Upside: pas trop difficile à mettre en œuvre, mais je ne le ferais que si vous devez résoudre cela une fois. S'il s'agit d'un problème récurrent, vous voudrez peut-être examiner les algorithsions distribués.
Utilisez iGraph , il est écrit en C, assez rapide et vous pouvez utiliser Python comme langue d'enveloppe.
Regardez les papiers / publications qui possèdent les mots-clés suivants: algorithmes de recherche de graphiques distribués. ici '' '' '' '' '' '' '' '''s u peut être utile.
Il y a ce compte ACM uniquement papier aussi: Computation distribuée sur les graphiques: algorithmes de chemin les plus courts
Vous êtes correct, ce n'est pas un problème de devoirs, juste un projet de plaisir. Je n'avais pas envisagé d'approximations, mais dans ce cas, j'ai besoin d'obtenir le chemin réel entre deux nœuds et non seulement la distance. Je ne vois pas comment une approximation pourrait vraiment aider dans ce cas, mais je serais intéressé à entendre comment si elles le pouvaient. Edit: C'était en réponse à un commentaire qui a été supprimé. Tant pis.
Désolé je l'ai supprimé! Je voulais juste demander si vous aviez envisagé de résoudre les approximations, mais j'ai décidé de ne pas demander de toute façon que vous avez déjà accepté une réponse. :)
Et une approximation dans ce contexte serait un chemin qui n'est pas garanti d'être le plus court, mais est garanti de ne pas être plus de x% plus longtemps que le chemin le plus court.
Avez-vous 18 gibib de mémoire pour stocker la solution? Avez-vous vraiment besoin de tous?