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ł

K-opt

2-opt przykład Przykładowe wykonanie algorytmu 2-optymalnego
3-opt przykład 8 sposobów połączenia ze sobą 3 fragmentów cyklu (jeden krok algorytmu 3-opt)

K-opt, algorytm k-optymalny – algorytm lokalnej optymalizacji wykorzystywany przy rozwiązywaniu problemu komiwojażera. Algorytm ten nie służy do samego wyznaczania trasy, a jedynie do ulepszania jej. Najprostszą wersją tego algorytmu jest algorytm 2-optymalny.

Działanie algorytmu

Algorytm polega na usuwaniu z cyklu k krawędzi i zastępowaniu ich innymi krawędziami tak, aby utworzyć inny prawidłowy cykl. Jeśli osiągnięte w ten sposób rozwiązanie jest lepsze od dotychczas znalezionego, zapamiętujemy je. Za każdym razem modyfikujemy cykl początkowy (nie rozwiązanie z poprzedniego kroku).

Usunięcie z cyklu k krawędzi sprawia, że cykl zostaje podzielony na k fragmentów. Należy sprawdzić wszystkie możliwości połączenia tych fragmentów w całość. Taki krok algorytmu należy powtórzyć dla każdej k-elementowej grupy krawędzi.

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

Załóżmy, że mamy cykl liczący n krawędzi. Jeśli chcemy usunąć z niego k krawędzi, to możemy uczynić to na n!/(k!(n-k)!) sposobów (kombinacja z n po k). Dla każdej kombinacji musimy sprawdzić wszystkie możliwości połączenia fragmentów cyklu w inny sposób. Fragmenty te możemy ustawić w różnej kolejności na (k-1)! sposobów. Dodatkowo każdy fragment można odwrócić, czyli wartość tę musimy pomnożyć przez 2k-1. Jest to oszacowanie z pewnym nadmiarem – jeśli dany fragment jest jednoelementowy, to nie trzeba go odwracać (im większe k, tym więcej będzie takich elementów, zatem dla dużych k czynnik ten będzie zanikał).

Podsumowując, mamy do sprawdzenia maksymalnie n!2k-1/(k(n-k)!) wariantów. Jest to złożoność rzędu O(nk), przy czym nawet dla dużych k złożoność nie przekroczy n!.

Biorąc pod uwagę, że złożoność algorytmu w zależności od k jest wykładnicza, w praktyce używa się tylko niewielkich wartości k, zazwyczaj 2 lub 3. Dla k=n wykonanie algorytmu byłoby tożsame ze sprawdzeniem wszystkich możliwych rozwiązań problemu komiwojażera.

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

Dodano: 17 czerwca 2017 15:20, ostatnia edycja: 17 czerwca 2017 16:08.

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 Edmondsa-Karpa – algorytm wyszukiwania maksymalnego przepływu w sieci przepływowej. Jest to przypadek szczególny algorytmu Forda-Fulkersona.

W algorytmie Edmondsa-Karpa ścieżka powiększająca wyznaczana jest za pomocą przeszukiwania grafu wszerz. Dzięki temu w każdej iteracji algorytmu dołączana jest zawsze najkrótsza (pod względem liczby krawędzi) ścieżka powiększająca. W metodzie Forda-Fulkersona sposób wyznaczania ścieżki powiększającej jest dowolny.

→ Czytaj całość

Bogosort – bardzo słaby algorytm sortowania oparty na metodzie prób i błędów. Polega na ustawianiu elementów w losowej kolejności i sprawdzaniu, czy są posortowane. Średnia złożoność tego algorytmu jest rzędu silnia, a w przypadku pesymistycznym algorytm będzie działał w nieskończoność.

Algorytm występuje też w nieco ulepszonej wersji, w której nie sprawdza się wielokrotnie tego samego ustawienia. Wówczas algorytm daje gwarancję znalezienia rozwiązania, jednak jego złożoność czasowa nadal jest rzędu silnia (w przypadku pesymistycznym trzeba sprawdzić wszystkie permutacje zbioru).

Ze względu na bardzo dużą złożoność czasową bogosort nie nadaje się do praktycznych zastosowań. Istnieją proste w implementacji, a znacznie wydajniejsze algorytmy sortujące, np. sortowanie przez wstawianie.

→ Czytaj całość
Polityka prywatnościKontakt