Vorgehensweise bei Problemen mit dynamischen Graphen

15

Ich habe diese Frage bei generic stackoverflow gestellt und war hier gerichtet.

Es ist großartig, wenn jemand erklären kann, wie man partielle oder vollständig dynamische Graphprobleme im Allgemeinen angeht.

Beispielsweise:

  • Finden Sie den kürzesten Pfad zwischen zwei Scheitelpunkten in einem ungerichteten gewichteten Diagramm für Instanzen, wenn bei jeder Instanz eine Kante entfernt wird.n(u,v)n
  • Finden Sie die Anzahl der verbundenen Komponenten in einem ungerichteten Diagramm für n Instanzen, wenn bei jeder Instanz eine Kante entfernt wird usw.

Ich bin kürzlich in einem Programmierwettbewerb auf dieses Problemgenre gestoßen. Ich habe im Internet gesucht und zahlreiche Forschungsarbeiten zu dynamischen Graphen gefunden [1,2]. Ich habe ein paar von ihnen gelesen und konnte nichts direktes finden (Clustering, Sparsification usw.). Tut mir leid, dass ich vage bin.

Ich weiß es wirklich zu schätzen, wenn einige Hinweise geben können, um diese Konzepte besser zu verstehen.


  1. Dynamische Graph-Algorithmen von D. Eppstein, Z. Galil, GF Italiano (1999)
  2. Kürzeste Wege auf dynamischen Graphen von G. Nannicini, L. Liberti (2008)
Prakash
quelle

Antworten:

12

Es ist schwierig, Ihnen konkrete Techniken zu vermitteln, da "dynamisch" eine Vielzahl von Dingen bedeuten kann und die Algorithmen / Ergebnisse von Ihrem Modell abhängen. Nachfolgend finden Sie eine Übersicht der Bedenken. Hier ist ein Artikel, der einen Überblick über verschiedene Anliegen und Modelle gibt (im Zusammenhang mit dem, was Peter in einer anderen Antwort zitiert hat).


Bei dynamischen Problemen im Allgemeinen sind die Hauptprobleme:

  • Wollen Sie auf jeden Fall eine exakte Lösung, oder ist eine Annäherung zulässig?
  • Wissen Sie etwas darüber, welche Veränderungen eintreten werden (z. B. eine Wahrscheinlichkeitsverteilung), oder sind sie alle gleich wahrscheinlich?
  • Wie erfährt der Algorithmus von den Änderungen?

Ein typisches dynamisches Modell sieht folgendermaßen aus:

  1. Bei einem gegebenen Diagramm möchten Sie eine Eigenschaft berechnen. Sie dürfen eine Lösung für das ursprüngliche Diagramm berechnen.

  2. Ihnen wird dann eine Änderung mitgeteilt: Kante wird gelöscht. Berechnen Sie die Eigenschaft im neuen Diagramm mit begrenzten Ressourcen .(e,f)

  3. Wiederholen Sie 2 für mal.n

Und hier sind 3 mögliche Modifikationen:

  • Sie dürfen zu Beginn nicht die vollständige Lösung berechnen, da die Informationen, die Zeit und der Raum begrenzt sind (ein Beispiel hierfür sind Online-Algorithmen ).

  • In Schritt 2 wird der Algorithmus nicht „ sagt“ die Modifikation, hat aber zu finden , die Änderung in der graphischen Darstellung durch eine Datenstruktur oder etwas abfragt.

  • Ein verteiltes Modell (wie Peter in einer anderen Antwort erläutert), in dem die Informationen lokal ermittelt und die Berechnung / Änderungen lokal vorgenommen werden.

Dynamische Modelle sind in der Regel aufgrund von Ressourcenbeschränkungen (z. B. Zeit / Raum) interessant. Wenn ich in Schritt 2 eine vollständige Antwort berechnen durfte (wie in Schritt 1), ist das Problem einfach, da es sich nur um ein wiederholtes statisches Diagrammproblem handelt. Wir sind mehr an der kleinsten Menge an Ressourcen interessiert, die zur Berechnung der Änderung erforderlich sind.

Lucas Cook
quelle
Vielen Dank für die Antwort. Ich habe versucht, die Komplexität und Möglichkeiten der Lösung eines einfachen, teilweise dynamischen Diagrammproblems zu verstehen.
Prakash
Vielen Dank für die Antwort. Ich werde die Papiere durchgehen. Ich habe versucht, die Komplexität und Möglichkeiten der Lösung eines einfachen, teilweise dynamischen Diagrammproblems zu verstehen. Beispiel: Eine Reihe von Städten, die durch Straßen verbunden, ungerichtet und nach Entfernung gewichtet sind. Finden Sie den kürzesten Weg zwischen 2 Städten in n Fällen, in denen eine Straße aus verschiedenen Gründen blockiert ist. Das Ausführen von Dijkstra zum Beispiel ist unpraktisch, gibt es eine Möglichkeit, vorhandene Algorithmen wie A * anzupassen, um diese Probleme zeitlich besser zu lösen?
Prakash
A * ist eine Verallgemeinerung der Dijkstra + Heuristik; Die Leistung ist im schlimmsten Fall ähnlich. Für mich ist die wichtige Frage für Ihr Problem, welche Art von Informationen Sie zwischen den Instanzen speichern können , um die nächste Instanz schneller zu machen. Wenn ich beispielsweise den vorherigen kürzesten Pfad speichere, kann ich schnell herausfinden, ob er "fehlgeschlagen" ist, aber es gibt keinen offensichtlichen Weg, um den nächsten kürzesten Pfad zu berechnen. (Auch wenn Sie k kürzeste Pfade von der vorherigen Instanz speichern, vermute ich, dass dies für k gilt.)
Lucas Cook
(In meinem vorherigen Kommentar ging es hauptsächlich um Worst-Case-Lösungen. Vielleicht interessiert Sie der Durchschnittsfall? Dann könnte es eine Heuristik geben, die eine gute A * -Lösung ergibt.)
Lucas Cook,
10

Dynamische Graphenmodelle wurden im Distributed Computing intensiv untersucht. Für verteilte Algorithmen ist die Berechnung in Runden strukturiert, und die Topologie von Graphen (= Netzwerk) kann sich von Runde zu Runde ändern, die von einem Gegner gesteuert werden. Darüber hinaus führt jeder Knoten des Graphen einen Algorithmus aus, der eine Nachricht an seine (aktuellen!) Nachbarn senden kann. (Diese Nachricht ist die Eingabe des Algorithmus des Nachbarn in der nächsten Runde.) Interessant ist, dass ein Knoten nicht den gesamten Graphen "sieht", sondern nur seine lokale Umgebung.

Probleme, die in diesen Einstellungen berücksichtigt werden, sind beispielsweise Informationen, bei denen jeder Knoten im Diagramm anfänglich ein Token enthält, und schließlich möchten Sie, dass jeder Knoten jedes Token gesehen hat. Das Ziel besteht darin, Algorithmen zu entwerfen, die dies in der geringsten Anzahl von Runden unter Verwendung der geringsten Anzahl von Nachrichten erreichen. Siehe [2] für eine aktuelle Umfrage.

Für die nicht verteilte Einstellung sollten Sie sich [1] ansehen, eine Erweiterung des Papiers, das Sie erwähnt haben.


[1] Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian, Eli Upfal und Fabio Vandin: Algorithmen zur Entwicklung von Graphen . ITCS 2012: 149-160

[2] Fabian Kuhn, Rotem Oshman: Dynamische Netzwerke: Modelle und Algorithmen . SIGACT News 42 (1): 82-96 (2011)

Peter
quelle
Haben diese Algorithmen zur Nachrichtenübermittlung keine Probleme mit (fehlender) Konvergenz?
Raphael
Ich verstehe nicht, was Sie mit "Konvergenz" meinen. Solange der Graph in jeder Runde verbunden bleibt, erhöht sich die Anzahl der Knoten, die ein bestimmtes Token t gesehen haben, um mindestens 1. Somit hat nach n Runden jeder t gesehen, unabhängig davon, wie der Gegner die Topologie ändert.
Peter
Ich dachte an das Count-to-Infinity-Problem, das durch die Änderung der Topologie verursacht wurde.
Raphael
@Raphael In der verteilten Dynamik untersuchen Forscher in der Regel, welche Eigenschaften innerhalb eines bestimmten Zeitrahmens im ungünstigsten Fall garantiert werden können. Somit kann "Konvergenz" für Distanzvektor / Bellman-Ford aufgrund grundlegender Probleme mit der Technik in einer dynamischen Umgebung nicht garantiert werden. Es gibt andere konvergente Routing-Protokolle, bei denen das Problem der Zählung bis zur Unendlichkeit nicht besteht.
Lucas Cook
3

Aufbauend auf @ Peter-Antworten (es ist ein sehr langer Kommentar, daher habe ich ihn nur als Antwort eingefügt, damit jemand davon profitiert).

Ich würde den folgenden Verweis vorschlagen:

Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, Nicola Santoro: Zeitvariable Graphen und dynamische Netzwerke. IJPEDS 27 (5): 387-408 (2012)

Δ

Was bei dieser Klassifizierung wirklich wichtig ist, ist, dass es Einschlussbeziehungen zwischen den verschiedenen Klassen gibt. Wenn Sie also ein Problem in einer bestimmten Klasse lösen, lösen Sie es in jeder anderen Klasse, in der es enthalten ist.

Dieselben Autoren stellten Rundfunkalgorithmen für einige der genannten Diagramme vor. Sie gaben verschiedene Leistungsmetriken in Bezug auf die Zeit an (dh unterschiedliche Definition der kürzesten Zeit). Beim Broadcasting besteht die Idee darin, dass jeder Knoten eine Ansicht des Netzwerks in der Zeitdomäne erstellt. Dies geschieht durch wiederholtes Abhören von Nachbarn und Senden von Informationen an Nachbarn. Wenn Periodizität angenommen wird, kann ein Knoten den kürzesten Zeitpfad zu einem anderen Knoten angeben. Diese Informationen werden beim Routing verwendet. Weitere Details finden Sie in:

Arnaud Casteigts, Bernard Mans, Nicola Santoro, Paola Flocchini: Deterministische Berechnungen in zeitveränderlichen Graphen: Rundfunk unter unstrukturierter Mobilität. IFIP TCS 2010: 111-124

uv{(u,x1),(x1,x2),....,(xk,v)}uvvu

Ich habe einen Vortrag der Vorgänger besucht. Nach meinem Verständnis behaupten sie, dass wir nicht in der Lage sind, mit dynamischen Graph-Algorithmen umzugehen (gemäß den Definitionen, die sie befolgen). Das sind wir noch bei einfachen Klassen. Tatsächlich behaupten sie, dass die meisten Algorithmen für mobile Computer einfach davon ausgehen, dass ihre Algorithmen zu schnell sind, um ausgeführt zu werden, während sich das Netzwerk im Übergang befindet! (was ich glaube, dass ich viel gehört habe) - Oder nehmen Sie einfach die Periodizität der Kantenerscheinung an (siehe verzögerungstolerante Netzwerke usw.)

AJed
quelle