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

15

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)
Prakash
źródło

Odpowiedzi:

12

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 .(mi,fa)

  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.

Lucas Cook
źródło
Wielkie dzięki za odpowiedź. Próbowałem zrozumieć złożoność i sposoby rozwiązania prostego częściowo dynamicznego problemu graficznego.
Prakash
Wielkie dzięki za odpowiedź. Przejrzę papiery. Próbowałem zrozumieć złożoność i sposoby rozwiązania prostego częściowo dynamicznego problemu graficznego. Na przykład, biorąc pod uwagę zestaw miast połączonych drogami, niekierowanych i ważonych odległością. Znajdź najkrótszą drogę między 2 miastami w n instancjach, gdy droga jest zablokowana w każdym z różnych powodów. Uruchamianie Dijkstry na przykład jest niepraktyczne, czy istnieje sposób na dostosowanie istniejących algorytmów, takich jak A *, w celu rozwiązania tych problemów w lepszym czasie, lub podejścia omówione w dokumentach to jedyna droga.
Prakash
A * to uogólnienie heurystyki Dijkstra +; wydajność jest podobna w najgorszym przypadku. Dla mnie ważnym pytaniem dla twojego problemu jest „jaki rodzaj informacji możesz przechowywać między instancjami, które przyspieszą kolejną instancję?” Np. Jeśli zachowam poprzednią najkrótszą ścieżkę, będę mógł szybko dowiedzieć się, czy „nie powiodła się”, ale nie ma oczywistego sposobu na obliczenie następnej najkrótszej ścieżki. (Nawet jeśli przechowujesz k najkrótszych ścieżek z poprzedniej instancji, podejrzewam, że dotyczy to dowolnego k.)
Lucas Cook
(Mój poprzedni komentarz mówi głównie o najgorszych rozwiązaniach. Może zależy Ci na przeciętnym przypadku? Może być więc heurystyka, która tworzy dobre rozwiązanie typu A *).
Lucas Cook
10

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)

Piotr
źródło
Czy te algorytmy przekazywania komunikatów nie mają problemów z (brakiem) konwergencji?
Raphael
Nie jestem pewien, czy rozumiem, co masz na myśli przez „konwergencję”. Tak długo, jak wykres pozostaje połączony w każdej rundzie, liczba węzłów, które widziały konkretny token, wzrośnie o co najmniej 1. Zatem po n rundach wszyscy zobaczą t, bez względu na to, jak przeciwnik zmieni topologię.
Peter
Myślałem o problemie liczenia do nieskończoności spowodowanym zmianą topologii.
Raphael
@Raphael W rozproszonej dynamice badacze zwykle badają, które właściwości mogą być najgorszym przypadkiem zagwarantowanym w określonym czasie. Zatem „konwergencji” nie można zagwarantować dla wektora odległości / Bellmana-Forda z powodu fundamentalnych problemów z techniką w dynamicznym środowisku. Istnieją inne zbieżne protokoły routingu, które nie mają problemu z liczeniem do nieskończoności.
Lucas Cook
3

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)

Δ . 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

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

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.)

AJed
źródło