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: 1.

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

REKLAMA

Zobacz też

Ten artykuł opisuje algorytm rozwiązujący problem wydawania reszty oparty na programowaniu dynamicznym. Algorytm ten daje gwarancję znalezienia rozwiązania optymalnego.

Istnieje również pewna modyfikacja tego algorytmu, która została opisana w osobnym artykule.

→ Czytaj całość

Quicksort, sortowanie szybkie – algorytm sortowania działający w średnim przypadku w czasie liniowo-logarytmicznym. Algorytm jest oparty na metodzie dziel i zwyciężaj. Nie jest to algorytm stabilny ani wykazujący zachowanie naturalne, jednak ze względu na efektywność jest algorytmem bardzo popularnym.

→ Czytaj całość

Algorytm Edmondsa-Karpa – algorytm wyszukiwania maksymalnego przepływu w sieci przepływowej. Jest to przypadek szczególny algorytmu Forda-Fulkersona.

W algorytmie Edmondsa-Karpa ścieżka powiększająca wyznaczana jest za pomocą przeszukiwania grafu wszerz. Dzięki temu w każdej iteracji algorytmu dołączana jest zawsze najkrótsza (pod względem liczby krawędzi) ścieżka powiększająca. W metodzie Forda-Fulkersona sposób wyznaczania ścieżki powiększającej jest dowolny.

→ Czytaj całość
Polityka prywatnościKontakt