Algorytm najmniejszej krawędzi

Info
Nazwa tego artykułu jest autorskim tłumaczeniem. Prawdopodobnie nie jest to nazwa oficjalnie używana w polskiej literaturze.
Algorytm najkrótszej krawędzi (1) Przykładowe wykonanie algorytmu
Własność wymiany niespełniona (2) Przykład niespełnionej własności wymiany przy próbie przedstawiania problemu komiwojażera za pomocą matroidu. Nie da się do zbioru 3 dodać elementu zbioru 4 w taki sposób, aby uzyskać inny podzbiór poprawnego rozwiązania
Algorytm najmniejszej krawędzi – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm wykorzystujący strategię zachłanną, jednak w inny sposób, niż algorytm najbliższego sąsiada. W anglojęzycznej literaturze algorytm jest najczęściej określany po prostu jako greedy algorithm (algorytm zachłanny), w skrócie GR.

Działanie algorytmu

Algorytm działa podobnie do algorytmu Kruskala poszukującego minimalnego drzewa rozpinającego. Polega on na kolejnym dołączaniu do rozwiązania najkrótszych spośród dopuszczalnych krawędzi. Działanie algorytmu można zapisać następująco:

  1. Posortuj wszystkie krawędzie rosnąco według ich wag, umieść je w kolejce.
  2. Pobierz z kolejki krawędź o najmniejszej wadze, usuń ją z kolejki.
  3. Sprawdź, czy dołączenie tej krawędzi do rozwiązania nie spowoduje utworzenia cyklu (nie dotyczy ostatniej iteracji) lub powstania wierzchołka, z którego wychodzą trzy krawędzie. Jeśli nie, dołącz krawędź do rozwiązania.
  4. Jeśli liczba krawędzi dołączonych do rozwiązania jest równa liczbie wierzchołków, zakończ działanie algorytmu. W przeciwnym razie przejdź do punktu 2.

Złożoność i ocena jakości

Główna pętla algorytmu wykona się maksymalnie n2 razy (n jest liczbą krawędzi). W trakcie każdego przebiegu pętli trzeba jednak sprawdzić, czy daną krawędź można dołączyć do rozwiązania. Złożoność obliczeniowa algorytmu zależy od sposobu implementacji sprawdzania tego warunku, a także od sposobu sortowania kolejki krawędzi. Według pracy [1] złożoność obliczeniowa algorytmu to O(n2log n).

Algorytm nie daje gwarancji znalezienia rozwiązania optymalnego. Jest on wprawdzie podobny do algorytmu Kruskala, jednak problemu komiwojażera (w odróżnieniu od problemu minimalnego drzewa rozpinającego) nie da się przedstawić za pomocą matroidu. Kontrprzykład został przedstawiony na rysunku (2). Według wspomnianej pracy [1], rozwiązania znalezione przez ten algorytm są średnio o ok. 16% gorsze od optymalnych.

Bibliografia

Ocena: +1 Tak Nie
Liczba głosów: 3.

Dodano: 19 października 2016 19:21, ostatnia edycja: 24 kwietnia 2020 20:01.

REKLAMA

Zobacz też

Wyznaczanie najkrótszej ścieżki – zagadnienie polegające na wyszkaniu w grafie takiej ścieżki łączącej dwa wierzchołki, której suma wag krawędzi jest jak najmniejsza.

W przypadku pesymistycznym do wyznaczenia optymalnej ścieżki z wierzchołka A do wierzchołka B konieczne jest wyznaczenie najkrótszych ścieżek z wierzchołka A do wszystkich pozostałych wierzchołków w grafie. Zagadnienie takie jest określane jako poszukiwanie najkrótszych ścieżek z jednego źródła. Do rozwiązywania tego zagadnienia można wykorzystać następujące algorytmy:

Nieco innym zagadnieniem jest poszukiwanie najkrótszych ścieżek pomiędzy każdą parą wierzchołków. W tym celu można wykorzystać algorytmy wymienione powyżej (wykonując je wielokrotnie, za każdym razem przyjmując inny wierzchołek źródłowy) lub algorytmy poszukujące od razu wszystkich ścieżek, takie jak:

Aby znalezienie najkrótszej ścieżki było możliwe, graf nie może zawierać ujemnych cykli osiągalnych z wierzchołka źródłowego. Jeśli taki cykl istnieje, to poruszając się nim „w kółko” cały czas zmniejszamy długość ścieżki. Dopuszczalne jest natomiast występowanie krawędzi o ujemnej wadze, choć nie wszystkie algorytmy dopuszczają ten przypadek.

Jeśli poszukujemy ścieżek o najmniejszej liczbie krawędzi (np. wtedy, gdy wszystkie krawędzie mają taką samą, dodatnią wagę), to zamiast powyższych algorytmów możemy skorzystać z prostego przeszukiwania grafu wszerz.

→ Czytaj całość

Graf – struktura G = (V, E) składająca się ze skończonego zbioru wierzchołków V oraz skończonego zbioru krawędzi E, gdzie każda krawędź e ∈ E jest dwuelementowym zbiorem wierzchołków u, v ∈ V. Wierzchołki u, v połączone krawędzią e = {u, v} określane są sąsiednimi. Grafy mają szerokie zastosowanie w informatyce, można za ich pomocą przedstawiać rożnego rodzaju relacje pomiędzy obiektami.

Powyższa definicja dotyczy grafu nieskierowanego, gdzie relacja sąsiedztwa jest symetryczna, tzn. krawędź łączy wierzchołki „w obie strony”. W grafie skierowanym krawędzie są „jednokierunkowe”. Krawędź grafu skierowanego zazwyczaj jest określana jako łuk.

Graf ważony (inaczej graf z wagami) to taki graf, w którym każdej krawędzi przypisana jest pewna wartość liczbowa. Wartość ta może oznaczać np. długość krawędzi lub jej przepustowość.

→ Czytaj całość

Bogosort – bardzo słaby algorytm sortowania oparty na metodzie prób i błędów. Polega na ustawianiu elementów w losowej kolejności i sprawdzaniu, czy są posortowane. Średnia złożoność tego algorytmu jest rzędu silnia, a w przypadku pesymistycznym algorytm będzie działał w nieskończoność.

Algorytm występuje też w nieco ulepszonej wersji, w której nie sprawdza się wielokrotnie tego samego ustawienia. Wówczas algorytm daje gwarancję znalezienia rozwiązania, jednak jego złożoność czasowa nadal jest rzędu silnia (w przypadku pesymistycznym trzeba sprawdzić wszystkie permutacje zbioru).

Ze względu na bardzo dużą złożoność czasową bogosort nie nadaje się do praktycznych zastosowań. Istnieją proste w implementacji, a znacznie wydajniejsze algorytmy sortujące, np. sortowanie przez wstawianie.

→ Czytaj całość
Polityka prywatnościKontakt