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

Question

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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);
}