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.
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.
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).
Dodano: 3 czerwca 2017 15:05, ostatnia edycja: 30 stycznia 2019 15:48.
Programowanie dynamiczne – technika projektowania algorytmów polegająca na rozwiązywaniu podproblemów i zapamiętywaniu ich wyników. W technice tej, podobnie jak w metodzie dziel i zwyciężaj, problem dzielony jest na mniejsze podproblemy. Wyniki rozwiązywania podproblemów są jednak zapisywane w tabeli, dzięki czemu w przypadku natrafienia na ten sam podproblem nie trzeba go ponownie rozwiązywać.
Wykorzystując programowanie dynamiczne można zastosować metodę zstępującą z zapamiętywaniem lub metodę wstępującą.
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.