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

[nikvic]

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

А если использовать "монетку" - на каждом шаге случайным образом добавлять от 0 до 4х вагонов, то плохой случай из области "неудачный поезд" переместиться в область "глобальное невезение"

Я использую её иначе, окрашивая новые участки на линейном протоколе с помощью монетки.
Сравнивается его дальний кусок с только что пройденными "цветами" вагонов, доля длины куска в длине протокола уменьшается с ростом протокола - отсюда и двойка в пределе.

[TOTAL]

(Оффтоп)

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

Я написал программу, которая вычисляет длину поезда. Изначально свет в вагонах горит случайным образом.
Использую алгоритм, описанный выше: шаги (проходы) увеличивающейся длины туда-обратно с проверкой света в ранее пройденных вагонах.

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

[Corwin]

(Оффтоп)

Ключевая строка программы:

1. if(res != n) throw new ApplicationException() 

Никакая формула не заменит маленького человечека, топающего туда-сюда по поезду :).

[sup]

Я провел тестирование по следующей схеме.
Выбирается длина поезда. Проводится 1000 экспериментов.
В каждом эксперименте в вагонах с вероятностью 0.5 (независимо друг от друга) устанавливается либо 0 либо 1.
Алгоритм стартует с комбинации 1 0 (чтобы не связываться с "балластом" входа в общую схему)
Далее набирается статистика и вычисляется выборочное среднее и выборочная сигма.
Как и ожидалось, для решения требуется в среднем $(2+\sqrt 2)n$ ходов.
Вот результаты (огрубленные)
Длина Решение Сигма
10 33.6 2.47
50 170 2.89
100 340.9 2.84
1000 3414 2.83
10000 34142 2.71
Для "худшего" случая тоже имеется некая информация. Для тех же длин результаты оказались лучше $(2+2\sqrt 2)n$. Причем константа зависит от округления вверх или вниз. Но это все не очень показательно, поскольку для длин близких к степеням $(1+\sqrt 2)$ может что-то и изменится. Я не изучал.

[nikvic]

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

Если в последних m новых вагонах свет горит так же, как в первых m уже посещённых вагонах, значит возможен цикл. Чтобы не ухудшать асимптотику, m должно быть равно количеству вагонов, пройденных на предыдущем шаге. Точнее, что не меньше, это очевидно, а что не больше - это всего лишь моё предположение.

Давайте условимся о терминах.
Предлагаю 2 протокола - бинарные слова, Новый цвет и Старый цвет. И положение - номер буквы-вагона, в котором мы находимся. Ну и состояние - протокол+положение.

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

[Corwin]

Цитата:

откуда взялась требуемая Вами пропорциональность m и ожидаемой длины поезда

На каждом (почти на каждом) шаге длина исследованной части поезда должна увеличиваться как минимум в 2 раза. Иначе в худшем случае получим асимптотику хуже (больше), чем 5N.

-- 16.05.2013, 12:15 --

sup
Вот результаты работы моей программы (по 10000 запусков на случайных массивах для каждого n).

n = 4090: minratio = 2,00367, maxratio = 4,00147, avgratio = 2,16142
n = 4091: minratio = 2,00342, maxratio = 4,00049, avgratio = 2,16061
n = 4092: minratio = 2,00318, maxratio = 4,00244, avgratio = 2,15900
n = 4093: minratio = 2,00342, maxratio = 3,99756, avgratio = 2,15597
n = 4094: minratio = 2,00342, maxratio = 3,99609, avgratio = 2,16520
n = 4095: minratio = 2,00366, maxratio = 3,99756, avgratio = 2,16259
n = 4096: minratio = 2,00391, maxratio = 3,99976, avgratio = 2,16357
n = 4097: minratio = 2,00391, maxratio = 4,00195, avgratio = 2,16276
n = 4098: minratio = 2,00366, maxratio = 4,00122, avgratio = 2,16220
n = 4099: minratio = 2,00342, maxratio = 3,99927, avgratio = 2,15714
n = 4100: minratio = 2,00390, maxratio = 3,99805, avgratio = 2,16386

В среднем получается $2.16 \cdot N$
Ну 110 тыс запусков - это слишком мало, чтобы "поймать" худший случай $5 \cdot N$.

p.s. ratio - коэффициент при N
min, max, avg - минимальное, максимальное и среднее значение в данной серии попыток

[nikvic]

Ну, вот, имеем среднее около 2.16, т.е. добавка к двойке на порядок меньше корня из двух.
Насколько я понимаю, программа "вписывается" в следующую схему. Берётся растущая функция m(L), и исследованная часть наращивается, пока там не наблюдается кусок длины m, совпадающий с противоположным концом старого проткола.
Верно ли я понимаю?
Если "да", то что за m(L)?

[sup]

Corwin
Я гонял алгоритм с $\lambda = \sqrt 2$.
Этот алгоритм вроде как оптимизирует именно худший случай. Теоретическая оценка для него $(2 + 2\sqrt 2) n$. На случайных данных он дает очень даже понятный результат $(2 + \sqrt 2) n$. Что, конечно, совсем не оптимум.
Если ориентироваться на среднее время для случайных данных, то надо применять рандомизированный вариант. Вы, наверное, так и делали.
Судя по всему, в данном случае алгоритмы, оптимизирующие среднее время и худшее время, должны различаться.

[nikvic]

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

Я гонял алгоритм с $\lambda = \sqrt 2$.
Этот алгоритм вроде как оптимизирует именно худший случай. Теоретическая оценка для него $(2 + 2\sqrt 2) n$.

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

[Corwin]

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

Ну, вот, имеем среднее около 2.16, т.е. добавка к двойке на порядок меньше корня из двух.
Насколько я понимаю, программа "вписывается" в следующую схему. Берётся растущая функция m(L), и исследованная часть наращивается, пока там не наблюдается кусок длины m, совпадающий с противоположным концом старого проткола.
Верно ли я понимаю?
Если "да", то что за m(L)?

Пусть на предыдущем шаге мы прошли $m$ вагонов. Для удобства мы покрасили их в один цвет.
Текущий шаг состоит из двух частей:
1. Проходим те же m вагонов в обратном направлении, проверяя их окраску (если изменилась - найден цикл) и перекрашивая в другой цвет.
2. Идём вперёд, пока не обнаружим идущие подряд m вагонов, окрашенных точно так же, как вагоны в пункте 1 (то есть, окрашенных одинаково и в правильный цвет).

Поэтому общая длина текущего шага будет не менее $2m$ и не более $N + m$. В случае максимальной длины текущий шаг будет предпоследним.

[nikvic]

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

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

Ну, вот, имеем среднее около 2.16, т.е. добавка к двойке на порядок меньше корня из двух.
Насколько я понимаю, программа "вписывается" в следующую схему. Берётся растущая функция m(L), и исследованная часть наращивается, пока там не наблюдается кусок длины m, совпадающий с противоположным концом старого проткола.
Верно ли я понимаю?
Если "да", то что за m(L)?

Пусть на предыдущем шаге мы прошли $m$ вагонов. Для удобства мы покрасили их в один цвет.
Текущий шаг состоит из двух частей:
1. Проходим те же m вагонов в обратном направлении, проверяя их окраску (если изменилась - найден цикл) и перекрашивая в другой цвет.
2. Идём вперёд, пока не обнаружим идущие подряд m вагонов, окрашенных точно так же, как вагоны в пункте 1 (то есть, окрашенных одинаково и в правильный цвет).

Поэтому общая длина текущего шага будет не менее $2m$ и не более $N + m$. В случае максимальной длины текущий шаг будет предпоследним. Вероятность того, что длина будет максимальной, предположительно (приблизительно) равна $1 - \frac{N}{2^m}$.

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

[sup]

nikvic
Алгоритм такой. Сначала каким-то образом убеждаемся, что вагонов не меньше двух, в первом вагоне выставляем 1, а во втором 0. Полагаем $n=2$ - возможная длина цикла.
Дальше действуем индуктивным образом.

шаг А.
1.У нас за спиной $n$ вагонов. В первом выставлена 1, а во всех остальных 0.
Поиск 1.
В цикле идем вперед. Если встретился 0 - увеличиваем $n=n+1$. В противном случае 1 найдена - выходим из этого цикла. В этот момент $n$ - возможная длина цикла. Меньшие длины невозможны.

шагБ.
Гасим эту 1-ку. Если мы действительно нашли цикл и $n$ - длина поезда, то теперь во всем поезде света нет.
Прямой проход
Идем вперед $\lambda n - 1$ вагонов. Если наткнулись на 1, то цикл все еще не найден. Поправляем надлежащим образом $n$ и снова идем в шагБ (найдена 1).

Обратный проход. Итак, в общей сложности мы прошли по $m = n + \lambda n$ вагонам. Нам известно, что длина поезда либо $n$ либо не меньше чем $m$. Проверяем первый вариант. Выставляем 1 и идем на $n$ шагов назад. Если там обнаруживается 1, то цикл найден. В противном случае возвращаемся в позицию $m$, вырубаем 1, полагаем $n=m$ и идем в шагА.

[nikvic]

Обычно удобнее построить свой алгоритм, чем разбираться в тонкостях чужого.
"Проверка" всегда происходит при движении "назад" по освоенной части - ищется изменение цвета, которое не должно произойти, если поезд бесконечен.
Когда освоенная часть закончилась, Вы предлагаете продолжить движение в "проверочном" направлении, ограничив удлиннение освоенной части в определённое число раз ("лямбда").
Какой в этом смысл, если достоверно, что перехлёста пока не может быть?
Для для такой уверенности достаточно менять цвет, попадая в вагон, который может быть новым.
Представьте, что до длины поезда ещё пока очень далеко...

[Corwin]

У меня возник вопрос: если бы в каждом вагоне было два выключателя (а не один), позволило бы найти алгоритм с лучшей асимптотикой (в худшем случае)?

[nikvic]

Да хоть тысяча. Всё равно удостовериться можно только после прохождения поезда дважды.