Informatyka graphs

1

Ile najkrótszych odległości zmienia się podczas dodawania krawędzi do wykresu?

Niech będzie jakimś kompletnym, ważonym, niekierowanym wykresem. Budujemy drugi wykres , dodając krawędzie jeden po drugim od do . Łącznie dodajemy krawędzie do .G ′ = ( V , E ′ ) E E ′ Θ ( | V | ) G ′G = ( V, E)G=(V,E)G=(V,E)sol′= ( V, E′)G′=(V,E′)G'=(V, …

22 algorithms graphs graph-theory shortest-path

2

Czy algorytm Dijkstry to tylko BFS z kolejką priorytetową?

Według tej strony algorytm Dijkstry to po prostu BFS z kolejką priorytetową. Czy to naprawdę takie proste? Myślę, że nie.

22 algorithms graphs shortest-path

2

Uzyskiwanie ujemnego cyklu za pomocą Bellmana Forda

Muszę znaleźć cykl ujemny na ukierunkowanym wykresie ważonym. Wiem, jak działa algorytm Bellmana Forda i który mówi mi, czy istnieje możliwy do osiągnięcia cykl ujemny. Ale nie określa go wprost. Jak uzyskać rzeczywistą ścieżkę cyklu?v1,v2,…vk,v1v1,v2,…vk,v1v1, v2, \ldots vk, v1 Po zastosowaniu standardowego algorytmu wykonaliśmy już iteracji i dalsza poprawa nie …

20 algorithms graphs shortest-path

2

Znajdowanie co najmniej dwóch ścieżek o tej samej długości na ukierunkowanym wykresie

Załóżmy, że mamy skierowany wykres i dwa węzły A i B . Chciałbym wiedzieć, czy istnieją już algorytmy do obliczania następującego problemu decyzyjnego:G = ( V, E)G=(V,E)G=(V,E)ZAAAbBB Czy istnieją co najmniej dwie ścieżki między i B o tej samej długości?ZAAAbBB Co powiesz na złożoność? Czy mogę to rozwiązać w czasie …

20 complexity-theory graph-theory time-complexity graphs

2

Czy drzewa cięte łączem są kiedykolwiek wykorzystywane w praktyce do obliczeń maksymalnego przepływu lub innych zastosowań?

Wiele algorytmów maksymalnego przepływu, które zwykle widzę zaimplementowanych, algorytm Dinica, push push i inne, mogą mieć asymptotyczny koszt czasu ulepszony dzięki zastosowaniu dynamicznych drzew (znanych również jako drzewa cięte łączem). Wciśnij etykietę w trybie lub O ( V 3 ) lub O ( V 2 √)O ( V2)mi)O(V.2)mi)O(V^2E)O ( V3))O(V.3))O(V^3)normalnie, …

20 reference-request graphs data-structures network-flow

1

Generujesz dane wejściowe dla algorytmów graficznych do testowania losowego?

Podczas testowania algorytmów powszechnym podejściem jest testowanie losowe: generuj znaczną liczbę danych wejściowych zgodnie z pewnym rozkładem (zwykle jednolitym), uruchom na nich algorytm i sprawdź poprawność. Nowoczesne ramy testowania mogą generować dane wejściowe automatycznie na podstawie podpisu algorytmów, z pewnymi ograniczeniami. Jeśli dane wejściowe są liczbami, listami lub łańcuchami, generowanie …

19 algorithms graphs randomness software-testing

2

Najkrótsza ścieżka na niekierowanym wykresie?

Pomyślałem więc, że należy do tego (choć nieco podstawowego) pytania: Powiedzmy, że mam wykres wielkości 100 węzłów ułożonych we wzór 10x10 (pomyśl szachownica). Wykres jest nieukierowany i nieważony. Poruszanie się po wykresie wymaga przesunięcia o trzy pola do przodu i jedno pole w prawo lub w lewo (podobnie do ruchu …

19 algorithms graphs graph-theory search-algorithms shortest-path

2

Ile krawędzi może mieć wykres unipatyczny?

Wykres unipatyczny jest wykresem ukierunkowanym, tak że istnieje co najwyżej jedna prosta ścieżka z jednego wierzchołka do dowolnego innego wierzchołka. Wykresy unipatyczne mogą mieć cykle. Na przykład podwójnie połączona lista (nie okrągła!) Jest grafem unipatycznym; jeśli lista zawiera elementów, wykres ma cykli o długości 2, w sumie .n - 1 …

19 graphs combinatorics

4

Cel szarego węzła w wyszukiwaniu na głębokości pierwszego wykresu

W wielu implementacjach pierwszego wyszukiwania głębokości, które widziałem (na przykład: tutaj ), kod rozróżnia szary wierzchołek (wykryty, ale nie odwiedzono wszystkich jego sąsiadów) i czarny wierzchołek (odkryty i odwiedzono wszystkich jego sąsiadów) . Jaki jest cel tego rozróżnienia? Wygląda na to, że algorytm DFS nigdy nie odwiedzi odwiedzonego wierzchołka, niezależnie …

19 algorithms graphs search-algorithms graph-traversal

4

Dlaczego wykresy skierowane są ważne?

Chcesz poprawić ten post? Podaj szczegółowe odpowiedzi na to pytanie, w tym cytaty i wyjaśnienie, dlaczego Twoja odpowiedź jest poprawna. Odpowiedzi bez wystarczającej ilości szczegółów mogą być edytowane lub usuwane. Czytaliśmy o algorytmach dla MST, silnej łączności, routingu itp. W grafach ukierunkowanych. Ostatnio ludzie przeprowadzają badania nad algorytmami dynamicznymi i …

18 graphs graph-theory fault-tolerance

2

Jak wdrożyć algorytm AO *?

Zauważyłem, że podczas implementacji algorytmów wyszukiwania stosowane są różne struktury danych. Na przykład używamy kolejek do implementacji pierwszego wyszukiwania szerokości, stosów do implementacji wyszukiwania z głębokości pierwszej i stosów min do implementacji algorytmu A * . W takich przypadkach nie musimy jawnie budować drzewa wyszukiwania. Ale nie mogę znaleźć prostej …

16 algorithms graphs data-structures search-algorithms

2

Oblicz maksymalny przepływ z minimalnego cięcia

Wiemy, że obliczenie maksymalnego przepływu lub. minimalne ograniczenie sieci o przepustowości jest równoważne; por. twierdzenie o maksymalnym przepływie min. cięcie . Mamy (mniej lub bardziej wydajne) algorytmy obliczania maksymalnych przepływów, a obliczanie minimalnego cięcia przy maksymalnym przepływie nie jest ani trudne, ani drogie. Ale co na odwrót? Biorąc pod uwagę …

16 algorithms graphs network-flow

4

Algorytm Dijkstry na wielkich wykresach

Bardzo dobrze znam Dijkstrę i mam konkretne pytanie dotyczące algorytmu. Jeśli mam ogromny wykres, na przykład 3,5 miliarda węzłów (wszystkie dane OpenStreetMap), to oczywiście nie byłbym w stanie mieć wykresu w pamięci, więc wykres jest przechowywany na dysku w bazie danych. Dostępne są biblioteki do obliczania najkrótszych ścieżek na takich …

15 algorithms graph-theory graphs shortest-path

3

Minimalny rozmiar zawarcia DAG w nowy DAG

Mamy DAG. Mamy funkcję na węzłach (luźno mówiąc, numerujemy węzły). Chcielibyśmy utworzyć nowy ukierunkowany wykres z tymi zasadami:fa: V→ N.F:V→NF\colon V\to \mathbb N Tylko węzły o tym samym numerze można zawrzeć w tym samym nowym węźle. . (Jednak .)fa( x ) ≠ F.( y) ⇒ x′. Y′F(x)≠F(y)⇒x′≠y′F(x) \neq F(y) \Rightarrow …

15 algorithms graphs np-complete reductions

4

Wykres ma dwa / trzy różne minimalne drzewa rozpinające?

Próbuję znaleźć skuteczną metodę wykrywania, czy dany wykres G ma dwa różne minimalne drzewa rozpinające. Próbuję również znaleźć metodę, aby sprawdzić, czy ma 3 różne minimalne drzewa rozpinające. Naiwnym rozwiązaniem, o którym myślałem, jest jednorazowe uruchomienie algorytmu Kruskala i znalezienie całkowitej masy minimalnego drzewa opinającego. Później, usuwając krawędź z wykresu …

15 algorithms graph-theory graphs spanning-trees

Pytania otagowane jako graphs