K-opt

2-opt przykład Przykładowe wykonanie algorytmu 2-optymalnego
3-opt przykład 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.

Dodano: 17 czerwca 2017 15:20
Ostatnia edycja: 17 czerwca 2017 16:08