Je recherche un algorithme rapide pour calculer le flux maximal dans des graphiques dynamiques (ajout / suppression de nœud avec des bords connexes au graphique). Nous avons un flux maximum dans g maintenant nouveau noeud ajouté / supprimé avec des bords connexes, je n'aime pas recalculer le flux maximal pour le nouveau graphique, je souhaite utiliser les résultats disponibles précédents pour ce graphique.
Tout prétraitement qui n'est pas très temps / la mémoire consommateur est approprié.
L'idée la plus simple consiste à recalculer le flux.
Une autre idée simple est que cela, sauvegardez tous les chemins augmentant utilisés dans le calcul de la maxflow précédent, désormais pour ajouter Vertex Aussi pour supprimer le noeud au-dessus de l'idée ne fonctionne pas.
Aussi ma question n'est pas liée à une autre question qui semble sur les bords dynamiques ajoutant / supprime . V , nous pouvons trouver de simples chemins (dans le graphique de la capacité mise à jour par étape précédente) qui commence À partir de la source, va à V puis va à destination, mais problème est que ce chemin doit être simple, je ne pouvais pas trouver mieux que O (n * e) pour ce cas. (Si ce n'était qu'un seul chemin ou des chemins était disjoint, cela peut être fait dans O (n + e), mais ce n'est pas le cas).
3 Réponses :
Ajouter dynamiquement un Vertex 1) Ajouter 2) Ajouter les bords associés Faites l'inverse pour supprimer un sommet et ses bords associés. V et ses bords associés E :
v par lui-même au graphique. Comme il n'a pas de bords, il ne peut affecter le flux maximum.
E au graphique, un à la fois, à l'aide de l'algorithme de cette question
-1 Connaissez-vous l'ordre de cet algorithme? C'est plus que O (E) pour chaque bord, il n'est pas bon (mon propre algorithme est plus simple et plus rapide), également ceci (ce que vous avez offert) ne couvre pas la suppression du nœud.
Pour ajouter Vertex V, utilisez l'ancien flux F et calculez le graphe résiduel, puis obtenez un chemin d'augmentation par DFS Pledeg (V) Times.
Pour retirer un Vertex V - Compute tout le flux qui quitte V, disons que la somme du flux laissant V est une, alors tandis que (A> 0) trouve un chemin P de S de S à Thro Thro V et réduit f (p) du flux et de a.
Je pense que cela devrait aider ... je suis plus sûr de l'ajout alors sur le Supprimer, alors j'adore être corrigé dans les commentaires :)
Bonne offre mais votre approche d'ajout de sommet prend du pire des cas (n e) dans le pire des cas, aussi votre option Supprimer prend également O (n e), je ne pense pas non plus, mais votre approche d'addition est plus simple que le mien.
Je ne pense pas que vous puissiez faire quelque chose de mieux que cela ... êtes-vous sûr qu'il y a une meilleure façon? Notez que WOPEG (V) Peu susceptible d'être aussi élevé dans la plupart des graphiques, de sorte que son boîtier Avrard devrait fonctionner dans O (E) ...
Aucune moyenne ne devrait pas être O (E), en moyenne (avec des graphiques aléatoires), vous aurez degré d'environ N / 2 pour de nouveaux sommets. Mais actuellement, je pense que votre algorithme a un bogue, ce n'est pas essentiellement de mesure de degré (v) le calcul temporel (V), peut-être que nous avons besoin de plus que ceci (dans les cas où vous traversez un nouveau bord supplémentaire plus d'une fois). Aussi, je ne pense pas qu'il y ait un algorithme droit, mais demandez-le ici de voir si quelqu'un a une bonne idée?
Vous avez raison, plus correctement, c'est que la complexité sera O (delta * e) où Delta est la diffrence F'-F, où F 'est le flux de fin. en supposant que nous avons eu un flux entier.
J'ai des nombres décimaux non des entiers, mais votre O n'est pas serré mais pas mal :)
J'ai posé cette question dans cstheory.stackexchange, pour ajouter de noeud comme je l'ai discuté avec d'autres personnes que j'ai trouvées recalculé est plus rapide que d'autres algorithmes connus, car la recalculition fonctionne sur un graphique semi-clairsemé (graphique résiduel) afin qu'il soit suffisamment rapide pour éliminer le nœud, Il y avait une bonne réponse, divisant le nœud (qui veut être supprimé) en deux ensembles, v_in et v_out et calculer le flux sur un graphique résiduel à partir de v_in à v_out, puis calculez à nouveau le débit dans le graphique résiduel de v_in à v_out en ajoutant un bord infini entre la source et destination. (et enfin comparer leur différence et la mise à jour du graphique résiduel). Vous pouvez voir Q / A et Discussions associées dans flux maximum incrémentiel dans des graphiques dynamiques .
Comment votre question n'est-elle pas liée au lien que vous avez donné? Cela me semble tape.
@Ekeithrandall, ma question concerne l'ajout de la suppression de sommet, mais cette question était sur les bords, en fait avec un sommet, vous ajouterez probablement des bords
n , donc le boîtier de Vertex est plus compliqué que le boîtier de bord, par exemple je peux Avoir une certaine intuition avec des bords, mais ma meilleure solution pour les sommets n'est pas une bonne solution.@Chals, décririez-vous pourquoi vous avez supprimé la balise de flux Max? J'ai ajouté cette balise à ce sujet parce que c'est utile. spécialement dans les recherches.
Les bords sont ce qui compte, ajoutant ou enlevant un sommet sans bords n'est pas trivial. Alors peut-être que vous demandez s'il existe un algorithme incrémentiel plus efficace pour ajouter
n les bords connectés à un seul sommet, que d'exécuter l'algorithme de bord incrémental lién fois?@Saeed, le terme "flux maximum" est générique et mal défini aux étrangers. On peut peut-être envisager d'ajouter une balise wiki, en choisissant un nom plus précis pour la balise (peut-être «un flux maximum» au lieu de «max-flow»?) Et à travers d'autres questions ici et en ajoutant le cas échéant. Prendre ces étapes dissuadera de nouveaux étiquettes de suppression des étiquettes telles que moi de la supprimer à l'avenir.
@Chalarles, imo Si vous vous attendez à ce que quelqu'un le ferait, vous devriez mentionner dans votre édition, personne ne peut penser à votre idée, créant également une nouvelle balise n'a pas une règle aussi compliquée, ainsi que des programmeurs le savent comme Max-Flow, si vous Regardez leur code Je suis à peu près sûr que la quantité élevée de leur nom de fonction est max_flow, maxflow, maxflow, ... pas maximumflow, ....
@Keithrandall, pas exactement, ma question se distingue essentiellement de celle-ci, si vous pouvez la convertir à celui-ci, la fournir comme réponse. (En fait, c'est maintenant mon temps de sommeil et est peu difficile de montrer des différences en détail).