Всем привет.
Не так давно мне попалась интересная задачка, условием и решением которой я хочу поделиться. Надеюсь, это не будет жутким “баяном”. Итак, представим себе стандартную шахматную доску 8x8, на которой нет ни одной фигуры. Далее, мы случайным образом помещаем коня в любую клетку. Задача — определить вероятность, что после N ходов случайным образом он останется на шахматной доске. Предполагается, что если конь покидает доску, то не может войти заново. А каждый из возможных ходов является равновероятным. Другими словами, необходимо реализовать функцию:
где N — количество ходов, а x и y — координаты начальной позиции.
Если несколько вариантов решения данной задачи: цепи Маркова и динамическое программирование. Здесь я хочу предложить решение, используя прием динамического программирования. Идея заключается в том, чтобы при каждом i-ом ходе отслеживать вероятность того, что конь окажется в определенной клетке.
Из каждой позиции конь может сделать один из 8 возможных ходов (серым обозначены возможные ходы)
Все возможные позиции для текущей клетки удобно записать, если ввести 2 массива:
тогда следующее состояние будет
Далее введем массив probability[steps][xPos,yPos], где steps — количество уже сделанных шагов, а xPos и yPos — координаты клеток доски. В стартовой клетке вероятность равна 1, а на всех остальных равна 0. После каждого хода вероятность на одной из возможных клеток будет составлять 1/8, а на остальных останется 0. Тогда после N ходов для любой определенной клетки вероятность будет находиться как сумма вероятностей возможных клеток за N-1 ходов. Таким образом, мы можем подсчитать вероятность после каждого хода для всех 64 клеток и получим алгоритм:
Жду комментариев и, возможно, других способов решения данной задачки. Готовую реализацию можно скачать здесь.
Не так давно мне попалась интересная задачка, условием и решением которой я хочу поделиться. Надеюсь, это не будет жутким “баяном”. Итак, представим себе стандартную шахматную доску 8x8, на которой нет ни одной фигуры. Далее, мы случайным образом помещаем коня в любую клетку. Задача — определить вероятность, что после N ходов случайным образом он останется на шахматной доске. Предполагается, что если конь покидает доску, то не может войти заново. А каждый из возможных ходов является равновероятным. Другими словами, необходимо реализовать функцию:
double probability(int N, int x, int y), 0 <= x <= 7, 0 <= y <= 7,где N — количество ходов, а x и y — координаты начальной позиции.
Если несколько вариантов решения данной задачи: цепи Маркова и динамическое программирование. Здесь я хочу предложить решение, используя прием динамического программирования. Идея заключается в том, чтобы при каждом i-ом ходе отслеживать вероятность того, что конь окажется в определенной клетке.
Из каждой позиции конь может сделать один из 8 возможных ходов (серым обозначены возможные ходы)
Все возможные позиции для текущей клетки удобно записать, если ввести 2 массива:
int dx[] = new int[] { 1, 2, 2, 1, -1, -2, -2, -1 };
int dy[] = new int[] { 2, 1, -1, -2, -2, -1, 1, 2 };
тогда следующее состояние будет
(x + dx[i], y + dy[i]), 0 <= i <= 7.Далее введем массив probability[steps][xPos,yPos], где steps — количество уже сделанных шагов, а xPos и yPos — координаты клеток доски. В стартовой клетке вероятность равна 1, а на всех остальных равна 0. После каждого хода вероятность на одной из возможных клеток будет составлять 1/8, а на остальных останется 0. Тогда после N ходов для любой определенной клетки вероятность будет находиться как сумма вероятностей возможных клеток за N-1 ходов. Таким образом, мы можем подсчитать вероятность после каждого хода для всех 64 клеток и получим алгоритм:
double probability(int N, int startX, int startY) {
double probability[][][] = new double[N + 1][8][8];
// init to 1 for beginning position
for (int x = 0; x < 8; x++) {
for (int y = 0; y < 8; y++) {
probability[0][x][y] = 1;
}
}
int dx[] = new int[] { 1, 2, 2, 1, -1, -2, -2, -1 };
int dy[] = new int[] { 2, 1, -1, -2, -2, -1, 1, 2 };
for(int n = 1; n <= N; n++) {
for(int x = 0; x < 8; x ++) {
for(int y = 0; y < 8; y++) {
double currentProbability = 0.0;
for(int i = 0; i < 8; i++) {
if (x+dx[i] >= 0 && x+dx[i] < 8 && y+dy[i] >= 0 && y+dy[i] < 8) {
currentProbability += probability[n-1][y+dy[i]][x+dx[i]] / 8.0;
}
}
probability[n][y][x] = currentProbability;
}
}
}
return probability[N][startX][startY];
}
Жду комментариев и, возможно, других способов решения данной задачки. Готовую реализацию можно скачать здесь.
Комментарии (12)
alexeykuzmin0
01.01.2018 18:07А зачем считать вероятность 64 раза? Можно изначально заполнить поле не «нулями и одной единицей в начальной клетке», а числом 1/64.
EndUser
01.01.2018 18:32+1Путь, пройденный шагами b (для коня 2.27), каждый в случайном направлении, за n шагов, равен r=v(nb?). /Эйнштейн, 1905/
EndUser
01.01.2018 19:34Случайно вспомнил этот факт.
Это из «Библиотека „Квант“ №25 (1983). Самая главная молекула. /Франк-Каменецкий/».
Книга о ДНК, на странице 46 глава «Она похожа на путь человека, заблудившегося в лесу».
P.S. Зело азартно написанная книга, кстати.
lxsmkv
02.01.2018 05:58мне попалась
укажите источник. Я не знаком с такой задачей, хотелось бы почитать про нее больше и поискать другие решения. Кому тоже интересно, вот:
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 Автор
02.01.2018 11:03Это был эвент для найма в осло. После на как минимум на geeksforgeeks решение не нашел
mikhaelkh
Для больших N лучше построить матрицу перехода и возвести её в N-ю степень. Можно также воспользоваться симметричностью доски и сократить число клеток с 64 до 10. Можно также построить Жорданову форму матрицы перехода.
Andrey_V_Markelov Автор
Да, Вы правы, но по моему такое решение требует более серьезной математической подготовки.
excoder
А можно подробнее про жорданову форму для таких задач?
saluev
Я так понимаю, чтобы быстрее в степень возводить.
excoder
Понятно, что если A = C^(-1) * J * C, то A^n = C^(-1) * J^n * C. Хочется узнать, является ли приём с жордановой формой для возведения матрицы в степень неким фольклором, который везде применяется — может быть, есть ссылки на литературу? Я просто сам никогда не встречал в литературе по алгоритмике.
saluev
Точно не в алгоритмике — жорданова форма вычислительно неустойчива и в вычислениях не используется.