Problem najkrótszej ścieżki - Polski Serwis Naukowy

Problem najkrótszej ścieżki jest zagadnieniem szczególnie istotnym w informatyce. Polega on na znalezieniu w grafie ważonym najkrótszego połączenia pomiędzy danymi wierzchołkami. Szczególnymi przypadkami tego problemu są problem najkrótszej ścieżki od jednego wierzchołka do wszystkich innych oraz problem najkrótszej ścieżki pomiędzy wszystkimi parami wierzchołków.

Minimalne drzewo rozpinające (ang. MST, Minimum Spanning Tree ) jest to drzewo rozpinające danego grafu o najmniejszej z możliwych wag, tj. takie, że nie istnieje dla tego grafu inne drzewo rozpinające o mniejszej sumie wag krawędzi.

Informatyka (łac. informatio - "wyobrażenie", "wizerunek", "pomysł", ang. computer science, computing science, information technology, informatics) – dziedzina nauki i techniki zajmująca się przetwarzaniem informacji – w tym technologiami przetwarzania informacji oraz technologiami wytwarzania systemów przetwarzających informacje. Pierwotnie część matematyki, została rozwinięta do osobnej dyscypliny nauki, pozostaje jednak nadal w ścisłym związku z matematyką, która dostarcza jej podstaw teoretycznych.

Okazuje się, że żeby znaleźć najkrótszą ścieżkę pomiędzy dwoma wierzchołkami grafu trzeba (w pesymistycznym przypadku) znaleźć najkrótsze ścieżki od wierzchołka wyjściowego do wszystkich innych wierzchołków. Problem najkrótszej ścieżki od jednego z wierzchołków do wszystkich innych można więc zobrazować jako problem znalezienia najkrótszej drogi pomiędzy dwoma miastami. W takim wypadku wierzchołkami grafu są skrzyżowania dróg, krawędziami – drogi, a wagi krawędzi odwzorowują długość danego odcinka drogowego. Do znalezienia najkrótszej ścieżki pomiędzy dwoma wierzchołkami zazwyczaj używane są algorytmy:

Problem komiwojażera (TSP - ang. traveling salesman problem) jest to zagadnienie z teorii grafów, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.

Algorytm Johnsona - algorytm znajdowania najkrótszych ścieżek między wszystkimi parami wierzchołków. Działa w czasie O( | V | 2lg | V | + | V | | E | ) (zakładając, że wykonuje algorytm Dijkstry przy użyciu kolejek priorytetowych opartych o kopce Fibonacciego), dla grafów rzadkich jest więc asymptotycznie szybszy od algorytmu Floyda-Warshalla. Algorytm Johnsona zwraca albo macierz wag najkrótszych ścieżek, albo informuje, że graf wejściowy ma cykl o ujemnej wadze. W algorytmie Johnsona jako podprogramy używane są algorytmy Dijkstry i Bellmana-Forda.

Dijkstry (przy założeniu, że w grafie nie ma wag ujemnych) o pesymistycznej złożoności obliczeniowej $O(V\,\log{V}+E)$ ,

Bellmana-Forda o pesymistycznej złożoności obliczeniowej $O(VE)$ ,

A*, używający heurystyki,

nienazwany (przy założeniu, że graf jest skierowany i nie ma cykli) o pesymistycznej złożoności obliczeniowej $O(V+E)$ ,

gdzie V to liczba wierzchołków grafu, a E to liczba jego krawędzi.

Heurystyka (gr. heuresis – odnaleźć, odkryć, heureka – znalazłem) - w informatyce metoda znajdowania rozwiązań, dla której nie ma gwarancji znalezienia rozwiązania optymalnego, a często nawet prawidłowego. Rozwiązań tych używa się np. wtedy, gdy pełny algorytm jest z przyczyn technicznych zbyt kosztowny, lub gdy jest nieznany (np. przy przewidywaniu pogody lub przy wykrywaniu niektórych zagrożeń komputerowych, takich jak wirusy lub robaki). Metody używa się też często do znajdowania rozwiązań przybliżonych, na podstawie których później wylicza się ostateczny rezultat pełnym algorytmem. To ostatnie zastosowanie szczególnie dotyczy przypadków, gdy heurystyka jest wykorzystywana do nakierowywania pełnego algorytmu ku optymalnemu rozwiązaniu, aby zmniejszyć czas działania programu w typowym przypadku bez poświęcania jakości rozwiązania (np. algorytm A*).

Algorytm – w matematyce oraz informatyce skończony, uporządkowany ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism - przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.

Drugi szczególny przypadek problemu najkrótszej ścieżki występuje, gdy chcemy znaleźć najkrótsze ścieżki pomiędzy każdą parą wierzchołków. Oczywiście możliwe jest zrobienie tego dla każdego wierzchołka używając algorytmu znajdującego najkrótszą ścieżkę od jednego wierzchołka do wszystkich innych, jednak metoda ta okazuje się w praktyce niezbyt efektywna. Najkrótsze ścieżki pomiędzy wszystkimi wierzchołkami znajdują m.in. algorytmy:

Problem marszrutyzacji - problem decyzyjny polegający na wyznaczeniu optymalnych tras przewozowych dla pewnej ściśle określonej ilości środków transportu, której zadaniem jest obsłużenie zbioru klientów znajdujących się w różnych punktach przy zachowaniu ograniczeń. Kryterium optymalizacji jest całkowity koszt transportu (wyrażony odległościowo, cenowo lub czasowo). Istnieją również rozwinięcia problemu uwzględniające więcej, niż jedno kryterium optymalizacji. Problem marszrutyzacji należy do podstawowej problematyki zarządzania operacyjnego flotą środków transportu (rzadziej zarządzania na wyższym szczeblu).

Krawędź grafu jest to para (zbiór dwuelementowy) wyróżnionych wierzchołków grafu, czyli takich, które są ze sobą połączone (sąsiednie). W reprezentacji graficznej jest to linia łącząca te wierzchołki. W szczególności krawędź może łączyć dwa te same wierzchołki i jest wówczas nazywana pętlą. Krawędź skierowaną, czyli będącą parą uporządkowanych wierzchołków, nazywamy łukiem.

nienazwany (wykorzystuje mnożenie macierzy) o pesymistycznej złożoności obliczeniowej $O(V^3\,\log{V})$

Floyda-Warshalla o pesymistycznej złożoności obliczeniowej $O(V^3)$ ,

Johnsona o pesymistycznej złożoności obliczeniowej $O(V^2\,\log{V}+VE)$

gdzie V to liczba wierzchołków, a E liczba krawędzi.

Zobacz też

minimalne drzewo rozpinające

problem komiwojażera

problem marszrutyzacji