h1

Przechadzka po szachownicy po raz drugi

Wrzesień 23, 2017

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.

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj /  Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj /  Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj /  Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj /  Zmień )

w

Connecting to %s

%d blogerów lubi to: