2-opt

2-opt przykład (1) 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

Ocena: 0 Tak Nie
Liczba głosów: 0.

Dodano: 3 czerwca 2017 15:05, ostatnia edycja: 30 stycznia 2019 15:48.

REKLAMA

Zobacz też

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ść.

→ Czytaj całość

Algorytm heurystyczny, heurystyka – algorytm niedający (w ogólnym przypadku) gwarancji znalezienia rozwiązania optymalnego, umożliwiający jednak znalezienie rozwiązania dość dobrego w rozsądnym czasie. Algorytmy tego typu używane są w takich problemach obliczeniowych, gdzie znalezienie rozwiązania optymalnego ma zbyt dużą złożoność obliczeniową (w szczególności są to problemy NP-trudne) lub w ogóle nie jest możliwe.

Pojęcie algorytmów heurystycznych jest bardzo szerokie, dotyczy ono różnych technik projektowania algorytmów. Wiele heurystyk wykorzystuje losowość, inne zaś są deterministyczne (wówczas dla takich samych danych wejściowych algorytm zawsze zwróci ten sam wynik).

Ogólny algorytm heurystyczny (opisujący samą ideę poszukiwań) bywa określany w literaturze jako metaheurystyka. Zgodnie z tym nazewnictwem, metaheurystyką jest np. algorytm zachłanny (jako ogólna idea), zaś heurystyką jest np. algorytm najbliższego sąsiada (jako zastosowanie idei algorytmu zachłannego do konkretnego problemu).

→ Czytaj całość

Sortowanie przez scalanie – rekurencyjny algorytm sortowania wykorzystujący metodę dziel i zwyciężaj.

→ Czytaj całość
Polityka prywatnościKontakt