Podróżne dylematy

Przed długim weekendem czerwcowym wiele rodzin/osób zastanawiało się jak spędzić ten czas. Czy spędzić go w domu czy wyjechać? Spędzić go w jednym miejscu czy w kilku? Przedłużyć weekend czy skorzystać tylko z 4 dni? Odwiedzić rodzinę? Kogo i kiedy? Gdzie nocować? Którędy jechać? Co zabrać? Wziąć urlop czy nie? Co załatwić? Co zrobić? Z czego zrezygnować? Gdzie będą korki na drodze? Gdzie są utrudnienia w ruchu? Jaki jest koszt przejazdu? I wiele innych pytań.

Jednym z elementów jest kwestia przemieszczania się, czyli jakie miejscowości oraz w jakiej kolejności odwiedzić. Załóżmy, że mamy do odwiedzenia kilka miejsc (lokalizację, z której startujemy oraz 4 inne lokalizacje, tak jak na poniższym diagramie) i chcemy każde z nich odwiedzić tylko raz i wrócić do domu. Przejazd między miastami jest związany z kosztem przejazdu, odległością oraz czasem potrzebnym na przejazd (przykładowe elementy zostały wskazane na dostępnych połączeniach na diagramie).

Jest to związane z tzw. problemem komiwojażera (ang. travelling salesman problem). Chodzi o wybór najszybszej, najkrótszej lub najtańszej ścieżki (w zależności od zastosowanych wag na przejściach) przejścia po takim diagramie (dokładnie grafie), w ramach której wyruszamy z danego punktu początkowego, odwiedzamy wszystkie lokalizacje i wracamy do punktu początkowego, odwiedzając każdą lokalizację (poza początkową) tylko raz.

Myślę, że z takim problemem spotkało się wiele osób mających w planach odwiedzenie kilku lokalizacji (nie wnikam z jakiego powodu) – nie istotne czy są to punkty na obszarze danego kraju, kilku krajów, kontynentów czy danego regionu lub miasta. Można wykorzystać różne środki komunikacji lub skorzystać z własnego. Można poruszać się też pieszo. Mogą wystąpić roboty drogowe, objazdy, zwiększone natężenie ruchu czy może konieczne jest wykorzystanie przeprawy promowej. Elementy te wpływają na koszty i czas przejazdu. Z kolei ukształtowanie terenu może spowodować, że trasa blisko położonych lokalizacji w linii prostej, może się znacznie wydłużyć. Niektórzy oferują także przewóz dodatkowych osób, zmniejszając koszt przejazdu po swojej stronie. Atrybuty na połączeniach powinny uwzględniać wszystkie te elementy w zakresie czasu, kosztu przejazdu czy też fizycznej odległości.

komiwojazer_584px

Na diagramie wskazałem przykładowe odległości, ceny i czas przejazdu między 5 lokalizacjami, zakładając, że jedna z nich jest traktowana jako startowa. Atrybuty te na pierwszy rzut oka mogą się wydawać nielogiczne, ale starałem się uwzględnić, nie wskazując tego wprost, niektóre z powyższych elementów. Bez problemu można znaleźć na nim ścieżkę, która odwiedza wszystkie wierzchołki (lokalizacje) i wraca do początkowego punktu. Przykładem jest ścieżka START->4->2->1->3->START lub START->1->2->3->4->START. Oznacza to, że powyższe połączenia między lokalizacjami tworzą tzw. cykl Hamiltona. Znalezienie takiej ścieżki o najmniejszej wartości atrybutu branego pod uwagę jest rozwiązaniem problemu komiwojażera.

Dla podanego grafu (połączenia między lokalizacjami go tworzą) mamy takie cykle (wydaje mi się, że to wszystkie i że się nie pomyliłem podczas zliczania):

Przykładowy cykl Odległość
(km)
Koszt
(zł)
Czas
(h)
Śr. 
prędkość
km/h
Liczba 
km/zł
START>4>2>1>3>START i odwrotnie 470 41 6 78,33 11,46
START>1>2>3>4>START  i odwrotnie 660 33 11 60,00 20,00
START>3>4>2>1>START  i odwrotnie 430 36 8 53,75 11,94
START>1>3>2>4>START  i odwrotnie 670 48 9,5 70,53 13,96

Wśród wskazanych powyżej cykli widać, że pierwszy ma najmniejszy czas przejazdu, drugi najniższą cenę a trzeci najkrótszą odległość. Osobiście wybrałbym pierwszą ścieżkę.

Przy większej liczbie lokalizacji i połączeń, proces wyszukiwania „najlepszego” rozwiązania komplikuje się obliczeniowo. Można jednak powiedzieć, że wyznaczenie optymalnej trasy jest częścią większego procesu składającego się z określenia lokalizacji do odwiedzenia, oszacowania kosztów, czasu oraz odległości wymaganych do pokonania, czyli atrybutów połączeń, zaplanowania sposobu postępowania (wybór całej ścieżki lub pierwszych kroków, a potem dostosowywanie), realizacji planu, a na koniec oceny planu (np. wybrana droga nie nadaje się do użytkowania) i dostosowanie na przyszłość. Na diagramie został wskazany taki proces – kolorem zostały zaznaczone kroki odnoszące się do diagramu połączeń.

Atrybuty na powyższym diagramie można zmieniać podczas następnego podejścia lub na przykład likwidować określone krawędzie/połączenia jako nieakceptowalne z perspektywy kolejnej realizacji takiej „podróży”. Można także dodawać i odejmować lokalizacje i połączenia. Istotne jest to, że przy każdej takiej zmianie może nastąpić zmiana optymalnego rozwiązania, a także może zmienić się liczba cykli.

Przechadzka po szachownicy po raz drugi

Przy okazji omawiania wzorca Odwiedzający skorzystałem z przykładu przechodzenia skoczkiem przez wszystkie pola szachownicy tak, aby każde pole odwiedzić tylko raz, zaczynając z różnych miejsc na szachownicy. Mechanizm szuka kolejnych pól, przechodzi dalej lub cofa się, jeżeli nie jest możliwe dalsze przejście. Rozwiązanie takiego problemu istnieje i pewnie nie jeden pasjonat szachów próbował to zrobić na kartce lub szachownicy. Szachownica zaprezentowana jest na poniższych diagramach. Zaznaczone są także przykładowe przejścia.

Wyobraźmy sobie, że każde pole szachownicy umieszczamy na grafie w węźle, a te węzły, które można ze sobą połączyć, łączymy krawędzią, stosując “wirtualną” odległość opartą o 2 kratki w pionie lub poziomie i 1 odpowiednio w poziomie lub pionie. W taki sposób można rozwiązać także inne sytuacje, np. łączenie wykładowców i przedmioty lub inne sytuacje biznesowe. Fragment takiego grafu jest zaprezentowany na poniższym diagramie.

szach_animated

W tym przykładzie w zależności od położenia pola na szachownicy, dany węzeł grafu ma 2 (kolor czerwony), 3 (kolor zielony), 4 (kolor szary), 6 (kolor niebieski) lub 8 (kolor żółty) wyjść. Na powyższym diagramie takie miejsca grafu zosały odpowiednio oznaczone kolorami. W zależności od węzła, od którego rozpoczynamy wędrówkę, mamy więcej lub mniej możliwości zmiany kierunku. Na animacji droga przechodzi przez różne punkty – rozpoczyna się w punkcie z 2 wyjściami (A1), potem przechodzi przez punkty z 6, 8, 4 wyjściami a kończy w punkcie z 4 wyjściami (F8). Nie przechodzi przez punkt z 3 wyjściami.

szachownica_obszary

Powyższe zadanie to tzw. poszukiwanie ścieżki Hamiltona na nieskierowanym grafie, czyli takim, w którym po każdej krawędzi można przejść w 2 strony. Z racji, że każdemu z węzłów można przypisać jeden z dwóch kolorów i nie ma połączenia/krawędzi między dwoma węzłami tego samego koloru, jest to równocześnie graf dwudzielny. W publikacjach można znaleźć różne algorytmy wyszukiwania takiej ścieżki. Więcej można przeczytać o powyższym problemie choćby we wpisie na anglojęzycznej wersji Wikipedii. Niestety w polskiej wersji informacje te są bardzo ograniczone.