Od 2010 · Ponad 2 mln uruchomień narzędzi miesięcznie
Od 2010
Dodaj do Chrome

Moje Narzędzia

Tryb Automatyczny

Nie zapisano jeszcze żadnych narzędzi.

Uaktualnij do Wersji Premium
Powiązane narzędzia
Generator SpirografuGenerator Labiryntów
Strona główna > Matematyka > Zaawansowane działania matematyczne
 

Solver Problemu Komiwojażera (TSP)

Znajdź najkrótszą trasę odwiedzającą każde miasto raz i wracającą do startu. Wykorzystuje dokładne programowanie Helda-Karpa dla małych instancji i najbliższego sąsiada z 2-opt dla większych, ze współrzędnych lub macierzy odległości.

BezpłatneBez rejestracjiNatychmiastowe wyniki
Solver Problemu Komiwojażera (TSP)Wypróbuj teraz — za darmo ▼
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)
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 oddzielone przecinkami lub spacjami, jedna na wiersz macierzy. Domyślnie A, B, C... jeśli pominięto.

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=1n-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) = mink ∈ S \ {j} [ C(S \ {j}, k) + d(k, j) ]

Optymalny koszt trasy to wtedy minj [C({1,...,n}, j) + d(j, 1)]. Algorytm Helda–Karpa działa w czasie O(2n · n²) i wymaga pamięci O(2n · 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(2n · n²) O(2n · 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

  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:

Zastosowania w świecie rzeczywistym

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(2n · n²) i pamięci O(2n · 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.

Zaawansowane działania matematyczne:

Popularne i zaktualizowane narzędzia:

Solver Programowania LiniowegoSolver Tablicy Karnaugha (K-Map)Solver Problemu Stabilnych MałżeństwZobacz wszystkie →
Strona główna > Matematyka > Zaawansowane działania matematyczne > Solver Problemu Komiwojażera (TSP)