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.

REKLAMA

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 2^k-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!2^k-1/(k(n-k)!) wariantów. Jest to złożoność rzędu O(n^k), 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.