W książce umieszczona jest świetna scena, gdy obaj bohaterowie zakradli się nocą do biblioteki i zgubili się w jej wnętrzu. Wilhelm, który zdawać by się mogło, wszelką wiedzę posiadł, prezentuje wtedy pewien sposób na wydostanie się z labiryntu, w którym błądzenie bez celu jest ograniczone do minimum. Przeczytałem sobie jego opis kilka razy i doszedłem do wniosku, że jest to całkiem fajny algorytm (wreszcie - to dla tych, co się zastanawiali, czemu w kategorii "Programowanie" o literaturze nawijam :)). Paręnaście minut temu skończyłem pisać odpowiedni program. Gdyby Wilhelm i Adso mieli wtedy komputery, z pewnością byliby mi za niego wdzięczni :).

W omawianym przeze mnie algorytmie labirynt zostaje odwzorowany jako graf nieskierowany. Poszczególne węzły reprezentują sale, a ścieżki - połączenia między nimi. Przyjąłem, że węzeł o indeksie 1 to wyjście z labiryntu. Do losowego węzła wpuszczamy nieszczęśnika. Ma on przy sobie rysik i podczas wędrówki umownymi znakami zaznacza przejścia. System jest następujący:

• Wchodząc do węzła nieodwiedzonego, ścieżkę przybycia znaczy trzema znakami.
• Wchodząc do węzła odwiedzonego, ścieżkę przybycia znaczy jednym znakiem.
• Wychodząc z węzła, znaczy je dwoma znakami.
• Wychodząc z węzła przez przejście z jednym znakiem, dodaje jeszcze dwa.

Teraz: przy wyborze ścieżki, wybieramy zawsze tę o najmniejszej liczbie znaków (czyli jak mamy 0 i 1, to idziemy tą pierwszą). Pod żadnym pozorem nie wolno nam wejść do ścieżki z dwoma znakami. Jeżeli wszystkie ścieżki są oznaczone dwoma lub trzema znakami, idziemy tą z trzema. W ten sposób po pewnym czasie wrócimy się z powrotem do miejsca, gdzie zaczęliśmy ślepy zaułek.

Takie oznaczanie stopniowo będzie eliminowało nam kolejne partie labiryntu tak, że podczas naszej wędrówki w końcu trafimy do wyjścia. Wiadomo, że komputerowi, który w pamięci trzyma jednocześnie mapę labiryntu, na $#%#$% taki algorytm, ale przecież od czego jest wyobraźnia? Osobiście znalazłem już jedno interesujące zastosowanie, a mianowicie sztuczną inteligencję. Mamy strażnika, który patroluje jakiś gmach, odwiedzając wszystkie sale. Usuwamy ograniczenie "wyjścia z labiryntu" i w ten sposób strażnik będzie robić regularne obchody po budynku bez dziwnego krążenia w kółko. Co jakiś czas resetujemy mu dla zabawy :) ilości znaków w węzłach i zabawa zaczyna się od nowa :).

Nie sprawdzałem jeszcze ani dokładnej złożoności obliczeniowej, ani tego, czy algorytm ten nie nosi już przypadkiem jakiejś uczonej nazwy. Zrobię to w najbliższym czasie, przy okazji publikując kody źródłowe. Zaś jeśli chodzi o złożoność, wstępnie podejrzewam, że może to być O(mn), gdzie n - il. węzłów; m - maks. ilość ścieżek w węźle. W praktyce jednak często bywa dużo niższa. Np. na testowym labiryncie złożonym z 22 węzłów udawało się komputerowi wydostać już po 6 ruchach po wsadzeniu go w najbardziej oddalone zadupie :). Wszystko zależy od kolejności wprowadzenia ścieżek i samego algorytmu wyboru ścieżki.

Powrót

Na Zyxist.com panuje swoboda wyrażania opinii oraz krytyki pod dowolnym adresem. Jedyny warunek: musi być ona kulturalna i rzeczowa. Na chamstwo, prostactwo lub jawne obrażanie kogokolwiek nie ma tu miejsca i takie komentarze są bardzo szybko usuwane. Jeśli zamierzasz polemizować z treścią wpisu, wpierw uważnie ją przeczytaj.