Introducing
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
Najkrótsze ścieżki - Michał Ochenduszkiewicz 1a
5
Najkrótsze ścieżki
O tym, jak najszybciej dostać się z A do B
Michał Ochenduszkiewicz
Wstęp
W dzisiejszych czasach bardzo często korzystamy z nawigacji samochodowej, np. wbudowaną w mapy Google. Jedną z jej funkcji jest obliczanie najkrótszej trasy pomiędzy dwoma wybranymi przez nas punktami. Program uwzględnia przy tym długość dróg, dopuszczalną prędkość, a ostatnio także ich stan (to, czy określone odcinki są zamknięte), korki oraz wypadki. W jaki sposób obliczana jest najbardziej optymalna droga?
Graf skierowany
Potraktujmy sieć dróg jako ważony graf skierowany. Niech każde skrzyżowanie będzie jakimś jego wierzchołkiem, a droga - krawędzią. Wagą tych krawędzi będzie wartość funkcji wyznaczającej oczekiwany czas przejazdu tą drogą, czyli dla przykładu iloraz długości drogi oraz dopuszczalnej prędkości na niej.
Prostsze problemy
Na początek rozważmy problem najkrótszej ścieżki dla:
- drzewa
- grafu nieważonego
Odpowiedzi
W przypadku drzewa wystarczy puścić dowol-ny algorytm przeszukiwania grafu (DFS lub BFS) z początkowego wierzchołka. Z uwagi na fakt, iż w drzewie istnieje dokładnie jedna ścieżka pomiędzy dwoma wierzchołkami, ta jedna ścieżka będzie tą najkrótszą. Odległość między nimi równa jest sumie odległości między kolejnymi wierzchołkami, które będziemy po drodze odwiedzać.
Dla nieważonego grafu użyjemy BFS. Zauważmy, że jeśli określony wierzchołek X jest odległy o n od początkowego wierzchołka A, wszystkie nieodwiedzone wierzchołki, do których można dojść bezpośrednio z X będą oddalone od A o n+1. W ten sposób otrzymamy grupy punktów oddalonych od A o ustaloną odległość.
Algorytm Dijkstry
Część 1
Przejdźmy do sedna sprawy. Problem najkrótszej ścieżki pojawia się również na Olimpiadzie Informatycznej. Problemy algorytmiczne na OI różnią się jednak od rzeczywistych sytuacji, gdzie można sobie pozwolić na bardziej heurystyczne algorytmy. Tak czy inaczej, podstawowym algorytmem znajdowania najkrótszej ścieżki na OI jest algorytm Dijkstry. Jak on działa?
Działanie
Będziemy chcieli stworzyć tablicę d[V] odległości od wyjściowego punktu A, które początkowo będą wynosić nieskończoność (poza d[A]=0). Wrzućmy wszystkie wierzchołki na kolejkę priorytetową, której priorytetem jest aktualnie wyliczona odległość od A. Będziemy z tej kolejki zdejmować najbliższy A nierozważony jeszcze wierzchołek. Dla każdego wierzchołka x, do którego można dojść z A rozważamy, czy d[A] + u(A,x) < d[x], gdzie u(A,x) to waga krawędzi między A a x. Jeśli tak, to d[x]:=d[A] + u(A,x).
Algorytm Bellmana-Forda
Część 2
Algorytm Dijkstry ma jedną wadę: nie działa, gdy w grafie występują krawędzie o ujemnej wadze. Tu z pomocą przychodzi nam algorytm Bellmana-Forda. Kosztem większej złożoności obliczeniowej obliczy nam on odpowiedni wynik lub poinformuje o ujemnym cyklu w grafie (wtedy nie ma sensu obliczanie najkrótszej ścieżki, ponieważ ciągle chodząc po ujemnym cyklu będziemy coraz bardziej zmniejszać jej wartość, aż stanie się ona nieskończenie mała).
Działłanie
Działanie
Tutaj również będziemy chcieli początkowo przypisać każdemu wierzchołkowi poza A nieskończone d[x]. Różnica jest taka, że zamiast kolejki priorytetowej będziemy wszystkie wierzchołki rozważać po kolei. Dla każdego wierzchołka B rozważymy wszystkich jego sąsiadów x. Jeśli d[x]>d[B]+u(B,x), d[x]:=d[B]+u(B,x).
Odległości między wszy-
stkimi wierzchołkami
Część 3
Powyższe algorytmy służyły do obliczania odległości od pojedynczego wierzchołka. Jeśli mielibyśmy rozważyć odległości między wszystkimi parami wierzchołków, zastosowanie V razy (V - liczba wierzchołków) tych algorytmów często nie jest najlepszym rozwiązaniem. Wówczas stosujemy algorytmy Floyda-Warshalla lub Johnsona.
Algorytm Floyda-Warshalla
Algorytm Floyda-Warshalla
Algorytm Floyda-Warshalla znajduje odległości między każdą parą wierzchołków lub stwierdza istnienie ujemnego cyklu. Jego zasada działania jest dziecinnie prosta. Utwórzmy dwuwymiarową tablicę d[V][V]. Jeśli istnieje krawędź między A i B, d[A][B] jest równe jej wadze. d[A][A] jest równe 0 dla każdego wierzchołka. Dalszą część algorytmu ilustruje następujący pseu-dokod:
dla każdego wierzchołka k od 1 do n:
dla każdego wierzchołka i od 1 do n:
dla każdego wierzchołka j od 1 do n:
jeśli d[i][j]>d[i][k]+d[k][j]:
d[i][j]:=d[i][k]+d[k][j]
//sprawdzenie, czy jest ujemny cykl
dla każdego wierzchołka k od 1 do n:
jeśli d[k][k]<0: istnieje ujemny cykl
Algorytm Johnsona
Algorytm Johnsona
Algorytm Johnsona to de facto złożenie 2 algorytmów. Najpierw do naszego grafu dodamy wierzchołek Q połączony z każdym wierzchołkiem krawędzią o wadze 0. Puśćmy z niego algorytm Bellmana-Forda, który albo wykryje ujemny cykl, albo zwróci tablicę h[V} odległości poszczególnych wierzchołków od Q. Każdej krawędzi (u,v) przypiszemy nową wagę w(u,v):=w(u,v)+h[u]-h[v]. Usuwamy wierzchołek Q i po tak zmodyfikowanym grafie puszczamy z każdego wierzchołka algorytm Dijkstry. Jeśli wiemy, że graf nie zawiera ujemnych krawędzi, możemy po prostu wywołać algorytm Dijkstry z każdego wierzchołka. Algorytm Johnsona jest szybszy niż algorytm Floyda-Warshalla dla grafów rzadkich, czyli o względnie małym stosunku liczby krawędzi do liczby wag.
Zakończenie
Powyższe algorytmy mają spore zastosowanie nie tylko na Olimpiadzie Informatycznej, ale i w prawdziwym życiu. W przypadku wyznaczania najkrótszej drogi na mapie są jednak za wolne. Nie możemy pozwolić sobie na przetworzenie wszystkich skrzyżowań. Musimy zastosować coś szybszego, być może jakąś heurystykę lub ich szereg. Z pomocą przychodzi nam dużo szybszy, ale heurystyczny (co skreśla go na OI) algorytm A* i jego odmiany. Z uwagi na mnogość jego odmian i możliwych heurystyk pozwolę sobie go nie omawiać. Przykładowe jego wersje znaleźć można na Wikipedii.
Podsumowanie
- Problem znalezienia najszybszej trasy na mapie sprowadza się do problemu naj-krótszej ścieżki w grafie.
- Do znalezienia najkrótszej ścieżki z poje-dynczego wierzchołka używamy zależnie od sytuacji algorytmów BFS, DFS, Dijkstry, Bellmana-Forda i A*.
- Aby znaleźć najkrótsze ścieżki pomiędzy każdą parą wierzchołków w grafie, możemy poza wielokrotnym wywołaniem powyższych algorytmów zastosować algorytmy Floyda-Warshalla i Johnsona.
Koniec
Teraz już serio koniec
Dziękuję za uwagę.