Solver Problemu Komiwojażera (TSP)

O Solver Problemu Komiwojażera (TSP)

Solver Problemu Komiwojażera TSP to praktyczny kalkulator edukacyjny dla klasycznego problemu komiwojażera (TSP): mając zestaw miast i odległości między nimi, należy znaleźć najkrótszą możliwą trasę, która odwiedza każde miasto dokładnie raz i powraca do punktu wyjścia. Ten solver akceptuje współrzędne płaskie lub niestandardową macierz odległości, automatycznie wybiera najlepszy algorytm na podstawie wielkości problemu i renderuje wynikową trasę jako animowaną mapę SVG.

Co to jest problem komiwojażera?

Formalnie, mając pełny graf ważony G = (V, E) ze zbiorem wierzchołków V = {1, 2, ..., n} i wagami krawędzi d(i, j), TSP poszukuje takiej permutacji π wierzchołków, która minimalizuje wyrażenie:

Ostatni człon zamyka pętlę. TSP jest jednym z najstarszych i najbardziej badanych problemów w optymalizacji kombinatorycznej — jest on NP-trudny w ogólnym przypadku, co oznacza, że żaden znany algorytm nie rozwiązuje każdej instancji w czasie wielomianowym. Mimo to pojawia się on w niezliczonych zastosowaniach rzeczywistych: planowaniu tras pojazdów, wierceniu płytek drukowanych PCB, sekwencjonowaniu DNA, trasach kompletacji w magazynach, harmonogramach obserwacji astronomicznych, a nawet w doręczaniu poczty wiejskiej.

Jak działa ten solver?

Programowanie dynamiczne Helda–Karpa (Dokładne)

Dla małych instancji (do 12 miast) solver oblicza trasę o udowodnionej optymalności przy użyciu algorytmu Helda–Karpa, opublikowanego niezależnie przez Richarda Bellmana oraz Michaela Helda i Richarda Karpa w 1962 roku. Kluczowa rekurencja, gdzie C(S, j) jest najkrótszą ścieżką od wierzchołka 1 do wierzchołka j odwiedzającą dokładnie podzbiór S:

Optymalny koszt trasy to wtedy min_j [C({1,...,n}, j) + d(j, 1)]. Algorytm Helda–Karpa działa w czasie O(2ⁿ · n²) i wymaga pamięci O(2ⁿ · n) — co stanowi ogromną poprawę w stosunku do metody brute force n!, ale nadal jest to wzrost wykładniczy. Powyżej około 20 miast zapotrzebowanie na pamięć staje się niepraktyczne.

Najbliższy sąsiad + 2-opt (Heurystyka)

Dla większych instancji solver używa dwuetapowej heurystyki. Najpierw algorytm najbliższego sąsiada konstruuje szybką trasę, chciwie przechodząc do najbliższego nieodwiedzonego miasta z każdego wierzchołka startowego. Solver wypróbowuje wiele wierzchołków startowych i zachowuje najlepszą trasę. Następnie przeszukiwanie lokalne 2-opt ulepsza trasę poprzez iteracyjne usuwanie dwóch krawędzi i ponowne łączenie dwóch wynikowych ścieżek w jedyny inny możliwy sposób:

Geometrycznie 2-opt usuwa każde „skrzyżowanie” w trasie: każde dwa przecinające się odcinki można zawsze rozprostować, aby uzyskać krótszą długość całkowitą. Algorytm zatrzymuje się w lokalnym optimum, w którym żadna pojedyncza zamiana już nie pomaga, co nazywa się trasą 2-optymalną. W rzeczywistych instancjach euklidesowych 2-opt zazwyczaj znajduje trasy w granicach 2–5% od prawdziwego optimum w ułamku sekundy.

Formaty wejściowe

Tryb współrzędnych (x, y)

Jedno miasto w linii. Każda linia to etykieta, x, y — etykieta jest opcjonalna. Solver automatycznie oblicza odległości euklidesowe i wizualizuje miasta w ich rzeczywistych pozycjach.

Tryb macierzy odległości

Kwadratowa macierz odległości nieujemnych o wymiarach n × n, jeden wiersz na linię, wartości oddzielone spacjami lub przecinkami. Macierze mogą być symetryczne lub asymetryczne — macierze asymetryczne modelują ulice jednokierunkowe, ceny lotów o różnej dostępności oraz podróże zależne od wiatru. Opcjonalnie można podać etykiety w polu Etykiety macierzy.

Porównanie algorytmów

Jak korzystać z tego solvera

1. Wybierz tryb wprowadzania. Współrzędne, jeśli miasta mają znaczące pozycje (x, y); Macierz odległości, jeśli koszty są nieeuklidesowe lub asymetryczne.
2. Wklej lub wpisz swoje dane. Jedno miasto lub wiersz na linię. Kliknij przycisk szybkiego przykładu nad formularzem, aby wstępnie wypełnić poprawny przykład.
3. Wybierz algorytm. Pozostaw na Auto dla odpowiedniego domyślnego wyboru: Held–Karp, gdy instancja jest wystarczająco mała dla udowodnionej optymalności, w przeciwnym razie NN + 2-opt. Wymuś konkretny algorytm, jeśli chcesz je porównać.
4. Wybierz trasę zamkniętą lub otwartą. Trasa zamknięta powraca do punktu wyjścia — to tradycyjny TSP. Tryb ścieżki otwartej rozwiązuje powiązany problem ścieżki Hamiltona, w którym sprzedawca kończy w innym mieście.
5. Kliknij Rozwiąż. Strona wyników pokazuje całkowitą długość trasy, animowany obraz SVG trasy (kliknij „Powtórz animację”, aby ją odtworzyć), pełną sekwencję miast, podział na poszczególne krawędzie oraz macierz odległości z podświetlonymi krawędziami trasy.

Przykład krok po kroku

Rozważmy pięć miast — prostokąt plus szczyt: A (0, 0), B (4, 0), C (4, 3), D (0, 3), E (2, 5). Solver zwraca:

• Trasa: A → D → E → C → B → A
• Długość: 3 + √8 + √8 + 3 + 4 ≈ 15.66
• Optymalna? Tak — algorytm Helda–Karpa udowadnia, że nie istnieje krótsza trasa.
• Dlaczego taka kolejność? Trasa przebiega wzdłuż otoczki wypukłej pięciu punktów (A → D → E → C → B → A). Klasyczną właściwością euklidesowego TSP jest to, że optymalna trasa odwiedza punkty na otoczce wypukłej w ich cyklicznej kolejności; punkty wewnętrzne wpasowują się między sąsiadów na otoczce. Każda trasa, która przecina własną ścieżkę, jak A → C → B → D → E → A (długość ≈ 21.8), może zostać zawsze rozprostowana przez 2-opt, dając krótszy wynik.

Zastosowania w świecie rzeczywistym

• Logistyka i dostawy — optymalizacja dziennej trasy kierowcy z 15 przystankami w celu zminimalizowania zużycia paliwa i czasu.
• Produkcja — ustalanie kolejności otworów, które wiertarka CNC musi wykonać na PCB, aby zminimalizować ruch głowicy.
• Asemblacja genomu — porządkowanie fragmentów DNA według podobieństwa nakładania się, zakodowanego jako macierz odległości.
• Astronomia — planowanie obrotów teleskopu między gwiazdami docelowymi w celu maksymalizacji czasu obserwacji.
• Kompletacja w magazynie — sekwencjonowanie wizyt w alejkach w celu zrealizowania zamówienia w jak najmniejszej liczbie kroków.
• Planowanie turystyki — planowanie podróży do wielu miast, która minimalizuje czas podróży i koszty biletów.

Często zadawane pytania

Co to jest problem komiwojażera?

Problem komiwojażera (TSP) polega na znalezieniu najkrótszej możliwej trasy, która odwiedza każde miasto dokładnie raz i powraca do miasta startowego. Jest to jeden z najsłynniejszych problemów optymalizacji kombinatorycznej i jest NP-trudny w ogólnym przypadku, co oznacza, że żaden znany algorytm nie rozwiązuje każdej instancji w czasie wielomianowym.

Co to jest algorytm Helda–Karp?

Held–Karp to algorytm programowania dynamicznego, który rozwiązuje TSP dokładnie w czasie O(2ⁿ · n²) i pamięci O(2ⁿ · n). Jest on znacznie szybszy niż metoda brute force (n silnia), ale nadal wykładniczy, więc w praktyce jest używany tylko dla instancji do około 20 miast. Ten solver używa algorytmu Helda–Karpa, gdy miast jest 12 lub mniej.

Co to jest 2-opt i dlaczego jest używany?

2-opt to heurystyka wyszukiwania lokalnego, która wielokrotnie usuwa dwie krawędzie z bieżącej trasy i łączy dwie wynikowe ścieżki w inny możliwy sposób. Gdy nowa trasa jest krótsza, zamiana zostaje zachowana. 2-opt działa w czasie wielomianowym na iterację i konsekwentnie znajduje trasy w granicach kilku procent od optymalnej, dlatego jest klasyczną heurystyką pierwszego wyboru dla większych instancji TSP.

Kiedy powinienem użyć współrzędnych, a kiedy macierzy odległości?

Użyj współrzędnych, gdy Twoje miasta znajdują się na płaszczyźnie z odległościami w linii prostej — na przykład punkty na mapie, lokalizacje magazynów lub otwory wiertnicze na płytce drukowanej. Użyj macierzy odległości, gdy koszt pary nie jest euklidesowy — na przykład ceny lotów, czasy podróży z ruchem drogowym, odległości drogowe w jedną stronę lub koszty asymetryczne. Tryb macierzy akceptuje wszelkie nieujemne odległości, nawet asymetryczne.

Czy rozwiązanie 2-opt jest optymalne?

Nie, 2-opt zwraca trasę 2-optymalną, co oznacza, że żadna pojedyncza para krawędzi nie może zostać zamieniona w celu uzyskania krótszej trasy. Jest to lokalne optimum i zazwyczaj mieści się w granicach kilku procent od globalnego optimum w dobrze uwarunkowanych instancjach, ale nie gwarantuje, że jest to najlepsze rozwiązanie globalne. Aby uzyskać trasę o udowodnionej optymalności dla małych instancji, wybierz Held–Karp.

Czy to narzędzie obsługuje asymetryczne macierze odległości?

Tak. W trybie macierzy odległości można wprowadzić dowolną nieujemną macierz kwadratową, w tym asymetryczną, gdzie D[i][j] różni się od D[j][i]. Zarówno Held–Karp, jak i 2-opt poprawnie obsługują macierze asymetryczne. Jest to przydatne w rzeczywistych problemach z trasowaniem z ulicami jednokierunkowymi, ruchem drogowym lub kosztami lotów zależnymi od wiatru.

Dalsza lektura

• Problem komiwojażera — Wikipedia
• Algorytm Helda–Karpa — Wikipedia
• 2-opt — Wikipedia
• Algorytm najbliższego sąsiada — Wikipedia

Zaawansowane działania matematyczne:

• Kalkulator Antylogarytmów
• Kalkulator funkcji beta
• Kalkulator współczynnika dwumianu
• Kalkulator rozkładu dwumianowego
• Kalkulator Bitowy Polecane
• Kalkulator Twierdzenia Centralnego Granicznego
• Kalkulator kombinacji
• Komplementarny kalkulator funkcji błędu
• Kalkulator liczb zespolonych
• Kalkulator Entropii
• Kalkulator funkcji błędu
• Kalkulator rozkładu wykładniczego
• Kalkulator wzrostu wykładniczego - wysoka precyzja
• Kalkulator całki wykładniczej
• kalkulator-wykładników-wysoka-precyzja
• Kalkulator silni
• Kalkulator Funkcji Gamma
• Kalkulator złotego podziału
• Kalkulator półtrwania
• Kalkulator tempa wzrostu procentowego
• Kalkulator permutacji
• Kalkulator Rozkładu Poissona Polecane
• Kalkulator korzeni wielomianów ze szczegółowymi krokami
• Kalkulator prawdopodobieństwa
• Kalkulator rozkładu prawdopodobieństwa
• Kalkulator Proporcji
• Kalkulator Formuły Kwadratowej
• Kalkulator Naukowy
• Kalkulator notacji naukowej Polecane
• Kalkulator Cyfr Znaczących Nowy
• Kalkulator sumy sześcianów
• Kalkulator sumy kolejnych liczb
• Kalkulator sumy kwadratów
• Generator tablicy prawdy
• Kalkulator teorii zbiorów
• Generator Diagramu Venna (3 zbiory)
• Kalkulator chińskiego twierdzenia o resztach
• Kalkulator Funkcji Tocjenta Eulera
• Kalkulator rozszerzonego algorytmu Euklidesa
• Kalkulator modularnej odwrotności multiplikatywnej
• Kalkulator ułamków łańcuchowych
• Kalkulator Najkrótszej Ścieżki Dijkstry
• Kalkulator Minimalnego Drzewa Rozpinającego
• Walidator ciągu stopni grafu
• Kalkulator Nieporządków (Podfaktoriał)
• Kalkulator liczb Stirlinga
• Kalkulator Zasady Szufladkowej
• Kalkulator rozkładu stacjonarnego łańcucha Markowa
• Kalkulator Zaokrąglania Nowy
• Kalkulator Rozkładu Ujemnego Dwumianowego Nowy
• Kalkulator Permutacji z Powtórzeniami Nowy
• Kalkulator Potęgowania Modularnego Nowy
• Kalkulator Pierwiastka Pierwotnego
• Upraszczacz Algebry Boole’a Nowy
• Solver Tablicy Karnaugha (K-Map) Nowy
• Kalkulator Kolorowania Grafów Nowy
• Kalkulator Sortowania Topologicznego Nowy
• Kalkulator Macierzy Sąsiedztwa Nowy
• Kalkulator Włączeń i Wyłączeń Nowy
• Solver Programowania Liniowego Nowy
• Solver Problemu Komiwojażera (TSP) Nowy
• Sprawdzanie Ścieżki Hamiltona Nowy
• Walidator Grafu Planarnego Nowy
• Kalkulator Przepływu w Sieci (Maksymalny Przepływ) Nowy
• Solver Problemu Stabilnych Małżeństw Nowy
• Kalkulator Rzędu w Teorii Grup Nowy
• Kalkulator Pierścieni i Ciał Nowy