Pytania otagowane jako shortest-path

Pytania o algorytmiczne problemy znalezienia najkrótszych ścieżek między węzłami na grafie.

7
Minimalne drzewo opinające vs Najkrótsza ścieżka
Jaka jest różnica między algorytmem minimalnego drzewa opinającego a algorytmem najkrótszej ścieżki? W mojej klasie struktur danych omówiliśmy dwa algorytmy minimalnego drzewa opinającego (Prim i Kruskala) oraz jeden algorytm najkrótszej ścieżki (Dijkstry). Minimalne drzewo opinające to drzewo na wykresie, które obejmuje wszystkie wierzchołki, a całkowita waga drzewa jest minimalna. Najkrótsza …
3
Pobieranie najkrótszej ścieżki dynamicznego wykresu
Obecnie badam najkrótsze ścieżki na ukierunkowanych wykresach. Istnieje wiele wydajnych algorytmów do znajdowania najkrótszej ścieżki w sieci, takich jak dijkstra lub bellman-ford. Ale co, jeśli wykres jest dynamiczny? Mówiąc dynamiczny, mam na myśli to, że możemy wstawiać lub usuwać wierzchołki podczas wykonywania programu. Próbuję znaleźć skuteczny algorytm do aktualizowania najkrótszych …
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 …
6
Dlaczego DFS nie może być używany do znajdowania najkrótszych ścieżek na nieważonych wykresach?
Rozumiem, że użycie DFS „tak jak jest” nie znajdzie najkrótszej ścieżki na nieważonym wykresie. Ale dlaczego poprawianie DFS, aby umożliwić mu znajdowanie najkrótszych ścieżek na nieważonych wykresach, jest tak beznadziejną perspektywą? Wszystkie teksty na ten temat po prostu stwierdzają, że nie można tego zrobić. Nie jestem przekonany (sam tego nie …
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 …
2
Skutecznie próbkuj najkrótsze ścieżki
Niech GGG jest wykresem, niech sss i ttt są dwa wierzchołki GGG . Możemy skutecznie próbki najkrótszą sss - ttt ścieżkę równomiernie i niezależnie losowo ze zbioru wszystkich najkrótszych ścieżek między sss i ttt ? Dla uproszczenia możemy założyć, że GGG jest prosty, nieukierunkowany i nieważony. Nawet w ograniczonych wielu …
2
Najkrótsza nie przecinająca się ścieżka dla wykresu osadzonego w płaszczyźnie euklidesowej (2D)
Jakiego algorytmu użyłbyś do znalezienia najkrótszej ścieżki wykresu, która jest osadzona w płaszczyźnie euklidesowej, tak aby ścieżka nie zawierała żadnych skrzyżowań własnych (w osadzaniu)? Na przykład na poniższym wykresie chcesz przejść z . Zwykle algorytm taki jak algorytm Dijkstry tworzyłby następującą sekwencję:( 0 , 0 ) → ( - 3 …
2
Algorytm Bellmana-Forda - Dlaczego krawędzie mogą być aktualizowane poza kolejnością?
Algorytm Bellmana-Ford, określa najkrótszą ścieżkę ze źródła, do pozostałych wierzchołków. Początkowo odległość między a wszystkimi innymi wierzchołkami jest ustawiona na . Następnie obliczana jest najkrótsza ścieżka od do każdego wierzchołka; dzieje się tak w przypadku iteracji . Moje pytania to:ssssss∞∞\inftysss|V|−1|V|−1|V|-1 Dlaczego potrzebne są iteracje ?|V|−1|V|−1|V|-1 Czy miałoby to znaczenie, jeśli …
2
Znajdowanie najkrótszych i najdłuższych ścieżek między dwoma wierzchołkami w DAG
Biorąc pod uwagę nieważony DAG (skierowane acykliczny wykres) oraz dwa wierzchołki i , jest możliwe znalezienie najkrótszej ścieżki, a najdłuższy z na w czasie wielomianowym? Długości ścieżek są mierzone liczbą krawędzi.s t s tD=(V,A)D=(V,A)D = (V,A)ssstttsssttt Interesuje mnie znalezienie zakresu możliwych długości ścieżek w czasie wielomianowym. Ps., To pytanie jest …
1
Jak konsekwencja oznacza, że ​​heurystyka jest również dopuszczalna?
Funkcja heurystyczna to ...h(n)h(n)h (n) Spójne, jeśli szacowany koszt od węzła do celu nie jest większy niż koszt kroku do jego następcy plus szacowany koszt od następcy do celu.nnnn′n′n' Dopuszczalne, jeżeli nigdy nie przecenia rzeczywistych kosztów do stanu docelowego.h(n)h(n)h(n) Podręcznik mojego kursu sztucznej inteligencji stwierdza, że ​​spójność jest silniejsza niż …
2
Dlaczego nie możemy znaleźć najkrótszych ścieżek o ujemnych wagach, po prostu dodając stałą, aby wszystkie wagi były dodatnie?
Obecnie czytam wprowadzenie do algorytmów i przyszedłem przez algorytm Johnsona, który polega na upewnieniu się, że wszystkie ścieżki są pozytywne. algo zależy od znalezienia nowej funkcji wagi (w '), która jest dodatnia dla wszystkich krawędzi i zachowuje poprawność relacji najkrótszych ścieżek. Odbywa się to poprzez obliczenie wartości h (s), h …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.