Récupérer le chemin le plus court d'un graphe dynamique

24

J'étudie actuellement les chemins les plus courts dans les graphiques dirigés. Il existe de nombreux algorithmes efficaces pour trouver le chemin le plus court dans un réseau, comme celui de dijkstra ou celui de bellman-ford. Mais que faire si le graphique est dynamique? En disant dynamique, je veux dire que nous pouvons insérer ou supprimer des sommets lors de l'exécution du programme. J'essaie de trouver un algorithme efficace pour mettre à jour les chemins les plus courts d'un sommet à tous les autres sommets u , après avoir inséré une arête e , sans avoir à exécuter à nouveau l'algorithme du chemin le plus court dans le nouveau graphique. Comment puis-je faire ceci? Merci d'avance.vue

  • Remarque: les modifications peuvent être effectuées après la première itération de l'algorithme
  • Remarque [2]: deux nœuds sont donnés, la source et t la cible. J'ai besoin de trouver le chemin le plus court entre ces nœuds. Lorsque le graphique est mis à jour, je n'ai qu'à mettre à jour π ( s , t ) , qui est le chemin le plus court entre s et t .stπ(s,t)st
  • Remarque [3]: Je ne suis intéressé que par le cas d'insertion de bord.

Une définition formelle : étant donné un graphique . Définissez une opération de mise à jour comme 1) une insertion d'une arête e dans Eg=(V,E)eE ou 2) aa suppression d'un bord de E . L'objectif est de trouver efficacement le coût de toutes les paires de chemins les plus courts après une opération de mise à jour. Par efficace, nous entendons au moins mieux que d'exécuter un algorithme All-Pairs-Shortest-Path, tel que l'algorithme Bellman-Ford, après chaque opération de mise à jour.eE


Edit: Ci - dessous, il existe une version simplifiée du problème:

Un graphe pondéré est donné, composé d'arêtes unidirectionnelles et de deux sommets critiques s et t . Un ensemble C de bords bidirectionnels candidats est également donné. Je dois construire une arête ( u , v ) C pour minimiser la distance de s à t .G(V,E)stC(u,v)Cst

Rontogiannis Aristofanis
la source
Plus de questions de clarification: les points d'extrémité de votre chemin restent-ils fixes à chaque fois? Êtes-vous uniquement intéressé par le cas d'insertion de bord ou par des modifications arbitraires du graphique? Je pense qu'il y a des recherches qui répondent à votre question, mais malheureusement je ne sais pas vraiment où chercher. Une recherche rapide sur Google révèle ces diapositives qui semblent très utiles, et cet article: "les chemins les plus courts sur les graphiques dynamiques" (espérons que le lien fonctionne). (u,v)
usul

Réponses:

14

Le problème que vous avez probablement remarqué est un problème assez difficile. La vérification du Web entraînera des instances complexes dont vous n'aurez probablement pas besoin. Voici une solution - au besoin (c'est-à-dire que vous n'avez pas besoin de tout recalculer à partir de zéro).

dans le cas de l'ajout d'une arête - puis en utilisant votre matrice de distance déjà construite - procédez comme suit:(u,v)

Pour chaque paire de nœuds et y, vérifiez si d ( ( x , u ) ) + c ( ( u , v ) ) + d ( ( v , y ) ) < d ( ( x , y ) ) - cela peut être fait dans O ( n 2 ) puisque vous comparez chaque paire de nœuds.Xyd((x,u))+c((u,v))+d((v,y))<d((x,y))O(n2)

Pour le cas de la suppression de bord: Étant donné la matrice de distance déjà construite, vous pouvez avoir pour chaque nœud un arbre de chemin le plus court enraciné en u . Si l'arête supprimée e n'est pas dans cet arbre, alors les chemins les plus courts de u à tous les autres ne sont pas affectés - (ils restent les mêmes).uueu

Si est dans l'arbre de chemin le plus court de u , alors pour chaque nœud v tel que le chemin le plus court π ( u , v ) inclut e , les chemins changeront. Par conséquent, calculez le chemin le plus court de u verseuvπ(u,v)eu . Maintenant, répétez la précédente pour chaque nœud - ce n'est pas la meilleure solution. En fait, dans le pire des cas, cela équivaut asymptotiquement à tout faire à partir de zéro, mais peut être meilleur en moyenne. v

si vous voulez avoir de meilleurs résultats que cela, alors regardez:

  1. Demetrescu, Camil et Giuseppe F. Italiano. "Une nouvelle approche pour dynamiser toutes les paires de chemins les plus courts." Journal de l'ACM (JACM) 51.6 (2004): 968-992. (peut être trouvé gratuitement sur Google)

  2. ou jetez un œil à cette enquête joliment écrite

AJed
la source
17

Le problème que vous demandez est un problème algorithmique bien connu. Il est en fait toujours ouvert, à quel point ce problème est difficile. Vous devez également savoir qu'il existe différentes incarnations de ce problème. En revanche, ce que vous demandez, généralement, seules les distances sont renvoyées, tandis que vous demandez les chemins les plus courts réels. Notez que ces chemins peuvent être déjà très longs. Les algorithmes de graphique dynamique distinguent uniquement les suppressions de bord (algorithmes dg décrémentiels), les insertions de bord uniquement (algorithmes dg incrémentiels) et les insertions et suppressions de bord (algorithmes dg entièrement dynamiques). Vous êtes donc intéressé par par les algorithmes incrémentaux .

Les algorithmes mentionnés dans le post d'AJed, sont légèrement dépassés. Il y a de nouveaux résultats par Thorup, voir ici, à la page 8 pour un bref aperçu. Le meilleur algorithme APSP exact entièrement dynamique actuellement de Thorup (pour les requêtes de distance, pas le chemin), a besoin de temps de mise à jour amorti, tout en prenant en charge O ( 1 ) dans le pire des cas, notez que si vous avez O ( n log n )O(n2(logn+log2(1+m/n))O(1)O(nlogn)bords, alors vous pouvez simplement recalculer à partir de zéro avec Dijkstra et Fibonacci-tas et obtenir le même temps d'exécution que dans l'algorithme de Thorup. Donc, si vos graphiques ne sont pas trop denses, je recommanderais d'utiliser Dijkstra.

Je ne connais pas de meilleur algorithme incrémental . Mais vous devriez faire une recherche sur le Web s'il existe de nouveaux résultats pour ce problème spécialisé.

A.Schulz
la source
Je n'ai pas besoin de mettre à jour tous les chemins les plus courts du graphique, mais uniquement entre une paire donnée . Y a-t-il quelque chose de mieux pour ça? (s,t)
Rontogiannis Aristofanis
@RondogiannisAristophanes en fait, ce qui a été proposé jusqu'à présent est en quelque sorte le meilleur. Jetez un oeil à cet article qui prétend que: "les problèmes de chemins les plus courts incrémentiels et décrémentiels à source unique, pour les graphiques dirigés ou non dirigés pondérés, sont, au sens fort, au moins aussi difficiles que les chemins les plus courts toutes paires statiques problème." (pour être honnête, je n'ai lu que l'intro) - référence: "Sur les problèmes de chemins les plus courts dynamiques", Roditty & Zwick - mais pourriez-vous s'il vous plaît nous dire quel est le problème exact que vous avez? quel scénario spécifique? qu'avez-vous jusqu'ici? - nous pouvons peut-être mieux vous aider.
AJed
@RondogiannisAristophanes meilleures sont les performances, plus il est difficile à implémenter (dans la plupart des cas) et parfois dans les applications pratiques, vous n'avez pas besoin d'autant d'amélioration des performances.
AJed
@AJed J'ai modifié mon article pour inclure une description simplifiée du problème.
Rontogiannis Aristofanis
5

Je pense que l'algorithme AD * pourrait vous aider.

http://www.cs.cmu.edu/~ggordon/likhachev-etal.anytime-dstar.pdf

Lorsque des informations mises à jour concernant le graphique sous-jacent sont reçues, l'algorithme répare progressivement sa solution précédente. Le résultat est une approche qui combine les avantages des planificateurs à tout moment et incrémentiels pour fournir des solutions ef fi caces à des problèmes de recherche complexes et dynamiques

Points forts d'AD *: c'est "à tout moment", ce qui signifie qu'il peut vous donner une "solution sous-optimale" très rapidement, même si ce n'est pas la meilleure. Avec suffisamment de temps, il retournera la solution optimale. En outre, vous pouvez limiter la solution sous-optimale pour qu'elle ne soit pas pire que la solution optimale par une constante définie par l'utilisateur. Cela vous donne la possibilité de l'utiliser dans un scénario de planification en temps réel où il est préférable d'avoir une solution correcte (où «ok» est théoriquement limité) que de n'avoir aucune solution du tout.

http://www.cs.cmu.edu/~maxim/software.html

Victor
la source