2-opt
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, 1995 [Dostęp 2019-01-26].
Liczba głosów: 0.
Dodano: 3 czerwca 2017 15:05, ostatnia edycja: 30 stycznia 2019 15:48.
Zobacz też
Przeszukiwanie w głąb (ang. depth-first search, w skrócie DFS) – jeden z dwóch podstawowych algorytmów przeszukiwania grafu. Polega na przechodzeniu zawsze do kolejnego nieodwiedzonego wierzchołka. Jeśli dany wierzchołek nie ma nieodwiedzonych sąsiadów, wracamy do poprzedniego wierzchołka i sprawdzamy jego sąsiadów. Mówiąc obrazowo, w algorytmie tym wchodzimy tak głęboko, jak to możliwe (przechodzimy dalej, dopóki się da).
Algorytm można zapisać w sposób rekurencyjny. Wywoływana rekurencyjnie procedura działa następująco: oznacz wierzchołek jako odwiedzony, a następnie wywołaj tę procedurę dla każdego sąsiada danego wierzchołka, jeśli nie został on wcześniej odwiedzony. Na początku wywołujemy procedurę dla wierzchołka początkowego.
Stos (ang. Stack) – struktura danych, w której bezpośredni dostęp jest tylko do ostatnio dodanego elementu. Stos bywa określany także jako kolejka LIFO (z ang. Last In, First Out, czyli: ostatni na wejściu, pierwszy na wyjściu). Stos można sobie wyobrazić jako kilka rzeczy ułożonych „jedna na drugiej” – łatwo można wziąć tylko rzecz leżącą na samym wierzchu, gdyż pozostałe są przykryte.