Math
Komiwojażer
Trasa, która skraca się na twoich oczach - zachłanna, 2-opt rozplątujący krawędź po krawędzi, wyżarzanie przełażące przez mur - wobec dokładnego optimum dla trzynastu miast i brutalnej siły po każdej trasie dla ośmiu.
Co się dzieje
Porównaj budowę najbliższego sąsiada, ulepszenie 2-opt i symulowane wyżarzanie w tych samych miastach. A 2-opt lokalne optymalne nie ma poprawy wymiany dwóch krawędzi; Nie musi to być najkrótsza trasa na świecie. Wyżarzanie czasami akceptuje dłuższe okrążenia, aby uniknąć lokalnych minimum, bez gwarancji optymalnego w skończonym biegu.
Minimalne drzewo rozciągające jest dolną granicą na każdej wycieczce. Dla tych odległości euklidesowych, podwojenie drzewa łączącego i skrócenie powtarzających się wizyt dowodzi, że optymalna trasa jest co najwyżej dwukrotnością minimalnego drzewa łączącego. Ograniczenie to dotyczy optymalnej i odpowiedniej konstrukcji opartej na drzewie; Nie ogranicza każdej chciwej lub pośredniej wycieczki.
Mała dokładna scena używa programowania dynamicznego Helda-Karpa na podzbiorach, z czasem O(N²·2^N) zamiast wyliczania każdej permutacji. Scena ośmiu miast może wymienić każdą odrębną trasę. Algorytmy dokładne nie muszą sprawdzać większości permutacji, ale żaden dokładny algorytm wielomianowy nie jest znany dla ogólnego problemu podróżującego sprzedawcy. Porównaj zmierzone wycieczki heurystyczne z dokładnym odniesieniem, jeśli jest dostępne.
Równania modułu
Równania
miasta: N punktów w [−1, 1]² ze wspólnej kostki (ziarno 3); długość trasy L = Σ |c_k − c_{k+1}| po cyklu; (N − 1)!/2 różnych tras: 2520 dla 8, 2.4·10^8 dla 13, 1.0·10^46 dla 40
zachłanny: z miasta 0, zawsze do najbliższego nieodwiedzonego (remisy rozstrzyga indeks); 12.8105 dla czterdziestu miast
2-opt: krawędzie (a, b) i (c, d), przy czym a leży przed c na trasie; Δ = |ac| + |bd| − |ab| − |cd|; pierwsza para w kolejności przeglądania z Δ < 0 jest rozplatana przez odwrócenie odcinka b … c; powtarzaj, aż nie będzie takiej pary: 16 rozplątań, 10.5850 - ściana (a więc optimum lokalne)
wyżarzanie: losowa para (i, j), i < j, j − i ≥ 2; przyjęta, jeśli Δ ≤ 0, w przeciwnym razie z prawdopodobieństwem exp(−Δ/T); T₀ = 0.3, T ← 0.9997 T w każdym kroku, 20 000 kroków; ziarno 6: najlepsza 10.4954, 462 przyjętych, 231 pogarszających; 2-opt na niej: 10.2673
oszacowanie: MST ≤ L dla każdej trasy (trasa po usunięciu jednej krawędzi jest drzewem rozpinającym), a trasa wzdłuż podwojonego drzewa pokazuje, że L_opt ≤ 2·MST; MST = 8.4480 dla tych czterdziestu (drzewo z GraphTheory, ten sam rzut kostką); 10.2673 / 8.4480 = 1.215
Held–Karp: dp[S, k] = najkrótsza ścieżka z 0 przez zbiór S kończąca się w k; dp[S + k, k] = min po j ze zbioru S z dp[S, j] + |jk|; 2^N·N² kroków; 13 miast, ziarno 8: optimum 7.4710, trasa 0 7 1 3 12 6 8 10 5 4 11 2 9; 2-opt z 50 losowych tras (Fisher–Yates na ziarnach 100 …): 7 osiąga optimum, najgorsza 1.0789 ×, średnio 1.0678 ×
przegląd zupełny: każda permutacja 1 … N − 1 w porządku leksykograficznym, każda trasa raz (pierwsze < ostatnie); 8 miast, ziarno 3: 2520 tras, najlepsza 5.2175 = Held–Karp, najdłuższa 11.9462, średnia 9.1055
