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.
- 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.
- Dynamiczne algorytmy grafowe D. Eppstein, Z. Galil, GF Italiano (1999)
- Najkrótsze ścieżki na wykresach dynamicznych G. Nannicini, L. Liberti (2008)
źródło
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)
źródło
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)
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
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.)
źródło