Вероятность смерти человека, движущегося n шагов в матрице

Question

Существует остров, который представлен квадратной матрицей nxn.

Человек на острове стоит на любой заданной координате (x, y). Он может двигаться в любом направлении на один шаг вправо, влево, вверх, вниз по острову. Если он выходит за пределы острова, он умирает.

Пусть остров будет представлен как (0,0) - (n-1, n-1) (т.е. матрица nxn) & человек стоит при заданных координатах (x, y). Ему разрешено перемещать n шагов на остров (вдоль матрицы). Какова вероятность того, что он мертв после того, как он совершит n шагов на острове?

Каким должен быть подход к поиску вероятности с использованием методов программирования?

У меня есть математический метод, но я не знаю, правильно это или нет. Вот он:

Общее количество исходов n^n. Чтобы вычислить количество результатов, которые могут привести к смерти человека:

Для каждого из четырех направлений проверьте, сколько шагов может привести к его выходу из матрицы. Затем примените формулу вероятности средней школы. Напр. предположим, что общее количество шагов, которые он может предпринять, равно 5; (x, y) = (2,1) [индексирование основано на 0]. Итак, ему нужно сделать 3 шага в северной дир. выпадать из острова. Сохраняя их в группе: (NNN) и делая другие 2 шага как любой из 4 вариантов, мы имеем формулу: 4 * 4 * 3. Аналогично, для других трех направлений. Наконец, вероятность = (сумма рассчитанных летальных исходов)/(итоговые результаты)

Это был вопрос интервью с Google.

Answer 1

TL; DR: Рекурсия. (Или «Математическая индукция», если вы пафосно.)

(В дальнейшем, «он умер после того, как он ходит n шаги на острове» Предполагается, что значит «он умирает после того, как меньше или равна n шаги». Если взять это означает„он умирает после того, как именно n шагов“, ответ будет немного отличаться. Я буду обсуждать это кратко в конце.)

Мы имеем NxN матрицу, где значение в каждом ячейка представляет вероятность смерти в n шагах, если мы начали с этой ячейки.

Учитывайте вероятность смерти в 0 шагах. Ясно, что это 0.0 для каждого местоположения на острове, и 1.0 везде вне его.

Какова вероятность смерти в 1 шагах? У вас есть четыре направления, в которые вы можете двигаться, с равной вероятностью. Поэтому для каждой ячейки вы берете четырех своих соседей, обнаруживаете вероятность их смерти в шагах 0 и усредняете их вместе. (Если сосед находится вне матрицы, если учесть его вероятность быть 1.0.)

Аналогично, вероятность смерти в k шагов, начиная от данной ячейки является среднее значение вероятности смерти в k-1 шагов, начиная с его соседних ячеек.

Python код:

from itertools import product as prod 

def prob_death(island_size, steps): 
    if island_size < 1 or steps < 0: raise ValueError 
    new_prob = [[0. for i in range(island_size)] for j in range(island_size)] 
    if steps == 0: 
     return new_prob 
    old_prob = prob_death(island_size, steps - 1) 
    directions = [(0, -1), (1, 0), (0, 1), (-1, 0)] 
    for (i, j, direction) in prod(range(island_size), range(island_size), directions): 
     neighbor_i = i + direction[0] 
     neighbor_j = j + direction[1] 
     if neighbor_i >= 0 and neighbor_i < island_size and \ 
       neighbor_j >= 0 and neighbor_j < island_size: 
      prob_death_this_way = old_prob[neighbor_i][neighbor_j] 
     else: # neighbor is outside the island 
      prob_death_this_way = 1. 
     new_prob[i][j] += 0.25* prob_death_this_way 
    return new_prob 

Теперь давайте проверим его немного: (mpr это просто функция для печати матриц красиво)

>>> mpr(prob_death(5, 0)) 
0.000000 0.000000 0.000000 0.000000 0.000000 
0.000000 0.000000 0.000000 0.000000 0.000000 
0.000000 0.000000 0.000000 0.000000 0.000000 
0.000000 0.000000 0.000000 0.000000 0.000000 
0.000000 0.000000 0.000000 0.000000 0.000000 

Как и ожидалось: Вы не можете умереть 0 шагов, если вы начнете с острова.

>>> mpr(prob_death(5,1)) 
0.500000 0.250000 0.250000 0.250000 0.500000 
0.250000 0.000000 0.000000 0.000000 0.250000 
0.250000 0.000000 0.000000 0.000000 0.250000 
0.250000 0.000000 0.000000 0.000000 0.250000 
0.500000 0.250000 0.250000 0.250000 0.500000 

Это то, чего мы ожидаем. Если вы начинаете с угловой ячейки, у вас есть 0.5 вероятность смерти в 1 шаге: 2 из ваших 4 соседей находятся за пределами острова. Если вы начинаете на краю, только один сосед находится снаружи, поэтому ваша вероятность смерти равна 0.25. Всюду, все соседи находятся внутри острова, поэтому вероятность смерти за 1 шаг - 0.0.

>>> mpr(prob_death(5, 5)) 
0.806641 0.666016 0.622070 0.666016 0.806641 
0.666016 0.437500 0.349609 0.437500 0.666016 
0.622070 0.349609 0.261719 0.349609 0.622070 
0.666016 0.437500 0.349609 0.437500 0.666016 
0.806641 0.666016 0.622070 0.666016 0.806641 

Вероятность смерти в 5 шагов. Я не могу проверить точные значения, но он выглядит правильно: вероятность смерти наивысшая по углам, немного ниже по краям и неуклонно уменьшается внутрь.

Это решение проблемы умирания менее или равно n шагов.

Теперь, чтобы найти вероятность умереть в точноn шаги: Пусть вероятность умереть в меньше или равна n шагов, начиная от (x,y) обозначим через P(x,y,n). Тогда вероятность угасания ровно n шагов - это вероятность выживания за n-1 шагов, умноженных на вероятность смерти на n-м шаге, учитывая, что мы выжили за n-1 шагов: (1-P(x,y,n-1))*(P(x,y,n) - P(x,y,n-1)). (Я не все, что уверен в этом формуле, поправьте меня, если я ошибаюсь.)

Answer 2

Сначала начните с матрицы с вероятностью находиться в квадрате (x, y) на 0-м шаге. Давайте моделируем его с помощью матрицы 4x4. Если предположить, что парень начинается (1, 2):

After 0 steps: 
    0.00% 0.00% 0.00% 0.00% 
    0.00% 0.00% 100.00% 0.00% 
    0.00% 0.00% 0.00% 0.00% 
    0.00% 0.00% 0.00% 0.00% 
outside: 0.00% 
---- 
After 1 steps: 
    0.00% 0.00% 25.00% 0.00% 
    0.00% 25.00% 0.00% 25.00% 
    0.00% 0.00% 25.00% 0.00% 
    0.00% 0.00% 0.00% 0.00% 
outside: 0.00% 
---- 
After 2 steps: 
    0.00% 12.50% 0.00% 12.50% 
    6.25% 0.00% 25.00% 0.00% 
    0.00% 12.50% 0.00% 12.50% 
    0.00% 0.00% 6.25% 0.00% 
outside: 12.50% 
---- 
After 3 steps: 
    4.69% 0.00% 12.50% 0.00% 
    0.00% 14.06% 0.00% 12.50% 
    4.69% 0.00% 14.06% 0.00% 
    0.00% 4.69% 0.00% 4.69% 
outside: 28.12% 
---- 
After 4 steps: 
    0.00% 7.81% 0.00% 6.25% 
    5.86% 0.00% 13.28% 0.00% 
    0.00% 9.38% 0.00% 7.81% 
    2.34% 0.00% 5.86% 0.00% 
outside: 41.41% 
---- 

Вот питон программа, которая вычисляет это:

class Table: 
    def __init__(self, n, outside=0): 
     self.T = [[0]*n for i in xrange(n)] 
     self.outside = outside 

    def add(self, i, j, value): 
     n = len(self.T) 
     if 0<=i<n and 0<=j<n: 
      self.T[i][j] += value 
     else: 
      self.outside += value 

    def make_next(self): 
     n = len(self.T) 
     Q = Table(n, self.outside) 

     for i in xrange(n): 
      for j in xrange(n): 
       value = self.T[i][j]/4.0 
       Q.add(i-1, j, value) 
       Q.add(i+1, j, value) 
       Q.add(i, j-1, value) 
       Q.add(i, j+1, value) 
     return Q 

    def __repr__(self): 
     return '\n'.join(' '.join(
        '{:6.2f}%'.format(item*100) 
        for item in line) 
        for line in self.T) + \ 
       '\noutside: {}'.format('{:6.2f}%'.format(self.outside*100)) 


N = 4 
T = Table(N) 
T.add(1, 2, 1) 

for k in xrange(N+1): 
    print 'After {} steps:'.format(k) 
    print T 
    print '----' 

    T = T.make_next() 

Answer 3

Это очень сложный и нюансами проблема - я подозреваю, что цель интервьюеров не было слышать, что вы придумали ответ, а скорее посмотрите, как вы подходите к проблеме.

Проблема становится шахматной доской п квадратов на стороне, по-видимому, с случайным размещением куска, который должен двигаться п пространства, двигаясь в направлении, по-видимому случайном кардинального каждый ход. Таким образом, вероятность того, что кусок останется на доске, связана не только с размером доски, но и с размещением куска. Так как любое перемещение на доске также считается выходом из борта, то путь кусок занимает поэтому также релевантный.

Для сетки 2 × 2 кусок имеет 2/7 вероятность пребывания на доске (четыре пути остаются на доске, четырнадцать общих дорожек, независимо от того, какая из четырех возможных стартовых точек).

Для сетки 3 × 3 кусок имеет вероятность наличия на борту 2/11 (16 путей остаются включенными, 88 общих дорожек), если он начинается на углу. Если он начинается со стороны, он имеет вероятность 3/11 (24 пути остаются включенными).Если он начинается в центре, он имеет вероятность 9/22 (36 путей остаются включенными). Поскольку кусок имеет вероятность 4/9, каждый из которых начинается в углу или сбоку, и вероятность 1/9 для начала в центре, его общая вероятность остаться на доске (2/11 + 3/11) × 4/9 + 9/22 × 1/9 = 0,247.

Сетка 4 × 4 будет (очевидно) еще сложнее, но это, пожалуй, стоит отметить, что сетки действительно соответствуют шаблону:

2 × 2:

- - 1 - - 
- 2 - 2 - 
1 - 2 - 1 
- 2 - 2 - 
- - 1 - - 

3 × 3:

- - - 1 - - - 
- - 3 - 3 - - 
- 3 - 9 - 3 - 
1 - 9 - 9 - 1 
- 3 - 9 - 3 - 
- - 3 - 3 - - 
- - - 1 - - - 

я начал на сетке 4 × 4, но нет, спасибо. Стартовый квадрат, кажется, имеет 36 путей, ведущих к нему, и на самом деле их идентификация, ну, утомительна. В каждом случае кусок начинается в центре рисунка, и мы можем рисовать доску по своему усмотрению.

Очевидно, что существует закономерность, и он справедливо кричит, что существует математическая симметрия, но у меня нет времени и терпения, чтобы ее решить. Каждый полюс имеет один путь, у следующей группы конечных точек есть n пути, а следующая группа имеет n Пути. Я подозреваю, что ошибся в подсчете самого внутреннего набора конечных точек для сетки 4 × 4, но если у меня нет, 36 = n (n - 1), что настоятельно предлагает шаблон для кольца.

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

Answer 4

подхода следует полагаться на вероятностной формулы - нет благоприятных случаев/общего числа случае

С учетом координат (х , у) и шагов - п Общего количества пользователей способов могут предпринять шаги -
первого шага - 4 пути второго шага - 4 * 3 (при условии, что он не может уйти в обратном направлении) 3-й шага - 4 * 3^2 .. . .... ... n-й шаг - 4 * 3^(n-1) Прогресс в артемите даст полные шаги.

Фавориты - то есть пересечение границ - рекурсивная функция с рекурсией во всех 4-х направлениях и число переменных incr при пересечении границ матрицы.

Разделите оба, чтобы получить ответ.

Answer 5

Спасибо Anubhav C за отличное решение, которое было очень полезно для освещения проблемы. Я думаю, что использование 0.25 в качестве вероятности (упомянутое выше) может ввести в заблуждение и неверно! Если мы посмотрим на вероятность # dead_cases/# total_possible_moves, результаты будут разными.

Рассмотрим следующий код для нахождения штамповой/уцелевших случаи:

def winLoss_stat(N, steps): 
    newStats = [[[0, 0, 0] for i in range(N)] for j in range(N)] 
    if steps==0: 
     newStats = [[[1, 0, 0] for i in range(N)] for j in range(N)] 
     return newStats 
    oldStats = winLoss_stat(N, steps-1) 
    for i in range(N): 
     for j in range(N): 
      for d in [(0, 1), (0, -1), (1, 0), (-1, 0)]: 
       indX = i + d[0] 
       indY = j + d[1] 
       if indX >=0 and indX < N and indY >= 0 and indY<N: 
        newStats[i][j][0] += oldStats[indX][indY][0] 
        newStats[i][j][1] += oldStats[indX][indY][1] 
        newStats[i][j][2] += oldStats[indX][indY][2] 
       else: 
        newStats[i][j][1] += 1 
        if steps==1: 
         newStats[i][j][2] = 1 
    return newStats 

(or equivalently, for one step (using dfs - recursive): 

class winLoss: 
    def __init__(self, N): 
     self.win = 0 
     self.loss = 0 
     self.N = N 
    def winLoss(self, x, y, n): 
     if x < 0 or y < 0 or x >= self.N or y >= self.N: 
      self.loss += 1 
      return 
     if n == 0: 
      self.win += 1 
      return 
     self.winLoss(x - 1, y, n-1) 
     self.winLoss(x, y - 1, n-1) 
     self.winLoss(x+1, y, n-1) 
     self.winLoss(x, y+1, n-1) 



    wl = winLoss(n) 
    wl.winLoss(i, j, n) 
for any i,j start point and n (size of square) 
) 

The winLoss_stat returns three values for starting point at each square i, j: 
[numbers of survive cases, numbers of die cases before or at k steps, numbers of death exactly at step k] 

The results are as the following for n=4 (4X4), steps=4: 

       0    1    2    3 
0 [58, 24, 12] [93, 34, 18] [93, 34, 18] [58, 24, 12] 
1 [93, 34, 18] [150, 46, 28] [150, 46, 28] [93, 34, 18] 
2 [93, 34, 18] [150, 46, 28] [150, 46, 28] [93, 34, 18] 
3 [58, 24, 12] [93, 34, 18] [93, 34, 18] [58, 24, 12] 

This translates to the following probabilities for 
1. death before or at k steps: 
      0   1   2   3 
0 0.292683 0.267717 0.267717 0.292683 
1 0.267717 0.234694 0.234694 0.267717 
2 0.267717 0.234694 0.234694 0.267717 
3 0.292683 0.267717 0.267717 0.292683 

2. death exactly at k steps: 
      0   1   2   3 
0 0.146341 0.141732 0.141732 0.146341 
1 0.141732 0.142857 0.142857 0.141732 
2 0.141732 0.142857 0.142857 0.141732 
3 0.146341 0.141732 0.141732 0.146341 

The results can be verified by looking at the numbers of win-loss from step 1 to 3 for n=3: 

winLoss_stat(3, 1) 
      0   1   2 
0 [2, 2, 1] [3, 1, 1] [2, 2, 1] 
1 [3, 1, 1] [4, 0, 0] [3, 1, 1] 
2 [2, 2, 1] [3, 1, 1] [2, 2, 1] 

winLoss_stat(3, 2) 
      0   1   2 
0 [6, 4, 2] [8, 5, 2] [6, 4, 2] 
1 [8, 5, 2] [12, 4, 4] [8, 5, 2] 
2 [6, 4, 2] [8, 5, 2] [6, 4, 2] 

winLoss_stat(3, 3) 
      0   1   2 
0 [16, 12, 4] [24, 13, 8] [16, 12, 4] 
1 [24, 13, 8] [32, 20, 8] [24, 13, 8] 
2 [16, 12, 4] [24, 13, 8] [16, 12, 4]