Algorytm Floyda-Warshalla
Algorytm Floyda-Warshalla – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Jest to algorytm oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n3) i złożoność pamięciową O(n2), gdzie n jest liczbą wierzchołków.
Algorytm dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli. Algorytm może być również wykorzystywany do wyszukiwania ujemnych cykli w grafie.
Działanie algorytmu
Tworzymy dwie macierze o wymiarach n na n. W pierwszej macierzy będziemy przechowywać odległości między punktami, w drugiej identyfikatory przedostatnich punktów na ścieżce łączącej punkty. Bardziej formalnie, wartość di,j oznacza odległość z punktu i do punktu j, a wartość pi,j oznacza punkt poprzedzający punkt j na ścieżce z punktu i do punktu j.
Na początku inicjujemy wartości w macierzach. Jeśli istnieje krawędź prowadząca z punktu i do punktu j, to wartości di,j przypisujemy długość tej krawędzi, a wartość pi,j ustawiamy na i. W przeciwnym razie wartości di,j przypisujemy nieskończoność, a wartość pi,j traktujemy jako niezdefiniowaną. Długości ścieżek prowadzących do tego samego punktu, z którego wychodzą, ustawiamy na 0.
Następnie wykonujemy zasadniczą część algorytmu:
- Dla każdego punktu u ze zbioru wierzchołków:
- Dla każdego punktu v1 ze zbioru wierzchołków:
- Dla każdego punktu v2 ze zbioru wierzchołków:
- Jeśli dv1, v2 > dv1, u + du, v2, to:
- dv1, v2 = dv1, u + du, v2,
- pv1, v2 = pu, v2.
Po wykonaniu algorytmu macierze zawierają optymalne rozwiązania. Ścieżkę między dwoma dowolnymi punktami można odczytać wykorzystując wartości znajdujące się w macierzy p. Jeśli po wykonaniu algorytmu wartość di,j nadal wynosi nieskończoność, to oznacza, że nie istnieje żadna ścieżka prowadząca z punktu i do punktu j.
Jeśli po wykonaniu algorytmu na głównej przekątnej macierzy odległości znajduje się wartość mniejsza od zera, to graf zawiera ujemny cykl.
Złożoność obliczeniowa
Algorytm zawiera trzy zagnieżdżone pętle, w każdej z nich przeglądane są wszystkie wierzchołki. Złożoność czasowa algorytmu wynosi zatem O(n3) (n jest liczbą wierzchołków). Dane są przechowywane w dwóch macierzach o wymiarach n na n. Złożoność pamięciowa algorytmu wynosi zatem O(n2).
Liczba głosów: 1.
- Algorytm Bellmana-Forda
- Algorytm Dijkstry
- Algorytm Floyda-Warshalla
- Algorytm Johnsona
Dodano: 9 sierpnia 2017 13:51, ostatnia edycja: 10 sierpnia 2017 15:02.
Zobacz też
Algorytm – przepis, zbiór poleceń, opis ciągu operacji prowadzących do rozwiązania konkretnego problemu. Algorytm możemy również rozumieć jako funkcję przekształcającą dane wejściowe w dane wyjściowe.
Algorytm musi być skończony, czyli jego zapis ma składać się ze skończonej liczby znaków. Musi również być poprawny, czyli dla wszystkich możliwych danych wejściowych powinien zwracać prawidłowy wynik (może być nim informacja o braku rozwiązania). Algorytm musi wykazywać również własność stopu – niezależnie od danych wejściowych obliczenia algorytmu powinny dochodzić do punktu końcowego, czyli po prostu kończyć się (nie mogą np. wpadać w nieskończoną iterację). Zapis algorytmu musi być precyzyjny, bez jakichkolwiek niejasności.
Algorytm heurystyczny, heurystyka – algorytm niedający (w ogólnym przypadku) gwarancji znalezienia rozwiązania optymalnego, umożliwiający jednak znalezienie rozwiązania dość dobrego w rozsądnym czasie. Algorytmy tego typu używane są w takich problemach obliczeniowych, gdzie znalezienie rozwiązania optymalnego ma zbyt dużą złożoność obliczeniową (w szczególności są to problemy NP-trudne) lub w ogóle nie jest możliwe. Metody heurystyczne zaliczają się do sztucznej inteligencji.
Pojęcie algorytmów heurystycznych jest bardzo szerokie, dotyczy ono różnych technik projektowania algorytmów. Wiele heurystyk wykorzystuje losowość, inne zaś są deterministyczne (wówczas dla takich samych danych wejściowych algorytm zawsze zwróci ten sam wynik).
Ogólny algorytm heurystyczny (opisujący samą ideę poszukiwań) bywa określany w literaturze jako metaheurystyka. Zgodnie z tym nazewnictwem, metaheurystyką jest np. algorytm zachłanny (jako ogólna idea), zaś heurystyką jest np. algorytm najbliższego sąsiada (jako zastosowanie idei algorytmu zachłannego do konkretnego problemu).
Przykładowe techniki konstruowania algorytmów heurystycznych to:
- przeszukiwanie lokalne,
- algorytmy zachłanne,
- symulowane wyżarzanie,
- przeszukiwanie tabu,
- algorytmy genetyczne.
Algorytm genetyczny – metaheurystyka inspirowana biologiczną ewolucją.
Pojęcie algorytmu genetycznego nie jest powiązane z żadnym konkretnym problemem obliczeniowym, algorytm ten może być wykorzystywany do rozwiązywania różnych problemów. Algorytm genetyczny nie próbuje rozwiązywać problemu w sposób analityczny, ale próbuje uzyskać jak najlepsze rozwiązania poprzez wybieranie jak najlepszych cech rozwiązań z określonej puli. Implementując algorytm genetyczny należy przedstawić potencjalne rozwiązanie problemu w postaci jakiejś struktury danych, a następnie zdefiniować operacje krzyżowania, mutacji i selekcji. Zakładamy, że z każdym kolejnym pokoleniem rozwiązania występujące w populacji będą coraz lepsze.