728 x 90

Rumpelstiltskin: zabłądziła księżniczka

Rumpelstiltskin: zabłądziła księżniczka

W poście Na przekór pięknemu umysłowi Nasha: Nie unikniesz Pytii (w decyzjach) pojawia się problem koordynacji wyborów graczy, którzy nie mogą się skomunikować. Dziś odbędziemy magiczną podróż na oślep. Nie wiedząc, które miejsce w danym momencie odwiedzamy i które miejsca już odwiedziliśmy, zrealizujemy plan wycieczki. Rzecz wykazuje pewien związek z algorytmiczną losowością.

Zły czarnoksiężnik uwięził księżniczkę w lochach jednego ze swych czterech ludzkim okiem nieodróżnialnych zamczysk: A, B, C lub D. By odczynić zły urok księżniczka musiałaby odwiedzić wszystkie zamki. Może jedynie przeskakiwać między zamkami za pomocą zaklęć, pojawiając się za każdym razem w identycznym lochu. Np. aby przeskoczyć z zamku A do zamku C musiałaby użyć zaklęcia §AC. Fakt, że w wyniku użycia zaklęcia §AC księżniczka pojawi się w zamku C, gdy przebywała w A możemy zapisać jako §AC(A)=C. Księżniczka zna wszystkie zaklęcia do przeskoków między zamkami. Co ważniejsze, zna również efekt działania zaklęcia celowego użytego w niewłaściwym zamku, tzn. wie jaki będzie wynik działania powiedzmy §AC(B); przyjmijmy dla ustalenia uwagi, że w ramach złośliwości losu akurat §AC(B)=A, czyli księżniczka sądzi, że jest w zamku A i chce przeskoczyć do C, podczas gdy w rzeczywistości jest w zamku B i ląduje w A. Księżniczka ma oczywiście świadomość, że jeśli nie jest w A, lecz w B, to  stosując swoje zaklęcie §AC, zamiast wylądować w C pojawi się w A. Mamy zatem do czynienia z funkcjami §XY: {A,B,C,D} → {A,B,C,D}, X,Y in {A,B,C,D}, X≠Y, o własności §XY(X)=Y.

Dlaczego nie znaczyć odwiedzanych miejsc, zapyta może Czytelnik? Choć to nie bajka o Jasiu i Małgosi, by znaczące drogę okruszki wyjadły zwierzęta leśne, ewentualne ślady znikają wnet po opuszczeniu odwiedzonego przez księżniczkę zamku.

Czy księżniczce uda się odczynić zły urok? Mogłaby rzucać zaklęcia na oślep. W ten sposób (jeśli nie popadłaby w złe nawyki rzutujące na niezależność wyboru zaklęć) przeprowadziłaby nasza księżniczka serię prób Bernoulliego. Poddając się ślepemu losowi, z prawdopodobieństwem równym 1 odwiedzi wszystkie zamki. (Jaki będzie średni czas oczekiwania na uwolnienie?) Przy czym prawie na pewno, to jeszcze nie na pewno. Zdarzenie, że księżniczka nigdy się nie uwolni jest zdarzeniem możliwym.

Czy istnieje jakiś algorytm deterministyczny? Tak. Można skomponować serię zaklęć w ten sposób, by ich melodia przeprowadziła nas przez wszystkie zamki. A Ty Czytelniku, czy znasz już tę melodię? Jeśli tak, to niestraszny Ci żaden Rumpelstiltskin, choć bywa groźny (por. Przekleństwo Kahana: Tanie zabawy floatami).

Nie wychodzi? Nie poddawaj się. Jeśli Ci nie idzie, to możesz zmniejszyć liczbę zamków.

Jeśli przeszkadza Ci, że tak mało wiesz o zaklęciach §XY, to przyjmij za §XY konkretne funkcje. Oczywiście istnieje wiele funkcji §XY: {A,B,C,D} → {A,B,C,D} spełniających warunek §XY(X)=Y. Można przyjąć np.  §XY(Z)= Y+ (Z-X), gdzie X,Y,Z in {A,B,C,D}, a dodawanie (+) i odejmowanie (-) są rozumiane jako działania na resztach z dzielenia przez 4, jeśli utożsamić A=0, B=1, C=2, D=3 (tzw. grupa cykliczna Z4 obrotów kwadratu o wierzchołkach ABCD). Dla przykładu: C+C= 2+2=4=0 =A, §AB(D)= B+ (D-A) =1+ (3-0)=4=0 =A.

Dla spragnionych ksiąg zakazanych zamieszczam rozwiązanie problemu księżniczki TU.

Okazuje się, że takie historie (fairy tales) jak powyżej przedstawiona bajka o księżniczce-podróżniczce, stoją za derandomizacją algorytmu iteracji losowej. Algorytm ten, znany również pod nazwą gra w chaos, jest fundamentalny dla praktycznych zastosowań geometrii fraktalnej (Playing the Chaos Game; M. Barnsley, 28 February 2013, MSI ANU; w streszczeniu wystąpienia nie na darmo występują ,,fairy tales”). Nieco dokładniej rzecz ujmując, derandomizację uzyskuje się poprzez zastosowanie ciągów dyzjunktywnych, zaś skomplikowane zaklęcia to wytrychy potrzebne ciągowi iteracyjnemu, by się włamać do którejś z przyzwoitych i okiełznanych orbit iteracji. Ciąg dyzjunktywny – jak wiadomo – zawiera w sobie wszystkie wytrychy świata.

W eseju O losowości nie tylko w informatyce. Część 2  wspomniane było zastosowanie algorytmicznej losowości do gry chaosu. Teraz wiemy już nieco więcej. Być może kiedyś wrócę do sprawy i przedstawię dalsze szczegóły bajkowej operacji.

(A skąd znak §? Jakiś Perlowy dolar? Nie, §pell.)

Źródło obrazu tytułowego: https://pixabay.com/pl/niemcy-map-zamek-neuschwanstein-2232607/

Leave a Comment

Your email address will not be published. Required fields are marked with *

Cancel reply

Inne artykuły