Je sais que l'approche de la force brute pour le faire est d'effectuer des DFS sur tous les sommets du graphique.SO pour cet algorithme la complexité serait O (v | v + e |). Mais existe-t-il un moyen plus efficace de faire cela?
3 Réponses :
Dans le pire des cas, O (| V | ^ 2) L'espace serait nécessaire pour stocker toutes ces informations explicitement - c'est-à-dire pour stocker la liste complète des sommets accessibles pour chaque sommet (penser à un graphique dans lequel chaque sommet a un bord à tous les autres sommets). Mais il est possible de le représenter de manière à ce que Seul O (| V |) soit nécessaire, et cette représentation peut être construite dans O (| V | + | e |) temps, L'idée de base est la suivante: Donc, étant donné un sommet U en G, recherchez son SCC, SCC (U). Appelez cela i. Effectuer un DFS via G 'à partir de Vertex I: Pour chaque sommet (de g') J rencontré lors de ce DFS, émis chaque sommet (de g) dans Verts (J). et une requête sur elle sera Ne prenez que du temps proportionnel à la taille de la réponse (nombre de sommets accessibles) .
En fait, il semble que l'heure dans le pire des cas n'est pas proportionnelle à la taille de la réponse. Imaginez un graphique qui a trois couches. Il y a tous les bords possibles de la troisième à la deuxième couche et de la seconde à la première couche. C'est un dag, il est donc de trouver CCC ne le change pas. Cependant, l'exécution d'un DFS à partir de n'importe quel sommet de la troisième couche consiste à examiner tous les bords ( O (n ^ 2) ), mais il y en a au plus O (n) sommets accessibles . Donc, exécuter un DFS de tous les sommets de la troisième couche entraîne O (n ^ 3) temps, ce qui n'est pas meilleur qu'une solution naïve.
@kraskevich: Vous avez absolument raison. Je ne peux pas voir un moyen de voir ça ... Pouvez-vous? Y a-t-il peut-être un moyen d'interroger efficacement pour le prochain enfant d'un sommet qui évite les sommets déjà observés?
@Kraskevich: Je me rends compte maintenant qu'une requête aussi efficace impliquerait que DFS peut être effectué à temps que o (| v | + | e |)!
Je soupçonne vraiment qu'il n'y a pas un meilleur algorithme connu pour les graphiques généraux. Tous les papiers que j'ai trouvés sur le sujet [1] [2] décrivent des algorithmes qui fonctionnent dans O (| V | * | e |) heure. Ce n'est pas mieux que votre tentative naïve dans le pire des cas.
Même la page Wikipedia [3] dit que les algorithmes les plus rapides réduisent le problème de la multiplication de matrice, que les algorithmes les plus rapides ne sont que marginalement mieux que votre base de référence.
[1] http://ion.uwinnipeg.ca/~ychen2/conferencepapers /tranrelationCopy.pdf
Je reçois l'impression de papiers comme http://research.microsoft.com/pubs /144985/todsfinal.pdf qu'il n'y a pas d'algorithme qui fait mieux que o (ve) ou o (v ^ 3) dans le cas général. Pour les graphiques clairsemés et d'autres graphiques spéciaux, il y a des algorithmes plus rapides. Il semble toutefois que vous puissiez toujours apporter des améliorations en séparant la "construction d'index" de "Query", si vous avez une idée du nombre de requêtes qui seront effectuées sur les données. S'il y aura beaucoup de questions, O (1) est possible pour les requêtes si toutes les données sont pré-calculées (DFS ou Floyd-Warshall, etc.) et stockées dans O (n ^ 2) espace. D'autre part, s'il va être relativement peu de requêtes, la durée de la construction d'espace et / ou d'index peut être réduite au détriment du temps de requête.