Solver Problemu Komiwojażera (TSP)

Znajdź najkrótszą trasę, która odwiedza każde miasto dokładnie raz i wraca do punktu startowego. Dokładne programowanie dynamiczne (Held-Karp) dla małych instancji oraz heurystyka najbliższego sąsiada + 2-opt dla większych. Akceptuje współrzędne lub macierz odległości i generuje animowaną trasę SVG.

Szybkie przykłady:

5-miast kwadrat+szczyt 8 losowych miast 8 stolic UE Macierz 4×4 Benchmark 10 miast Trójkąt (ścieżka otwarta)

⌖ Współrzędne (x, y) ▦ Macierz odległości

Miasta lub macierz

Linie współrzędnych: A, 10, 20 lub 10 20. Wiersze macierzy: 0 10 15 20 — jeden wiersz na linię, macierz kwadratowa, nieujemna. Maksymalnie 40 miast.

Etykiety macierzy (opcjonalnie)

Etykiety oddzielone przecinkami lub spacjami, jedna na wiersz macierzy. Domyślnie A, B, C... jeśli pominięto.

Algorytm

Typ trasy

Embed Solver Problemu Komiwojażera (TSP) Widget

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:

minimalizuj Σ_i=1^n-1 d(π(i), π(i+1)) + d(π(n), π(1))

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:

C(S, j) = min_{k ∈ S \ {j}} [ C(S \ {j}, k) + d(k, j) ]

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:

Przed: ... a — b ... c — d ... Po zamianie 2-opt: ... a — c ... b — d ... Jeśli d(a,c) + d(b,d) < d(a,b) + d(c,d) → zaakceptuj zamianę, odwróć podtrasę b..c

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.

A, 10, 20 B, 40, 70 C, 75, 30 Paris: 2.35, 48.86 10 20 ← automatyczna etykieta C1

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.

0 10 15 20 10 0 35 25 15 35 0 30 20 25 30 0

Porównanie algorytmów

Algorytm	Złożoność czasowa	Pamięć	Jakość wyniku	Praktyczny rozmiar
Brute force	O(n!)	O(n)	Optymalny	n ≤ 10
Held–Karp DP	O(2ⁿ · n²)	O(2ⁿ · n)	Optymalny	n ≤ 20
Najbliższy sąsiad	O(n²)	O(n)	~25% gorszy od optymalnego	n ≤ tysiące
NN + 2-opt	O(n² · przebiegi)	O(n)	~2–5% gorszy od optymalnego	n ≤ setki

Jak korzystać z tego solvera

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.
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.
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ć.
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.
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

Cytuj ten materiał, stronę lub narzędzie w następujący sposób:

"Solver Problemu Komiwojażera (TSP)" na https://MiniWebtool.com/pl/solver-problemu-komiwojazera-tsp/ z MiniWebtool, https://MiniWebtool.com/

przez zespół miniwebtool. Aktualizacja: 21 kwietnia 2026

Możesz także wypróbować nasz AI Rozwiązywacz Matematyczny GPT, aby rozwiązywać swoje problemy matematyczne poprzez pytania i odpowiedzi w języku naturalnym.

Inne powiązane narzędzia:

Kalkulator Macierzy SąsiedztwaNowy

Kalkulator Najkrótszej Ścieżki DijkstryNowy

Kalkulator Kolorowania GrafówNowy

Walidator ciągu stopni grafuNowy

Sprawdzanie Ścieżki HamiltonaNowy

Solver Programowania LiniowegoNowy

Kalkulator Sortowania TopologicznegoNowy

Solver Problemu Komiwojażera (TSP)

O Solver Problemu Komiwojażera (TSP)

Co to jest problem komiwojażera?

Jak działa ten solver?

Programowanie dynamiczne Helda–Karpa (Dokładne)

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

Formaty wejściowe

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

Tryb macierzy odległości

Porównanie algorytmów

Jak korzystać z tego solvera

Przykład krok po kroku

Zastosowania w świecie rzeczywistym

Często zadawane pytania

Co to jest problem komiwojażera?

Co to jest algorytm Helda–Karp?

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

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

Czy rozwiązanie 2-opt jest optymalne?

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

Dalsza lektura

Inne powiązane narzędzia:

Zaawansowane działania matematyczne:

Polecane narzędzia: