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: -2 Tak Nie
Liczba głosów: 2.

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

REKLAMA

Zobacz też

Metoda z zastosowaniem przepływu blokującego – algorytm wyznaczający maksymalny przepływ w sieci przepływowej. W algorytmie tym przepływ zwiększany jest iteracyjnie, w każdej iteracji wyznaczony przepływ jest powiększany o przepływ blokujący w warstwowej sieci residualnej.

→ Czytaj całość

Matroid – struktura matematyczna składająca się z niepustego zbioru elementów E i takiej rodziny jego podzbiorów I, że spełnione są następujące warunki:

  1. Jeśli jakiś zbiór należy do I, to wszystkie jego podzbiory także należą do I.
  2. Jeśli weźmiemy dowolne dwa zbiory należące do I o różnej liczbie elementów, to jesteśmy w stanie dodać do mniejszego z nich taki element z większego (spośród tych, które nie należą do mniejszego), że utworzony w ten sposób zbiór także będzie należał do I.

Drugi warunek, zwany własnością wymiany, formalnie może być zapisany jako:

$$⋀↙{A,B∊I}↙{ |A|>|B| }⋁↙{t∊(A-B)} B∪\{t\} ∈ I$$

Co istotne, rodzina zbiorów I nie musi zawierać wszystkich możliwych podzbiorów zbioru E. Ważne tylko, aby była spełniona własność wymiany. Przykładowo, dla E={a,b,c,d} prawidłową rodziną I, może być zarówno { {a,b}, {b,c}, {a}, {b}, {c}, ∅}, jak i { {a}, {b}, {c}, {d}, ∅}. Trywialnym przypadkiem poprawnego matroidu jest taki, w którym rodzina I zawiera jedynie zbiór pusty.

→ 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ść
Polityka prywatnościKontakt