Macierz przejścia-szachownica

Ogólne pogawędki i dywagacje
paula.0120
Posty: 9
Rejestracja: śr mar 18, 2020 11:20 pm

Macierz przejścia-szachownica

Post autor: paula.0120 »

Cześć mam pytanie.
Ostatnio zainteresowały mnie spacery losowe, łańcuch Markowa oraz macierze przejścia.
Zaczęłam zastanawiać się jak wyznaczyć taką macierz przejścia dla ruchów skoczka po szachownicy. Czy jest jakiś sposób? Bardzo proszę o jakieś wskazówki. :)
OpenOffice 3.1 na Windows
Jan_J
Posty: 4558
Rejestracja: pt maja 22, 2009 1:20 pm
Lokalizacja: Wrocław

Re: Macierz przejścia-szachownica

Post autor: Jan_J »

O przejściu przez szachownicę:

Klasyczne rozwiązanie to algorytm z powrotami: próbowanie następnego ruchu jeśli jest możliwy; wypisanie rozwiązania jeśli się zakończy, i cofnięcie do ostatniej rokującej nadzieję możliwości jeśli coś się „zatka”.

Klasyczna lektura: Niklaus Wirth Algorytmy + struktury danych = programy. Książka ma swoje lata, ale była wznawiana w XXI wieku (WNT). Własne eksperymenty robiłbym nie tylko w klasycznym wariancie 8×8, ale ogólnym m×n, i nie tylko ze skoczkiem z ruchem prosto/w skos.

Przy okazji, przejście tablicy/macierzy/szachownicy (np. ruchem skoczka) i macierz przejścia w łańcuchach Markowa to są zupełnie, ale to zupełnie różne rzeczy. Gromadzenie ich ot tak w jednym temacie to jakaś niedelikatność co najmniej, albo nieporozumienie (albo z botem rozmawiam i o tym nie wiem!).

Co do łańcuchów Markowa, jest to trudniejsze zagadnienie, do którego warto mieć podstawy matematyczne. MC są jednym z wiodących tematów pięknej książki Briana Kernighana i Roba Pike'a Lekcja programowania. O ile pamiętam też WNT, też wznawiane w 200x roku.
Jest również ładny rozdział o MC u Jona Bentelya Perełki programowania (czy jak chcą inni tłumacze, Perełki oprogramowania). Wydawane wielokrotnie. Przy Twoich zainteresowaniach jest to bardzo pożyteczna lektura. Późniejsze wydania są rozbudowane w stosunku do poprzednich.

// Chyba musimy założyć wątek Pogawędki / Porady bibliograficzne dla adeptów programowania? Bo do „Form pierwszego kontaktu” to wszystko się nie nadaje. Przenoszę do „Pogawędek”.
JJ
LO (7.6|24.2) ∙ Python (3.12|3.10) ∙ Unicode 15 ∙ LᴬTEX 2ε ∙ XML ∙ Unix tools ∙ Linux (Rocky|CentOS)
ODPOWIEDZ