Algorytmy. Ćwiczenia
34,90 zł
PHP 7. Algorytmy i struktury danych
−30%41,30 zł
PHP 7. Algorytmy i struktury danych
−30%41,30 zł
Python. Uczenie maszynowe
69,00 zł
Android Studio. Tworzenie aplikacji mobilnych
69,00 zł
JavaScript i jQuery. Interaktywne strony WWW dla każdego
99,00 zł

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 Przykładowe wykonanie algorytmu
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 The Traveling Salesman Problem: A Case Study in Local Optimization (link w bibliografii) złożoność obliczeniowa algorytmu to O(n2log n).

Algorytm nie daje gwarancji znalezienia rozwiązania optymalnego. Według wspomnianej pracy The Traveling Salesman Problem: A Case Study in Local Optimization rozwiązania znalezione przez ten algorytm są średnio o ok. 16% gorsze od optymalnych. Istnieją przypadki, w których algorytm najbliższego sąsiada daje najgorsze możliwe rozwiązanie.

Bibliografia

  1. D.S. Johnson, L.A. McGeoch, The Traveling Salesman Problem: A Case Study in Local Optimization (link) [dostęp: 21 listopada 2017].
  2. G. Gutin, A. Yeo, A. Zverovich, Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP (link) [dostęp: 21 listopada 2017].
Ocena: 0 Tak Nie
Liczba głosów: 0.

Dodano: 19 października 2016 19:21, ostatnia edycja: 21 listopada 2017 19:10.

Zobacz też

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

Algorytm Bellmana-Forda – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. W odróżnieniu od algorytmu Dijkstry, algorytm Bellmana-Forda dopuszcza krawędzie o ujemnych wagach, nie mogą istnieć jednak ujemne cykle osiągalne z wierzchołka źródłowego. Algorytm może być również wykorzystywany do sprawdzania, czy w grafie występują ujemne cykle.

Algorytm występuje również pod nazwą algorytm Bellmana-Forda-Moore’a.

→ Czytaj całość

Algorytm heurystyczny, heurystyka – algorytm poszukujący najlepszego spośród wielu dostępnych rozwiązań. Algorytmy heurystyczne w ogólnym przypadku nie dają gwarancji znalezienia rozwiązania optymalnego, jednak pozwalają znaleźć rozwiązanie dość dobre w stosunkowo krótkim czasie.

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).

→ Czytaj całość
Polityka prywatnościKontakt