Всем привет.
Не так давно мне попалась интересная задачка, условием и решением которой я хочу поделиться. Надеюсь, это не будет жутким “баяном”. Итак, представим себе стандартную шахматную доску 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];
}
Жду комментариев и, возможно, других способов решения данной задачки. Готовую реализацию можно скачать здесь.
