K-opt

2-opt przykład (1) Przykładowe wykonanie algorytmu 2-optymalnego
3-opt przykład (2) 8 sposobów połączenia ze sobą 3 fragmentów cyklu (jeden krok algorytmu 3-opt)

K-opt, algorytm k-optymalny – algorytm lokalnej optymalizacji wykorzystywany przy rozwiązywaniu problemu komiwojażera. Algorytm ten nie służy do samego wyznaczania trasy, a jedynie do ulepszania jej. Najprostszą wersją tego algorytmu jest algorytm 2-optymalny.

Działanie algorytmu

Algorytm polega na usuwaniu z cyklu k krawędzi i zastępowaniu ich innymi krawędziami tak, aby utworzyć inny prawidłowy cykl. Jeśli osiągnięte w ten sposób rozwiązanie jest lepsze od dotychczas znalezionego, zapamiętujemy je. Za każdym razem modyfikujemy cykl początkowy (nie rozwiązanie z poprzedniego kroku).

Usunięcie z cyklu k krawędzi sprawia, że cykl zostaje podzielony na k fragmentów. Należy sprawdzić wszystkie możliwości połączenia tych fragmentów w całość. Taki krok algorytmu należy powtórzyć dla każdej k-elementowej grupy krawędzi.

Algorytm można wykonywać kilkakrotnie, aż do momentu, w którym żadna modyfikacja nie spowoduje skrócenia trasy. W ten sposób osiągnięte zostanie minimum lokalne.

Złożoność obliczeniowa

Załóżmy, że mamy cykl liczący n krawędzi. Jeśli chcemy usunąć z niego k krawędzi, to możemy uczynić to na n!/(k!(n-k)!) sposobów (kombinacja z n po k). Dla każdej kombinacji musimy sprawdzić wszystkie możliwości połączenia fragmentów cyklu w inny sposób. Fragmenty te możemy ustawić w różnej kolejności na (k-1)! sposobów. Dodatkowo każdy fragment można odwrócić, czyli wartość tę musimy pomnożyć przez 2k-1. Jest to oszacowanie z pewnym nadmiarem – jeśli dany fragment jest jednoelementowy, to nie trzeba go odwracać (im większe k, tym więcej będzie takich elementów, zatem dla dużych k czynnik ten będzie zanikał).

Podsumowując, mamy do sprawdzenia maksymalnie n!2k-1/(k(n-k)!) wariantów. Jest to złożoność rzędu O(nk), przy czym nawet dla dużych k złożoność nie przekroczy n!.

Biorąc pod uwagę, że złożoność algorytmu w zależności od k jest wykładnicza, w praktyce używa się tylko niewielkich wartości k, zazwyczaj 2 lub 3. Dla k=n wykonanie algorytmu byłoby tożsame ze sprawdzeniem wszystkich możliwych rozwiązań problemu komiwojażera.

Ocena: 0 Tak Nie
Liczba głosów: 0.

Dodano: 17 czerwca 2017 15:20, ostatnia edycja: 17 czerwca 2017 16:08.

REKLAMA

Zobacz też

K-opt, algorytm k-optymalny – algorytm lokalnej optymalizacji wykorzystywany przy rozwiązywaniu problemu komiwojażera. Algorytm ten nie służy do samego wyznaczania trasy, a jedynie do ulepszania jej. Najprostszą wersją tego algorytmu jest algorytm 2-optymalny.

→ Czytaj całość

Algorytm Helda-Karpa (czasami określany jako algorytm Bellmana-Helda-Karpa) – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm dokładny oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n22n) i złożoność pamięciową O(n2n). Jest to co prawda złożoność gorsza od wielomianowej, ale algorytm ten jest znacznie lepszy od algorytmu sprawdzającego wszystkie warianty (złożoność czasowa O(n!)).

→ 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