Jak podejść do problemów związanych z dynamicznym wykresem

Zadałem to pytanie przy ogólnym przepełnieniu stosu i skierowano mnie tutaj.

Świetnie będzie, jeśli ktoś będzie w stanie wyjaśnić, w jaki sposób ogólnie podejść do częściowych lub w pełni dynamicznych problemów graficznych.

Na przykład:

• Znajdź najkrótszą ścieżkę między dwoma wierzchołkami na niekierowanym wykresie ważonym dla wystąpień, gdy krawędź jest usuwana w każdym wystąpieniu.$(u,v)$$n$
• Znajdź liczbę połączonych komponentów na niekierowanym wykresie dla n wystąpień, gdy krawędź jest usuwana w każdym wystąpieniu itp.

Ostatnio spotkałem ten gatunek problemów w konkursie programistycznym. Przeszukałem sieć i znalazłem wiele artykułów naukowych dotyczących dynamicznych wykresów [1,2]. Przeczytałem kilka z nich i nie mogłem znaleźć niczego prostego (grupowanie, sparsyfikacja itp.). Przepraszam, że jestem niejasny.

Naprawdę doceniam to, że niektórzy mogą dostarczyć wskazówek, aby lepiej zrozumieć te pojęcia.

1. Dynamiczne algorytmy grafowe D. Eppstein, Z. Galil, GF Italiano (1999)
2. Najkrótsze ścieżki na wykresach dynamicznych G. Nannicini, L. Liberti (2008)

Trudno jest podać konkretne techniki, ponieważ „dynamiczny” może oznaczać wiele różnych rzeczy, a algorytmy / wyniki zależą od modelu. Poniżej znajduje się przegląd obaw. Oto artykuł, który zawiera przegląd różnych obaw i modeli (związanych z tym, co Peter zacytował w innej odpowiedzi).

W przypadku ogólnych problemów dynamicznych kluczowymi zagadnieniami są:

• czy potrzebujesz dokładnego rozwiązania we wszystkich przypadkach, czy też dozwolone jest zbliżenie?
• czy wiesz cokolwiek o tym, jakie zmiany wystąpią (np. rozkład prawdopodobieństwa), czy też wszystkie są jednakowo prawdopodobne?
• w jaki sposób algorytm dowiaduje się o zmianach?

Typowy model dynamiczny wygląda mniej więcej tak:

1. Na podstawie wykresu chcesz obliczyć pewną właściwość. Możesz obliczyć rozwiązanie dla początkowego wykresu.

2. Następnie powiedziano ci jedną modyfikację: zbocze zostało usunięte. Oblicz właściwość na nowym wykresie przy użyciu ograniczonych zasobów .$(e,f)$

3. Powtórz 2 dla razy.$n$

A oto 3 możliwe modyfikacje:

• Nie możesz obliczyć kompletnego rozwiązania na początku z powodu ograniczeń informacji / czasu / przestrzeni (jednym z przykładów są algorytmy online )

• W kroku 2 algorytm nie jest „informowany” o modyfikacji, ale musi znaleźć modyfikację na wykresie, sprawdzając strukturę danych lub coś w tym rodzaju.

• Model rozproszony (jak Peter omawia w innej odpowiedzi), w którym informacje są odkrywane lokalnie, a obliczenia / zmiany są dokonywane lokalnie.

Modele dynamiczne są zazwyczaj interesujące ze względu na ograniczenia zasobów (np. Czas / przestrzeń). W kroku 2, jeśli pozwolono mi obliczyć pełną odpowiedź (tak jak w kroku 1), problem jest prosty, ponieważ jest to tylko powtórzenie problem z grafem statycznym . Bardziej interesuje nas jak najmniejsza ilość zasobów niezbędnych do obliczenia zmiany.

Modele wykresów dynamicznych były intensywnie badane w obliczeniach rozproszonych. W przypadku algorytmów rozproszonych obliczenia są podzielone na rundy, a topologia grafów (= sieć) może podlegać pewnym zmianom z rundy na rundę, które są pod kontrolą przeciwnika. Co więcej, każdy węzeł wykresu uruchamia algorytm, który może wysłać wiadomość do swoich (obecnych!) Sąsiadów. (Ta wiadomość jest wprowadzeniem algorytmu sąsiadów w następnej rundzie.) Ciekawe jest to, że węzeł nie „widzi” całego wykresu, a jedynie jego lokalne sąsiedztwo.

Problemami branymi pod uwagę w tych ustawieniach są na przykład rozpowszechnianie informacji, gdzie każdy węzeł na wykresie początkowo zawiera token, a ostatecznie chcesz, aby każdy węzeł widział każdy token. Celem jest zaprojektowanie algorytmów, które osiągną to w najmniejszej liczbie rund, przy użyciu jak najmniejszej liczby komunikatów. Ostatnia ankieta znajduje się w [2].

W przypadku ustawienia niepodzielnego warto przyjrzeć się [1], który jest rozszerzeniem wspomnianego papieru.

[1] Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian, Eli Upfal, Fabio Vandin: Algorytmy na ewoluujących grafach . ITCS 2012: 149–160

[2] Fabian Kuhn, Rotem Oshman: Sieci dynamiczne: modele i algorytmy . SIGACT News 42 (1): 82-96 (2011)

Opierając się na odpowiedziach @Peter (jest to bardzo długi komentarz, więc podałem tylko jako odpowiedź, mając nadzieję, że ktoś na tym skorzysta).

Sugerowałbym następujące odniesienie:

Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, Nicola Santoro: Wykresy zmieniające się w czasie i sieci dynamiczne. IJPEDS 27 (5): 387-408 (2012)

$\Delta$ . Lub krawędzie, które nie następują okresowo, ale pojawią się w pewnym momencie wykonania algorytmu. - i jest w sumie około 9 klas.

To, co jest naprawdę ważne w tej klasyfikacji, to fakt, że istnieją zależności między różnymi klasami. Więc jeśli rozwiążesz problem w pewnej klasie, rozwiążesz go w każdej innej klasie, w której jest zawarty.

Ci sami autorzy przedstawili algorytmy transmisji na niektórych z wymienionych wykresów. Podali różne wskaźniki wydajności związane z czasem (tj. Inną definicję najkrótszego czasu). W nadawaniu chodzi o to, że każdy węzeł buduje widok sieci w dziedzinie czasu. Odbywa się to poprzez wielokrotne słuchanie sąsiadów i wysyłanie informacji do sąsiadów. Zakładając okresowość, węzeł może określić najkrótszą ścieżkę czasową do innego węzła. Wykorzystuje te informacje w routingu. Więcej informacji można znaleźć w:

Arnaud Casteigts, Paola Flocchini, Bernard Mans, Nicola Santoro: Deterministyczne obliczenia na wykresach zmieniających się w czasie: transmisja w ramach nieustrukturyzowanej mobilności. IFIP TCS 2010: 111-124

$u$$v$$\{(u,x_1), (x_1, x _2), ...., (x _k, v)\}$$u$$v$$v$$u$

Wziąłem udział w wykładzie poprzednich autorów. Z mojego zrozumienia twierdzą oni, że daleko nam do radzenia sobie z algorytmami grafów dynamicznych (zgodnie z podanymi przez nie definicjami). Że wciąż jesteśmy w przypadku prostych klas. W rzeczywistości twierdzą, że większość mobilnych algorytmów obliczeniowych po prostu zakłada, że ​​ich algorytmy są zbyt szybkie, aby można je było wykonać, gdy sieć się zmienia! (które, jak sądzę, dużo słyszałem) - Lub po prostu załóż okresowość wyglądu krawędzi (zobacz sieci tolerujące opóźnienia itp.)