Szczególne przypadki komiwojażera

Jest wiele sposobów obejścia wszystkich punktów A₁, A₂, ... A₇.
Interesować nas będą drogi, czyli takie wędrówki, w których chodzimy od wierzchołka do wierzchołka i każdy z nich odwiedzamy dokładnie raz, np. A₁A₃A₂A₅A₇A₄A₆.
Rozważać będziemy też cykle, czyli drogi obchodzące wszystkie wierzchołki i zakończone powrotem do punktu wyjścia, np. A₁A₄A₂A₆A₃A₇A₅A₁.

Nietrudno zgadnąć, że startując z A₁, mamy dwie najkrótsze drogi: A₁A₂A₃A₄A₅A₆A₇ oraz A₁A₇A₆A₅A₄A₃A₂. Są rzeczywiście najkrótsze, bo wędrujemy po najkrótszych odcinkach łączących wierzchołki siedmiokąta foremnego.

Tak samo jest z najkrótszymi cyklami (patrz obok).

Pokazana na rysunku jest faktycznie najdłuższa, bo wędrówka odbywa się tylko po najdłuższych przekątnych siedmiokąta foremnego.
Jest jeszcze jedna najdłuższa droga z A₁. Jaka?

Podobnie jest z najdłuższymi cyklami (patrz obok).

    Wędrówki pomiędzy 10 punktami na prostej

Na prostej rozważamy 10 punktów leżących tak, jak na rysunku poniżej. Umawiamy się, że w czasie wędrówki chodzimy od punktu do punktu, ignorując pozostałe, tzn. np. w pewnym etapie - kroku, idąc od A₅ do A₇ przechodzimy obok A₆, nie zauważając go. Aby na obrazku trasa była cały czas widoczna, rysujemy każdy etap nieco wyżej od poprzednich. To przejście wyżej jest tylko konwencją rysunku, nie liczy się do długości wędrówki.

Pokazane obok: nie są ani najdłuższe, ani najkrótsze.

Nietrudno zgadnąć, że jest A₁A₂A₃A₄A₅A₆A₇A₈A₉A₁₀ oraz A₁₀A₉A₈A₇A₆A₅A₄A₃A₂A₁.

Pokazany obok jest jednym z wielu. Oto przykłady innych najkrótszych cykli: A₁A₂A₃A₅A₆A₈A₁₀A₉A₇A₄A₁,   A₃A₁A₂A₅A₈A₁₀A₉A₇A₆A₄A₃. Wszystkich najkrótszych cykli jest 2560 = 10 ^. 2⁸.

Dużo trudniej jest znaleźć przykłady najdłuższych cykli. Jeden z nich pokazano powyżej . Jeszcze trudniej uzasadnić, że jest on faktycznie najdłuższy. Poniżej właśnie tym zajmiemy się dokładniej.

Obserwacja 1
W dowolnym cyklu ponad środkiem odcinka A₆A₇ możemy przechodzić z lewa na prawo i z prawa na lewo; przy czym:
- z lewa na prawo przechodzimy nie więcej niż 6 razy, bo tyle jest co najwyżej punktów wyjścia,
- z lewa na prawo przechodzimy nie więcej niż 4 razy, bo tyle jest co najwyżej punktów dojścia,
- z prawa na lewo przechodzimy nie więcej niż 4 razy, bo tyle jest co najwyżej punktów wyjścia,
- z prawa na lewo przechodzimy nie więcej niż 6 razy, bo tyle jest co najwyżej punktów dojścia.
Podsumowując, odcinek A₆A₇ możemy przechodzić co najwyżej 8 razy, przy czym nie więcej niż 4 razy z lewa na prawo i nie więcej niż 4 razy z prawa na lewo.

Obserwacja 1'
W dowolnym cyklu ponad środkiem odcinka A_iA_i+1 możemy przechodzić z lewa na prawo i z prawa na lewo (powiemy w_prawo_krok i w_lewo_krok), przy czym:
- w_prawo_kroków jest nie więcej niż i, bo jest co najwyżej i początków w_prawo_kroków,
- w_prawo_kroków jest nie więcej niż 10-i, bo jest co najwyżej tyle końców w_prawo_kroków,
- w_lewo_kroków jest nie więcej niż 10-i, bo jest co najwyżej tyle początków w_lewo_kroków,
- w_lewo_kroków jest nie więcej niż i, bo jest co najwyżej i końców w_lewo_kroków.
Podsumowując, odcinek A_iA_i+1 możemy przechodzić co najwyżej 2^.min{i, 10-i} razy, przy czym nie więcej niż min{i, 10-i} razy z lewa na prawo i nie więcej niż min{i, 10-i} razy z prawa na lewo.

Obserwacja 2
Dowolny cykl ma długość nie większą niż
  2A₁A₂ + 4A₂A₃ + 6A₃A₄ + 8A₄A₅ + 10A₅A₆ + 8A₆A₇ + 6A₇A₈ + 4A₈A₉ + 2A₉A₁₀.

Zatem pokazany poprzednio (i obok) cykl, jest jednym z najdłuższych.

A jak wyglądają pozostałe najdłuższe cykle?

Obserwacja 3
W dowolnym cyklu, jeśli:
- któryś w_lewo_kroków lub w_prawo_kroków nie przechodzi nad środkiem odcinka A₅A₆, to cykl ten nie jest najdłuższy (jest krótszy od najdłuższych co najmniej o długość A₅A₆),
- w każdym w_lewo_kroku i w każdym w_prawo_kroku przechodzimy nad środkiem odcinka A₅A₆, to cykl ten jest najdłuższy.

Zatem wszystkie najdłuższe cykle wypiszemy, pisząc na przemian punkty z dwóch grup: {A₁A₂A₃A₄A₅} i {A₆A₇A₈A₉A₁₀}; innymi słowy, gdy w każdym kroku (i w_prawo_kroku, i w_lewo_kroku) przechodzić będziemy ponad środkiem odcinka A₅A₆. Tych najdłuższych cykli jest 2^.(5!)² = 28800.

Badanie najdłuższych dróg zaczniemy od banalnej uwagi.

Obserwacja 4
Dowolną drogę można przedłużyć do cyklu, dodając krok od ostatniego do pierwszego punktu drogi.

Obserwacja 5
Dowolna droga ma długość nie większą niż
  d = 2A₁A₂ + 4A₂A₃ + 6A₃A₄ + 8A₄A₅ + 9A₅A₆ + 8A₆A₇ + 6A₇A₈ + 4A₈A₉ + 2A₉A₁₀.

Jest tak faktycznie, bo przedłużając drogę, dostajemy (dłuższy) cykl. Jeśli ten cykl nie jest jednym z najdłuższych, to na podstawie Obserwacji 3 ma długość nie większą niż d. Jeśli jest jednym z najdłuższych, to w każdym kroku, więc i w tym kroku dodanym do drogi, przechodzi nad odcinkiem A₅A₆, więc długość drogi nie przekracza d.

Można już zatem opisać wszystkie najdłuższe drogi.

Obserwacja 6
Droga jest najdłuższa, gdy zaczyna się i kończy w zbiorze { A₅, A₆} i w każdym kroku (i w_prawo_kroku, i w_lewo_kroku) przechodzi nad środkiem odcinka A₅A₆.

Zatem pokazana poprzednio (i obok) droga, jest jedną z najdłuższych. Jest ich 2^.(4!)² = 1152.

Uwaga 7
Zauważmy, że wśród dróg od A₁ do A₁₀ najdłuższymi są te (i tylko te), w których w każdym kroku (i w_prawo_kroku, i w_lewo_kroku) przechodzi się nad środkiem odcinka A₅A₆, np. A₁A₆A₂A₇A₃A₈A₄A₉A₅A₁₀. Bowiem uzupełniając takie drogi w_lewo_krokiem A₁₀A₁, dostajemy najdłuższe cykle. Takich najdłuższych dróg jest (4!)² = 576.

Uwaga 8
Powyższe rozważania łatwo można uogólnić na sytuację z dowolną parzystą liczbą punktów na prostej. (Szczegóły pomijamy.)

Uwaga 9
Badanie sytucji z nieparzystą liczbą punktów na prostej jest nieco trudniejsze. Zachęcamy do zbadania przypadku 9 punktów. (Szczegóły pomijamy.)
Podpowiedź 1. W pewnym sensie można zignorować środkowy punkt A₅, dorzucając go jako 'przystanek' w pewnym w_lewo_kroku lub w_prawo_kroku.
Podpowiedź 2. Najtrudniejsze jest zbadanie najdłuższych dróg. Mają one długość
2A₁A₂ + 4A₂A₃ + 6A₃A₄ + 8A₄A₅ + 8A₅A₆ + 6A₆A₇ + 4A₇A₈ + 2A₈A₉ - min{A₄A₅,A₅A₆}

    Wędrówki po ośmiokącie foremnym

Badanie cykli i dróg wiodących przez wszystkie wierzchołki ośmiokąta foremnego wydaje się analogiczne do badań dla siedmiokąta foremnego. Tak jest faktycznie (patrz odpowiedzi obok) z wyjątkiem badania najdłuższych cykli. Skąd bierze się tu jakaś istotna zmiana? Poniżej spróbujemy to prześledzić.

Zacznijmy od najdłuższych dróg. Ta pokazana obok jest faktycznie jedną z najdłuższych, bo biegnie przez wszystkie 4 najdłuższe przekątne, a pozostałe 3 kroki są wzdłuż przekątnych o długościach największych wśród wszystkich pozostałych przekątnych.

Uzupełnienie tej drogi krokiem A₈A₁ daje cykl. NIE JEST TO NAJDŁUŻSZY CYKL.

DLACZEGO?

Można 'zmusić' komputer, by zbadał wszystkie 7! cykli startujących (i kończących się) w A₁ i obliczał ich długości, wybierając wśród nich największe. Poniżej widać efekt. Cyklu z rysunku nie ma wśród najdłuższych.

147263851 -> długość = 15.086554390135441
147385261 -> długość = 15.086554390135441
148527361 -> długość = 15.086554390135441
152748361 -> długość = 15.086554390135443
158362741 -> długość = 15.086554390135441
162583741 -> długość = 15.086554390135443
163725841 -> długość = 15.086554390135441
163847251 -> długość = 15.086554390135441

Powyższe obliczenia nie odpowiadają na pytanie 'dlaczego', a jedynie na pytanie 'jak jest'. Od razu odnotujmy: NIE WIEM 'DLACZEGO?'.

Zadziwiające jest, że te najdłuższe cykle przechodzą tylko przez dwie najdłuższe przekątne ośmiokąta. Pomagając sobie komputerem, można sprawdzić, że dla 2n-kątów foremnych, dla n=3,4,5,6,7,8,9,10 też tak jest.

Obesrwacja komputerowa
Ustalmy n=3,4,5,6,7,8,9,10 i wierzchołki 2n-kąta foremnego. Wśród cykli obchodzących wierzchołki tego 2n-kąta foremnego jest 2n najdłuższych startujących z ustalonego wierzchołka. Wszystkie one biegną przez dwie najdłuższe przekątne, a pozostałe kroki mają długości równe drugiej co do długości przekątnej tego 2n-kąta.

Czy tak jest dla DOWOLNEGO n?

Potrafię uzasadnić następujące obserwacje.

Obserwacja 10.
Ustalmy n - dowolną liczbę naturalną większą niż 3 i wierzchołki 2n-kąta foremnego wpisanego w koło o promieniu 1. Nazwijmy kolejne wierzchołki kolejnymi liczbami naturalnymi 1, 2, 3, ..., 2n. Wtedy:
  a)  cykl 1(n+1)2(n+2)3(n+3)...n(n+n)1 ma długość 2n+(n-1)^.2cos(pi/(2n)) + 2sin(pi/(2n)),
  b)  2n+(n-1)^.2cos(pi/(2n)) + 2sin(pi/(2n))   <   2^.2+(2n-2)^.2cos(pi/(2n)),
  c)  istnieje 2n cykli o długości   2^.2+(2n-2)^.2cos(pi/(2n)),
  d)  cykle o krokach tylko dwóch długości: 2 i 2cos(pi/(2n)) mają dokładnie 2 kroki dlugości 2,
  e)  różnica między długościami najdłuższych cykli a cyklami takimi jak w c) maleje do zera wraz ze zrostem n.

Uzasadnienia a), b) i e) nie są zbyt pasjonujące. Są na tyle żmudne, że pomijamy tu szczegóły.
Uzasadnienie punktu c) nie jest trudne. Wystarczy kodować cykle jak na poniższych rysunkach.

Natomiast poniższy rysunek przedstawia strukturę połączeń wierzchołków 10-kąta foremnego. Odcinki pionowe reprezentują połączenia najdłuższe (wzdłuż najdłuższych przekątnych). Pozostałe linie reprezentują połączenia przekątnymi długości największej wśród pozostałych przekątnych. Za pomocą takiego schematu można (dość zawile) uzasadnić podpunkt d).