Algorytmy. Ćwiczenia
34,90 zł
PHP 7. Algorytmy i struktury danych
−30%41,30 zł
PHP 7. Algorytmy i struktury danych
−30%41,30 zł
Python. Uczenie maszynowe
69,00 zł
Android Studio. Tworzenie aplikacji mobilnych
69,00 zł
JavaScript i jQuery. Interaktywne strony WWW dla każdego
99,00 zł

2-opt

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

  1. D.S. Johnson, L.A. McGeoch, The Traveling Salesman Problem: A Case Study in Local Optimization (link) [dostęp: 3 czerwca 2017].
Ocena: 0 Tak Nie
Liczba głosów: 0.

Dodano: 3 czerwca 2017 15:05, ostatnia edycja: 17 czerwca 2017 16:09.

Zobacz też

Algorytm – przepis, zbiór poleceń, opis ciągu operacji prowadzących do rozwiązania konkretnego problemu. Algorytm możemy również rozumieć jako funkcję przekształcającą dane wejściowe w dane wyjściowe.

Algorytm musi być skończony, czyli jego zapis ma składać się ze skończonej liczby znaków. Musi również być poprawny, czyli dla wszystkich możliwych danych wejściowych powinien zwracać prawidłowy wynik (może być nim informacja o braku rozwiązania). Algorytm musi wykazywać również własność stopu – niezależnie od danych wejściowych obliczenia algorytmu powinny dochodzić do punktu końcowego, czyli po prostu kończyć się (nie mogą np. wpadać w nieskończoną iterację). Zapis algorytmu musi być precyzyjny, bez jakichkolwiek niejasności.

→ Czytaj całość

Algorytm Floyda-Warshalla – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Jest to algorytm oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n3) i złożoność pamięciową O(n2), gdzie n jest liczbą wierzchołków.

Algorytm dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli. Algorytm może być również wykorzystywany do wyszukiwania ujemnych cykli w grafie.

→ Czytaj całość

Algorytm Dijkstry – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. Algorytm wymaga, aby wagi krawędzi grafu nie były ujemne. Autorem algorytmu jest holenderski naukowiec Edsger Dijkstra.

Algorytm realizuje podejście zachłanne. W każdej iteracji wybierany jest ten spośród nieodwiedzonych wierzchołków, do którego można dotrzeć najmniejszym kosztem. Po wyznaczeniu ścieżki do konkretnego wierzchołka nie zostanie ona zmodyfikowana w trakcie wykonywania dalszej części algorytmu.

→ Czytaj całość
Polityka prywatnościKontakt