2-opt
Przykład wykonania algorytmu
2-opt, algorytm 2-optymalny – algorytm lokalnej optymalizacji wykorzystywany przy rozwiązywaniu problemu komiwojażera. Jest to szczególny przypadek algorytmu k-optymalnego.
Algorytm 2-opt nie służy do wyznaczania trasy, a jedynie do ulepszania jej. Samą trasę można wyznaczyć np. za pomocą algorytmu najbliższego sąsiada. Algorytm może być wykorzystany do ulepszenia algorytmu genetycznego – w ten sposób powstanie algorytm memetyczny.
Działanie algorytmu
Algorytm 2-opt polega na usunięciu z cyklu dwóch krawędzi i zastąpieniu ich innymi krawędziami tak, aby utworzyć inny cykl. Czynność jest powtarzana dla każdej pary krawędzi, z wyjątkiem krawędzi sąsiadujących ze sobą – ich modyfikacja nie spowodowałaby żadnych zmian. Za każdym razem modyfikujemy cykl początkowy (nie rozwiązanie z poprzedniego kroku). Po sprawdzeniu wszystkich par krawędzi sprawdzamy, która modyfikacja najbardziej skróciła trasę. Jeśli żadna modyfikacja nie poprawiła trasy, zwracamy cykl początkowy (nie zmieniamy nic).
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
W trakcie jednego przebiegu algorytmu trzeba przeanalizować n*(n-3)/2 par krawędzi. Złożoność czasowa (jednej iteracji) wynosi więc O(n2).
Bibliografia
- D.S. Johnson, L.A. McGeoch, The Traveling Salesman Problem: A Case Study in Local Optimization (link) [dostęp: 3 czerwca 2017].
Liczba głosów: 0.
Dodano: 3 czerwca 2017 15:05, ostatnia edycja: 17 czerwca 2017 16:09.
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.
Graf – struktura składająca się ze zbioru wierzchołków oraz zbioru krawędzi. Grafy mają szerokie zastosowanie w informatyce, można za ich pomocą przedstawić wiele zagadnień.
Wyróżniamy grafy nieskierowane oraz grafy skierowane. W grafie nieskierowanym relacja sąsiedztwa jest symetryczna, tzn. krawędź łączy wierzchołki „w obie strony”. W grafie skierowanym krawędzie są „jednokierunkowe”. Krawędź grafu skierowanego zazwyczaj jest określana jako łuk.
Graf ważony (inaczej graf z wagami) to taki graf, w którym każdej krawędzi przypisana jest pewna wartość liczbowa. Wartość ta może oznaczać np. długość krawędzi lub jej przepustowość.
Algorytm Johnsona – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Algorytm wykorzystuje algorytm Dijkstry i algorytm Bellmana-Forda. Dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli.
Złożoność czasowa algorytmu (jeśli algorytm Dijkstry zostanie zaimplementowany z wykorzystaniem kopca Fibonacciego) to O(n2log n + en), gdzie n jest liczbą wierzchołków, a e jest liczbą krawędzi. Dla grafów rzadkich (ze stosunkowo małą liczbą krawędzi) jest to złożoność lepsza, niż złożoność algorytmu Floyda-Warshalla.