Tutorial: Problem komiwojażera, algorytm genetyczny

Aby korzystać z tej strony musisz mieć włączoną obsługę JavaScript.
Ocena: +10 Tak Nie
Liczba głosów: 12.

Przykład rozwiązania problemu komiwojażera za pomocą algorytmu genetycznego. Ten samouczek jest powiązany tematycznie z artykułem „Algorytmy genetyczne”.

Dodano: 6 maja 2017 17:28.

Zobacz też wszystkie nasze tutoriale!
REKLAMA

Zobacz też

Minimalne drzewo rozpinające (ang. minimum spanning tree, w skrócie MST), inaczej drzewo rozpinające o minimalnej wadze – drzewo łączące wszystkie wierzchołki pewnego grafu spójnego mające najmniejszą możliwą sumę wag krawędzi.

Jeśli graf ma v wierzchołków, to jego drzewo rozpinające zawsze będzie miało v-1 krawędzi. Jeśli ten graf ma e krawędzi, aby utworzyć drzewo rozpinające, trzeba usunąć z grafu e-v+1 krawędzi. Liczba ta jest określana jako liczba cyklomatryczna.

→ Czytaj całość

Dziel i zwyciężaj (ang. divide and conquer) – technika projektowania algorytmów polegająca na podejściu rekurencyjnym. W technice tej problem dzielony jest na mniejsze podproblemy, te podproblemy na jeszcze mniejsze podproblemy, aż dojdzie się do przypadków trywialnych (np. posortowanie jednoelementowej tablicy, obliczenie silni z 1).

Jeśli rozpatrywany problem wymaga podzielenia na podproblemy, jest on określany jako przypadek rekurencyjny. Jeśli mamy do czynienia z przypadkiem trywialnym, jest to przypadek bazowy. Tworząc algorytm wykorzystujący metodę dziel i zwyciężaj musimy ustalić:

  • Jak rozwiązać przypadek bazowy (trywialny).
  • Jak wyznaczyć rozwiązanie problemu, mając dostępne rozwiązania podproblemów.

Przykładem algorytmu opartego na tej metodzie jest sortowanie przez scalanie.

→ Czytaj całość

Powtarzalny algorytm najbliższego sąsiada (ang. repetitive nearest neighbour algorithm, w skrócie RNN) – algorytm służący do rozwiązywania problemu komiwojażera korzystający z algorytmu najbliższego sąsiada.

Algorytm polega na wielokrotnym wykonaniu algorytmu najbliższego sąsiada w taki sposób, aby każdy wierzchołek raz był wierzchołkiem początkowym. Następnie algorytm zwraca najlepsze spośród otrzymanych rozwiązań.

Dla grafu pełnego algorytm ma złożoność O(n3), gdzie n jest liczbą wierzchołków. W trakcie wykonywania algorytmu RNN n razy zostanie wykonany algorytm najbliższego sąsiada, który ma złożoność czasową O(n2).

Algorytm RNN nie daje gwarancji znalezienia rozwiązania optymalnego. W odróżnieniu od algorytmu najbliższego sąsiada daje jednak gwarancję, że zwróci rozwiązanie co najmniej tak dobre, jak n/2-1 innych rozwiązań (dowód i więcej informacji na ten temat znajduje się w pracy podanej w bibliografii).

→ Czytaj całość
Polityka prywatnościKontakt