Задача о шахматном коне и вероятности

[mikhaelkh]

Для больших N лучше построить матрицу перехода и возвести её в N-ю степень. Можно также воспользоваться симметричностью доски и сократить число клеток с 64 до 10. Можно также построить Жорданову форму матрицы перехода.

[Andrey_V_Markelov]

Да, Вы правы, но по моему такое решение требует более серьезной математической подготовки.

[excoder]

А можно подробнее про жорданову форму для таких задач?

[saluev]

Я так понимаю, чтобы быстрее в степень возводить.

[excoder]

Понятно, что если A = C^(-1) * J * C, то A^n = C^(-1) * J^n * C. Хочется узнать, является ли приём с жордановой формой для возведения матрицы в степень неким фольклором, который везде применяется — может быть, есть ссылки на литературу? Я просто сам никогда не встречал в литературе по алгоритмике.

[saluev]

Точно не в алгоритмике — жорданова форма вычислительно неустойчива и в вычислениях не используется.

[alexeykuzmin0]

А зачем считать вероятность 64 раза? Можно изначально заполнить поле не «нулями и одной единицей в начальной клетке», а числом 1/64.

[EndUser]

Путь, пройденный шагами b (для коня 2.27), каждый в случайном направлении, за n шагов, равен r=√(nb²). /Эйнштейн, 1905/

[Andrey_V_Markelov]

Не знал. Спасибо

[EndUser]

Случайно вспомнил этот факт.
Это из «Библиотека „Квант“ №25 (1983). Самая главная молекула. /Франк-Каменецкий/».
Книга о ДНК, на странице 46 глава «Она похожа на путь человека, заблудившегося в лесу».

P.S. Зело азартно написанная книга, кстати.

[lxsmkv]

мне попалась

укажите источник. Я не знаком с такой задачей, хотелось бы почитать про нее больше и поискать другие решения. Кому тоже интересно, вот:
leetcode.com/articles/knight-probability-in-chessboard (задача с решениями)
www.geeksforgeeks.org/probability-knight-remain-chessboard (задача с решением)
community.topcoder.com/stat?c=problem_statement&pm=3509&rd=6528 (задача)
community.topcoder.com/tc?d1=match_editorials&d2=tccc05_online_rd_1&module=Static#3509 (решение)
www.quora.com/Given-the-position-x-y-of-a-knight-on-an-8X8-chess-board-what-is-the-probability-that-it-stays-within-the-chess-board-after-n-moves(решение)

Второе:
Интереснее было бы если бы вы добавили что-то к этой задаче. Например сделать решение для трехмерной «доски». Хотя подход будет наверное ровно тем же.

Третье:
В принципе это хороший пример, чтобы показать, что математическую вероятность и вероятность реальную можно легко перепутать. Ведь если мы не станем двигать коня на конкретной доске, вероятность, того что он окажется на любой другой подходящей клетке либо за пределами доски будет 0. Так же я могу просто переместить коня за пределы доски. Это не по правилам но возможно. И вероятность будет 1. Т.е пространство вариантов всегда шире чем моделируют в вероятностном эксперименте. Именно поэтому полагаться на вероятностное исчисление для построения прогнозов нужно как минимум очень осторожно.

Четвертое:
Полвека назад когда за каждый час вычислений на компьютере нужно было платить приличные деньги, такие задачи решали на бумаге аналитическим путем. Чтобы понять о чем я: как вы можете убедиться в том, что выданное программой решение верное.
Вспомним парадокс Монти Холла, задачи которую большинство людей решали (и решают) неверно. Даже здравомыслящие люди могут быть едины в своем ошибочном решении.

[Andrey_V_Markelov]

Это был эвент для найма в осло. После на как минимум на geeksforgeeks решение не нашел