Jak rozwiązać problem komiwojażera?
Dwa proste i efektywne algorytmy w C++.
Problem komiwojażera (ang. Traveling Salesman Problem) jest jednym z najbardziej popularnych zagadnień z zakresu optymalizacji. Istnieje wręcz niezliczona liczba opracowań na ten temat. Taki sukces zawdzięcza zapewne temu, że problem wydaje się dość prosty, a mimo to wcale nie jest łatwy do rozwiązania.
Na czym polega ten problem? Powiedzmy, że chcemy odwiedzić wszystkie europejskie stolice. Każde miasto możemy odwiedzić tylko raz. Podróż musimy zakończyć w mieście, z którego wyruszyliśmy. W jakiej kolejności powinniśmy odwiedzić poszczególne stolice, aby pokonać jak najkrótszy dystans?
Znalezienie najbardziej optymalnego planu podróży będzie wymagało, w najgorszym przypadku, sprawdzenia $n!$ różnych tras. To bardzo zła informacja. Nawet niewielki wzrost ilości miast może gigantycznie wydłużyć czas obliczeń, do tego stopnia, że na wynik będziemy musieli czekać całe wieki! Poza tym, większość z analizowanych tras będzie zupełnie pozbawiona sensu i daleko będzie im do optymalności. Po co więc marnować czas i energię na ich obliczanie?
Heurystyka konstrukcyjna
Istnieje wiele sprytnych algorytmów, które można zastosować do rozwiązania problemu komiwojażera. Jednym z nich jest prosta heurystyka, która buduje trasę poprzez dołączanie do aktualnego planu podróży najbliższego nieodwiedzonego miasta. Określana jest mianem algorytmu najbliższego sąsiada (ang. Nearest Neighbour algorithm). Na poniższym rysunku możesz zobaczyć jak przebiega konstruowanie trasy za pomocą tego algorytmu.
Planowanie trasy zaczynamy z miasta początkowego oznaczonego literą $a$. Wyznaczamy dystans pomiędzy nim a każdym z dotychczas nieodwiedzonych miast, co na rysunku reprezentowane jest za pomocą przerywanych szarych linii. Do trasy dołączamy to miasto, do którego odległość jest najmniejsza. W naszym przypadku będzie to miasto $b$. Miasto startowe oznaczamy jako odwiedzone i wykonujemy te same czynności dla punktu $b$. Postępujemy tak do czasu, aż odwiedzimy wszystkie miasta. Spróbujmy zaimplementować ten algorytm.
using Tour = std::vector<int>;
/**
* Układa trasę za pomocą algorytmu najbliższego sąsiada.
*
* @param start Numer miasta startowego.
* @param cities Ilość wszystkich miast.
* @return Zbudowana trasa.
*/
auto nn(int start, unsigned long cities) {
Tour tour(cities);
// inicjalizujemy trasę
std::iota(tour.begin(), tour.end(), 0);
// ustawiamy miasto startowe na początku trasy
std::swap(tour[0], tour[start]);
// budujemy trasę
for (int i = 1; i < cities - 1; i++) {
int nearest = i;
// szukamy najbliższego nieodwiedzonego sąsiada
for (int j = nearest + 1; j < cities; j++) {
if (distance(tour[i], tour[j]) < distance(tour[i], tour[nearest])) {
nearest = j;
}
}
// przestawiamy znalezione miasto
// na następną pozycję w trasie
std::swap(tour[i + 1], tour[nearest]);
}
return tour;
}
Na poniższym rysunku znajduje się przykładowa trasa zbudowana tym algorytmem. Miasto początkowe zostało zaznaczone czerwonym kwadratem.
Z rysunku widać, że trasa, którą uzyskaliśmy nie jest zbyt optymalna. Pytanie: dlaczego? Odpowiedzialność można przypisać strategii wyboru zachłannego, na której opiera się algorytm najbliższego sąsiada. Cechą charakterystyczną algorytmów zachłannych jest to, że w danej chwili zawsze dokonują wyboru, który wydaje się najkorzystniejszy. Nie biorą pod uwagę wpływu bieżących decyzji na dalsze wybory podejmowane w kolejnych krokach algorytmu.
Zgodnie ze strategią zachłanną, algorytm najbliższego sąsiedztwa w każdym następnym kroku wybierał nieodwiedzone dotychczas miasto, położone najbliżej miejsca w którym aktualnie znajdował się podróżnik. W ten sposób odwlekał wybór miast położonych najdalej. Gdy wszystkie miasta będące blisko siebie zostały już włączone do trasy, algorytm nie miał już zbyt wielu możliwości optymalnego dołączenia pozostałych, najbardziej oddalonych miast. W rezultacie algorytm nadal podejmował lokalnie optymalne decyzje – wybierał spośród pozostałych miast to które było najbliższej, jednak z punktu widzenia rozwiązania jako całości, niektóre decyzje, szczególnie te podejmowane pod koniec, okazały się zupełnie nietrafione.
Uzyskana trasa nie należy jednak do najgorszych. Spróbujmy zbudować kilka tras, za każdym razem zaczynając z innego miasta. Może uda nam się znaleźć lepszą. W końcu niezależnie od tego skąd zaczniemy, optymalna trasa będzie zawsze tylko jedna. Poniższy rysunek przedstawia rozwiązanie znalezione tym sposobem.
Mimo iż udało się uzyskać trochę lepszą trasę, nadal gołym okiem widać, że mogłaby być jeszcze krótsza. Strategia zachłanna nadal daje o sobie znać. Na tej podstawie można wyciągnąć bardzo istotny wniosek: kolejność odwiedzanych miast nie zawsze jest oczywista. Czasem z lokalnego punktu widzenia trzeba podjąć nieoptymalną decyzję, aby rozwiązanie jako całość było optymalne. Inaczej: czasem trzeba wybrać dalsze miasta, aby potem trasa jako całość była krótsza. W związku z tym strategia zachłanna najprawdopodobniej nie będzie wystarczająca do rozwiązania problemu komiwojażera.
Poza tym budowanie każdej nowej trasy od zera wydaje się trochę niepraktyczne. W końcu uzyskane rozwiązania nie są do końca złe i można by je ulepszyć poprzez zmianę kolejności odwiedzania niektórych miast. Tylko skąd wiedzieć które miasta poprzestawiać i w jaki sposób?
Heurystyka polepszająca
Zanim zaczniemy budować kolejną trasę zaczynając od innego miasta, możemy jeszcze spróbować poprawić uzyskane rozwiązanie. W tym celu możemy skorzystać z heurystyk ulepszających, które na bazie rozwiązania zbudowanego w oparciu o jedną z heurystyk konstrukcyjnych, będą starały się za pomocą małych zmian znaleźć lepsze rozwiązanie. Wśród nich jest prosta i efektywna heurystyka o nazwie 2-opt.
Działanie heurystki 2-opt opiera się na bardzo prostej obserwacji: w dobrych trasach drogi się nie przecinają. W związku z tym, zadaniem tego algorytmu jest wykrycie fragmentów trasy, w których dwie drogi się krzyżują, a następnie przekształcenie ich w taki sposób, aby pozbyć się krzyżowania. Pokazuje to poniższy rysunek.
Jak stwierdzić które drogi się przecinają? Na szczęście, aby to ustalić, nie trzeba badać zależności geometrycznych między odcinkami. Dla każdej pary dróg w trasie, wystarczy sprawdzić czy isnieje alternatywna, krótsza droga pomiędzy tymi samymi miastami. Przeanalizujmy to na przykładzie.
Na powyższym rysunku przecina się tylko jedna para dróg: $bd$ oraz $ce$. Jedynymi alternatywnymi drogami mającymi swój początek i koniec w tych wierzchołkach, które pozwolą zachować ciągłość trasy, są drogi: $bc$ oraz $de$. Jeśli porównamy teraz sumaryczną długość każdej z tych par dróg, w rezultacie czego spełniona będzie poniższa nierówność, to możemy być pewni, że ten fragment trasy można skrócić.
\[ |bd| + |ce| > |bc| + |de| \]
W ten sposób, zanim dokonamy w rozwiązaniu jakiejś zmiany, możemy wcześniej określić jaki będzie z niej zysk, np. o ile się skróci cała trasa. Dzięki temu możemy przyśpieszyć algorytm, szczególnie gdy jest kosztowny pod względem obliczeniowym.
Gdy nierówność będzie spełniona, wystarczy już tylko odwrócić kolejność odwiedzania miast pomiędzy wierzchołkami $b$ i $e$, uzyskując w ten sposób krótszy wariant tego fragmentu rozwiązania. Teraz możemy zaimplementować heurystykę 2-opt.
using Move = std::pair<int, int>;
/**
* Określa jaki fragment trasy należy odwrócić,
* aby jak najbardziej zmniejszyć jej dystans.
*
* @param tour Trasa.
* @return Indeksy pomiędzy którymi należy obrócić trasę.
*/
auto find_best_move(const Tour &tour) {
Move move(-1, -1);
double max_gain = 0;
for (int i = 1; i < tour.size() - 1; i++) {
// wyznaczamy miasta połączone przez pierwszą krawędź
int a = tour[i - 1], b = tour[i];
for (int j = i + 1; j < tour.size(); j++) {
// wyznaczamy miasta połączone przez drugą krawędź
int c = tour[j - 1], d = tour[j];
// określamy o ile zmniejszy się trasa,
// jeśli zastosujemy alternatywne połączenie miast
double current = distance(a, b) + distance(c, d);
double alternative = distance(a, c) + distance(b, d);
double gain = current - alternative;
// gdy znajdziemy lepszy ruch
if (gain > max_gain) {
// zapamiętujemy indeksy pomiędzy
// którymi należy obrócić trasę
max_gain = gain;
move.first = i;
move.second = j;
}
}
}
return move;
}
/**
* Optymalizuje trasę za pomocą algorytmu 2-opt.
*
* @param tour Trasa.
*/
void two_opt(Tour &tour) {
bool improved;
do {
improved = false;
// spróbuj znaleźć ruch, który najbardziej skróci trasę
auto move = find_best_move(tour);
// jeśli taki ruch istnieje
if (move.first >= 0) {
// odwróć trasę pomiędzy wskazanymi punktami
std::reverse(
tour.begin() + move.first,
tour.begin() + move.second
);
improved = true;
}
// przenosimy dwa miasta z początku na koniec trasy,
// zachowując przy tym kolejność ich odwiedzania,
// aby funkcja find_best_move, w kolejnym obiegu pętli,
// mógła uwzględnić podczas analizy krawędź powrotną
std::rotate(tour.begin(), tour.begin() + 2, tour.end());
} while (improved);
}
Zauważ, że heurystyka 2-opt bezpośrednio modyfikuje, przekazany w parametrze tour, plan podróży. Dzięki temu unikamy kosztownego, pod względem obliczeniowym, kopiowania trasy podczas optymalizacji, tym bardziej, że jeśli trasy nie da się poprawić, to i tak zostanie ona bez zmian.
Pojawia się jeszcze pewne pytanie: czy wystarczy zastosować heurystykę 2-opt tylko do najlepszej trasy zbudowanej za pomocą algorytmu najbliższego sąsiada, aby otrzymać doskonały rezultat? Niestety, nigdy do końca nie wiadomo która z ułożonych tras okaże się tą najlepszą. Z tego powodu, rozsądnym będzie użycie heurystyki ulepszającej do każdej z nich. Zwiększymy w ten sposób szansę uzyskania najlepszego wyniku. Poniższy rysunek przedstawia efekt pracy obu algorytmów.
Widać, że trasa prezentuje się o wiele bardziej sensownie. Nie posiada już żadnych zauważalnych defektów. Pytanie: czy jest to najlepsza z możliwych tras? Niestety, nie wiadomo. Musielibyśmy skorzystać z algorytmów dokładnych, które zawsze gwarantują znalezienie optimum, jeśli takie istnieje, kosztem dłuższego czasu obliczeń. Mimo to, trasy uzyskane za pomocą heurystyki 2-opt mogą być zaledwie do kilku procent gorsze od optimum, a w końcu o to nam chodziło: aby uzyskać dobrą trasę w krótkim czasie.
Kompletny kod źródłowy wraz z komentarzami znajdziesz w repozytorium TSP. Ponadto umieściłem tam również przykładowe zbiory miast do testowania algorytmów oraz skrypty pozwalające generować losowe miasta i wizualizować uzyskane trasy.