Кольцевой поезд - найти число вагонов.

[sup]

Логика алгоритма довольно проста. Представим себе, что начиная с некоторого момента Вы обнаруживаете совпадение состояния текущих вагонов с началом. Сколько шагов надо пройти, чтобы запустить проверку обратным ходом? Все как в известном мультике "Кот рыболов".
Первый вариант (лиса).
Что толку попусту ходить. Совпало несколько штук и хватит. Идем обратно и проверяем. Такая стратегия хороша в случае случайного распределения 0 и 1. Как вариант, мы сами за собой оставляем случайную последовательность 0 и 1, чтобы не напороться на демона Максвелла.
Однако, сколь мала бы вероятность не была, тем не менее есть шанс, что совпадение случайное. В таком случае Вы понапрасну будете бегать назад, чтобы убедиться - цикла нет. Неприятно.
Второй вариант (волк).
Пусть зацепится понадежнее. Идем в несколько раз больше предполагаемого цикла. Наверняка цикл длинный, что зря назад бегать. И точно. Для длинных циклов мы изрядно экономим на проверках. Но вот беда. Когда цикл был найден, мы слишком долго не могли поверить своему счастью. А в результате затратили слишком много ходов.
Третий вариант (медведь).
Надежный. Идем вперед ровно на длину предполагаемого цикла. Ну что тут скажешь - разумно. Это дает константу 5.
Но вопрос остался: а сколько на самом деле надо пройти?
Вот и оказывается, что компромиссом является не $n$, а $\sqrt 2 n$.

[nikvic]

sup в сообщении #724615 писал(а):

Но вопрос остался: а сколько на самом деле надо пройти?
Вот и оказывается, что компромиссом является не $n$, а $\sqrt 2 n$.

В наихудшем случае это даёт известную длину поиска (TOTAL) и оказывается больше 5.
Для $N=a^{k-1}+1$ надо $1+a^1+a^2+ \cdots + a^k +N.$ шагов. Найдите отношение.

"Волчий" вариант достигает двойки в среднем, если проверочная длина растёт быстрее логарифма.

[sup]

Вы, видимо, решили, что я взял этот корень с потолка?
Можно показать, что константа в худшем случае равна
$2 + \lambda + \frac {2}{\lambda}$
Можете сами убедиться, что для $\lambda =1$ константа равна 5. А оптимум достигается как раз при выборе $\sqrt 2$.
Что касается разговора о среднем - это просто другая задача. Я уже упоминал, что оптимизация среднего и оптимизация худшего варианта - это разные задачи. Впрочем, ничего нового здесь нет. Достаточно вспомнить сортировки HeapSort и QuickSort.

[nikvic]

sup в сообщении #724624 писал(а):

Можно показать, что константа в худшем случае равна
$2 + \lambda + \frac {2}{\lambda}$

Покажите, пожалуйста.
Для варианта, когда чёрт на шаг опережает Вас перед переходом в явно новый вагон.

[sup]

Пусть я на шаге А. Мне известны $n$ вагонов и к этому моменту я затратил $S_n$ ходов. По индукции мы докажем, что $S_n \leqslant C + \theta n$ с некоторой константой $C$ и $\theta > 1$. На асимптотику эта константа никак не влияет.
Далее я ищу 1. Каждый 0 увеличивает как возможную длину цикла так и затраты на 1. Поэтому здесь индукция проходит. Далее. Прямой проход. Мы проверяем $\lambda n$ вагонов. Опять таки, если здесь мы наткнемся на 1, оценка длины и затраты вырастут на одну и ту же величину и опять индукция проходит.
Итак я проверил все $\lambda n$ вагонов. К этому моменту мои затраты выросли до $S_n +\lambda n$. Далее проверка обратным ходом. Если она не пройдет, затраты вырастут до $S_n +\lambda n +2n$, но и само $n$ будет заменено на $n +\lambda n$. Осталось найти $\theta$ из уравнения
$\theta n + \lambda n +2n = \theta (1+ \lambda)n$
Откуда находим
$\theta = (\lambda +2) /\lambda$
Если обратная проверка находит цикл, то в этот момент затраты равны $S_n +\lambda n +n$
Осталось только подставить $\theta$ и получить нужную формулу.

[nikvic]

Буква А используется один раз - она лишняя.
Мне известны n вагонов - где в этот момент Вы находитесь?
Судя по тексту, Ваши "шаги" имеют длину, растущую примерно как геом. прогрессия - пока проверки дают отрицательный результат. Подтвердите либо опровергните.

[Corwin]

Реализовал алгоритм предложенный sup

В худшем случае для $N = 2^{12}$ получил такие результаты:

1:  maxratio = 4,99659, avgratio = 4,37667
1,1:  maxratio = 4,86111, avgratio = 4,70459
1,2:  maxratio = 4,80971, avgratio = 4,69457
1,3:  maxratio = 4,58333, avgratio = 4,21052
1,4:  maxratio = 4,76901, avgratio = 4,57785
1,5:  maxratio = 4,69231, avgratio = 3,94607
1,6:  maxratio = 4,60000, avgratio = 4,09716
1,7:  maxratio = 4,80000, avgratio = 4,23727
1,8:  maxratio = 4,68806, avgratio = 4,33736
1,9:  maxratio = 4,84661, avgratio = 4,45043
1,4142135623731:  maxratio = 4,82570, avgratio = 4,62910

Круглые цифры для 1.6 и 1.7 объясняются тем, что максимум получаем при $N = 5$.

Результаты странные... Возможно, я где-то ошибся с реализацией худшего случая...

В среднем случае получилось для 1.6:

n = 4096: minratio = 3,59985, maxratio = 3,60327, avgratio = 3,60032

p.s. Для $\sqrt{2}$ получаем обещанные $(2 + 2 \sqrt{2})$

[nikvic]

Corwin в сообщении #724694 писал(а):

Реализовал алгоритм предложенный sup

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

[sup]

nikvic
Вы уж простите великодушно, но я несколько раз описывал эту схему. Не хочется в очередной раз повторять все с начала. Буква А относится к последнему такому описанию. Худший вариант действительно развивается по геометрической прогрессии с множителем $1 + \lambda$.
Отсюда, кстати, следует, что не все $N$ равноправны. Те $N$ которые близки к этой прогрессии будут давать оценки более близкие к теоретической. Помимо этого, есть еще и эффекты округления. Я пробовал округлять и вверх и вниз. Результаты получались разные. Насколько это влияет на окончательную оценку я тоже затрудняюсь сказать. Однако думаю, что поправки будут меньшего порядка.

(Оффтоп)

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

[nikvic]

sup в сообщении #724708 писал(а):

nikvic
Худший вариант действительно развивается по геометрической прогрессии с множителем $1 + \lambda$.

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


Для $N=a^{k-1}+1$
надо $1+a^1+a^2+ \cdots + a^k +N.$ шагов.
После суммирования, деления на $N=a^{k-1}+1$ и взятия предела получим простенькую дробь с минимумом для а=2 и значением 5.

[TOTAL]

nikvic в сообщении #724760 писал(а):

sup в сообщении #724708 писал(а):

nikvic
Худший вариант действительно развивается по геометрической прогрессии с множителем $1 + \lambda$.

Именно этот вариант разобрал TOTAL

Нет, не этот, здесь совсем другой алгоритм, для которого делается $1+a^1+a^2+ \cdots + a^{k-1}+(1+\lambda)N}$ шагов при $(2+\lambda)N=a^k$

[Corwin]

Что-то я запутался.
Для "ключевых" точек на каждом шаге алгоритм идёт $(a_{k} - a_{k-1})$ вперёд, затем $a_{k-1}$ назад и, если шаг не последний, то $a_{k-1}$ вперёд.
На последнем шаге $N = a_{k-1}$.

Я ошибаюсь?

[nikvic]

TOTAL в сообщении #724958 писал(а):

nikvic в сообщении #724760 писал(а):

sup в сообщении #724708 писал(а):

nikvic
Худший вариант действительно развивается по геометрической прогрессии с множителем $1 + \lambda$.

Именно этот вариант разобрал TOTAL

Нет, не этот, здесь совсем другой алгоритм, для которого делается $1+a^1+a^2+ \cdots + a^{k-1}+(1+\lambda)N}$ шагов при $(2+\lambda)N=a^k$

Ок. Вы опять способствовали пропихиванию куска через мою длинную шею

-- Пт май 17, 2013 15:06:57 --

Corwin в сообщении #725036 писал(а):

Что-то я запутался.
Для "ключевых" точек на каждом шаге алгоритм идёт $(a_{k} - a_{k-1})$ вперёд, затем $a_{k-1}$ назад и, если шаг не последний, то $a_{k-1}$ вперёд.
На последнем шаге $N = a_{k-1}$.

Я ошибаюсь?

Попробую по-своему.
Обнаружив возможность "перехлёста" в точке 100%, двигаемся к точке 240%. Если перехлёст не опровергнут, идём назад, в 140%. Если перехлёст не подтверждён, снова вперёд, к 240%. Оттуда начинаем новый поиск возможного перехлёста.
======
Но задачка не доделана. Нет нужной нижней оценки для константы...

[TOTAL]

nikvic в сообщении #725046 писал(а):

Но задачка не доделана. Нет нужной нижней оценки для константы...

Если имеется в виду количество шагов при самом большом везении, то уже говорили, чтло надо сделать всего $(2+\lambda)N$ шагов.

[nikvic]

TOTAL в сообщении #725059 писал(а):

nikvic в сообщении #725046 писал(а):

Но задачка не доделана. Нет нужной нижней оценки для константы...

Если имеется в виду количество шагов при самом большом везении, то уже говорили, чтло надо сделать всего $(2+\lambda)N$ шагов.

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