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ż

Algorytm Kruskala – algorytm wyznaczający minimalne drzewo rozpinające. Algorytm ten wykorzystuje strategię zachłanną, zawsze zwraca rozwiązanie optymalne.

→ 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ść

Notacja dużego O – notacja przedstawiająca asymptotyczne tempo wzrostu, wykorzystywana do zapisywania złożoności obliczeniowej algorytmu. Za pomocą tej notacji zapisywany jest rząd wielkości funkcji wyrażającej liczbę operacji dominujących (w przypadku złożoności czasowej) lub rozmiar wymaganej pamięci (w przypadku złożoności pamięciowej) w zależności od liczby danych wejściowych.

Wykorzystując notację dużego O nie podajemy dokładnego wzoru funkcji, a jedynie jej najbardziej znaczący składnik, w dodatku z pominięciem stałego współczynnika. Przykładowo, funkcję postaci f(n)=5n2+20n+100 możemy zapisać jako O(n2). Zakładamy bowiem, że dla dostatecznie dużych n wpływ pomijanych elementów jest znikomy. Choć oczywiście dla małych n może się zdarzyć, że funkcja o gorszej złożoności będzie się wykonywała szybciej.

Weźmy dla przykładu funkcje f(n) = 1000n+2000 i g(n) = n2. Choć pierwsza funkcja ma pozornie bardzo duże stałe współczynniki, to dla n ≥ 1002 będzie ona przyjmowała wartości mniejsze. Im większe n, tym ta różnica będzie wyraźniejsza. Dla n = 10000 (w przypadku danych przetwarzanych komputerowo nie jest to wielka wartość) f(n) = 10002000 (ok. 10 mln), a g(n) = 100000000 (100 mln), czyli blisko 10 razy więcej.

Możliwe jest również wykorzystanie notacji dużego O dla funkcji wielu zmiennych. Wówczas zapis może wyglądać tak: O(v2e). Znajduje to zastosowanie np. dla algorytmów operujących na grafach, gdzie złożoność zależy zarówno od liczby wierzchołków, jak i liczby krawędzi w grafie.

→ Czytaj całość
Polityka prywatnościKontakt