Алгоритм нахождения дыры в бесконечномерном графе

Question

Корова стоит перед бесконечным забором.На другой стороне трава.Корова хочет добраться до этой травы.Где-то вдоль этого забора есть отверстие, через которое корова может попасть на другую сторону.Расстояние d от коровы до ямы связано с распределением вероятности f (d), то есть вероятность того, что яма находится на расстоянии k шагов от коровы, определяется как f (k).Обратите внимание, что мы рассматриваем все расстояния как дискретные, то есть они всегда измеряются с точки зрения шагов, предпринятых коровой. Корова может делать шаги с отрицательным целым числом, а также шаги с положительным целым числом, т.е.Также мы знаем, что ∑ (k = -∞) ^ ∞ | k | ⋅f (k) <∞.Мы хотим описать алгоритм, который может найти дыру с вероятностью 1. </p>

Задача 1 Что является достаточным условием для алгоритма, чтобы найти дыру с вероятностью 1?Задача 2. Опишите такой алгоритм.

Answer 1

Мне кажется, что ваша проблема, как указано, имеет тривиальное решение:

• проверка на наличие дыры в текущем положении
• шаг вперед на 1 шаг, проверка на наличие отверстия
• пройти назад 2 шага, проверить на предмет отверстия
• пройти вперед 3 шага, проверить на наличие отверстия
• пройти назад 4 шага, проверить на наличие отверстия ...

Эта прогулка посетит все относительные целые числа с вероятностью 1. Конечно, вы действительно хотите оптимизировать среднее количество шагов, которое должна сделать корова, что известно как поисковая задача игры .Решение представляет собой одномерную экспоненциальную «спираль»;Вы просто заменяете приведенную выше арифметическую последовательность 1-2-3-4-5 на геометрическую, умножаясь на 2 каждый раз.То есть:

• проверка на наличие отверстия в текущем положении
• шаг вперед на 1 шаг, проверка на отверстие на каждом шаге
• шаг назад на 2 шага, проверка на отверстие накаждый шаг
• идти вперед 4 шага, проверяя наличие дырки на каждом шаге
• идти назад 8 шагов, проверяя дыры на каждом шагу ...

Google for«Проблема коровьего пути», которая является вашим обобщением для перекрестка N-way (у вас есть только два, «левый» и «правый»)

Answer 2

Можете ли вы проверить, находится ли отверстие в заданной позиции? Если так, то кажется, что единственное, что нужно сделать, это проверить позиции в порядке уменьшения вероятности. Вы гарантированно найдете дыру, но это может занять произвольно много времени. (Вы можете гарантировать, что вы найдете дыру в определенном количестве поисков, если и только если f имеет конечную поддержку - то есть, если существует только конечное число k, для которых f (k)> 0). Если число отверстий неизвестно, вы сможете определить, что вы нашли их все, только если f имеет конечную поддержку.

С другой стороны, если вы можете проверить, меньше ли расстояние до отверстия, чем определенная величина, тогда, вероятно, лучшим вариантом будет что-то вроде двоичного поиска, взвешенного CDF для f.

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

Answer 3

findHole(S)
{
  k = 0;
  previous_k = 0;

  current_f = f(k, S);
  if (current_f == 1) return (S);

  previous_f = 0;
  //While the probability of finding a hole increases,
  //we increase k and verify if the vertex at k steps is a hole
  while (current_f >= previous_f)
  {
    previous_f = current_f;
    previous_k = k;

    //As closer to probability 1 we are, as smaller steps we make
    k = (1 - current_f) * MAX_STEP_SIZE;
    current_f = f(k, S);
    if (current_f == 1) return (S);
  }

  //If we overshot our hole and the probability of finding
  //a hole at k steps distance has started to decrease, we
  //perform a binary search within the boundaries of the interval
  //[previous_k, k], with probabilities in [previous_f, current_f],
  //having a guarantee that our hole is within this interval
  return binSearch(previous_k, k, S);
}

Answer 4

Создайте выстрел из пули, поместите промежуточные стены переменного размера между ними и посмотрите, по какой стене не стреляют. иди оттуда. Вы должны знать, как построить график функции дырок (возможно, подойдет приближение, но не к бесконечной дыре).