Java: Как найти дыру в одномерном графе?

Question

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

Проблема:

Человек стоит перед стеной бесконечной длины.На другой стороне стены находится город, в который он пытается попасть.Где-то в стене есть ворота, и парень может пойти налево или направо, чтобы найти их.

Мне нужно написать алгоритм с линейным временем выполнения, и я просто не в состоянии понять это ... Любая помощь очень ценится!

Answer 1

Он должен попробовать обе стороны.Тем не менее, если он просто пойдет по новой длине в каждом направлении, это станет проблемой "Schlemiel the Painter".Ему нужно увеличить новую длину, по которой он ходит в каждом направлении, в геометрической прогрессии, чтобы амортизированное время поиска стало линейным.Вам нужно будет проработать детали и то, как они переводятся в формулы сложности.

Answer 2

Не уверен, как намекнуть на ответ, просто не отдав его.

Вы знаете, что вы не можете идти "бесконечно налево", тогда, если это не удастся, идите направо, пока не найдете дверь.Это не так.

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

Тогда возникает вопрос: можете ли вы придумать способ увеличить размер «битов», чтобы общее время выполнения, то есть сумма всех «бит», было достаточно, чтобынайти дверь, является линейной?

Вы уже сказали в комментарии, что если вы увеличиваете каждый раз на 1, то сложность слишком высокая (O (n ^ 2) на самом деле, не экспоненциальная, но все жеслишком большой).Так что ищите лучший прогресс, который приведет к меньшему общему увеличению и уменьшению.

Answer 3

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

Также посмотрите на ответы на этот вопрос

Answer 4

Если человек идет поочередно влево и вправо, с увеличивающимися интервалами, он в конце концов поразит ворота. Но я не знаю, соответствует ли это «линейному времени выполнения».

Вот пример того, что я имею в виду:

1. he goes 1 km left
2. he goes 2 km right, being 1 km right of where he started
3. he goes 3 km left, being 2 km left of where he started
4. he goes 4 km right, being 2 km right of where he started
5. he goes 6 km left, being 4 km left of where he started
6. he goes 8 km right, being 4 km right of where he started

Это моя идея для алгоритма, но я уверен, что возможны многие оптимизации.

Answer 5

Как и положено, это невозможно, потому что, если он пойдет не так, он потратит бесконечное количество времени на поиск. Если он может телепортироваться, это легко - через каждые N метров он может телепортироваться на другую сторону своей начальной точки, искать N метров, затем телепортироваться назад и повторять. Это становится линейным поиском.