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

[vorvalm]

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

Когда останавливаться?

Пока не упремся в начальную комбинацию.
Corwin
Я с вами свиней не пас.

[Legioner93]

vorvalm в сообщении #723738 писал(а):

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

Когда останавливаться?

Пока не упремся в начальную комбинацию.

Как мы узнаем, что это те же самые вагоны, а не точно такие же?

Есть только один способ это узнать. Поменять свет, пойти назад и смотреть на изменение цвета в других вагонах. Без возвращения назад обойтись нельзя.

Это первый наивный алгоритм, который я придумал почти сразу, начав решать задачу. Звучал он примерно так "идём вправо, как только встречаем $n$-кратное повторение какой-то комбинации, меняем свет и идём назад, наблюдая за изменением цвета в других вагонах" + некоторые оптимизации.

К сожалению, этот алгоритм не даёт даже времени $O(N)$ в худших случаях.

[vorvalm]

Legioner93 в сообщении #723744 писал(а):

Как мы узнаем, что это те же самые вагоны, а не точно такие же?

Как только по пути нашего алгоритма попадется комбинация $1,0,1,0...$, делаем остановку.
Фиксируем пройденное число вагонов и этап нашего алгоритма. Затем идем дольше, проверяя, насколько
далеко распространяется найденная комбинация, т.е не является ли это началом нашего движения.
Если мы обнаружим, что наш алгоритм нарушается, то снова фиксируем пройденное число вагонов и
возвращаемся к месту, где мы первый раз остановились и начинаем продолжать прерванный алгоритм
до тех пор , пока не встретим новую комбинацию $1,0,1,0...$.
Далее все повторяется до упора.

[nikvic]

vorvalm в сообщении #723773 писал(а):

Legioner93 в сообщении #723744 писал(а):

Как мы узнаем, что это те же самые вагоны, а не точно такие же?

Как только по пути нашего алгоритма попадется комбинация $1,0,1,0...$, делаем остановку.
Фиксируем пройденное число вагонов и этап нашего алгоритма. Затем идем дольше, проверяя, насколько
далеко распространяется найденная комбинация, т.е не является ли это началом нашего движения.
Если мы обнаружим, что наш алгоритм нарушается, то снова фиксируем пройденное число вагонов и
возвращаемся к месту, где мы первый раз остановились и начинаем продолжать прерванный алгоритм
до тех пор , пока не встретим новую комбинацию $1,0,1,0...$.
Далее все повторяется до упора.

Как в этом процессе появляется отрезок длины более N, проходимый туда-сюда (без этого возможна ошибка)?

[sup]

2 vorvalm
Без обратного движения найти длину поезда невозможно.
Пусть Ваш алгоритм просматривает вагоны только вперед и как-то выставляет свет в пройденных вагонах. В какой то момент он (алгоритм) должен остановиться и заявить: длина поезда равна стольки-то. К этому моменту он просмотрел $N$ вагонов и все, что он знает, это какой свет был в этих вагонах. Однако, что мешает поезду быть длиннее чем $N$ и иметь в первых $N$ вагонах какое угодно освещение? (в том числе и то, на основании которого Ваш алгоритм и сделал свое заключение).

[vorvalm]

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

[Corwin]

vorvalm в сообщении #723738 писал(а):

Corwin
Я с вами свиней не пас.

Извините.

На большинстве форумов принято обращаться друг к другу на "ты". Сейчас перечитал правила форума и (с большим трудом) нашёл, что на этом форуме принято обращаться на "Вы".

[Corwin]

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

Вроде бы константу можно улучшить до $2 + 2\sqrt {2}$.
В изложенных алгоритмах никак не учитывался свет в вагоне при "прямом" проходе. Типичный ход - идем вперед $n$ шагов и выключаем свет. Идем обратно $2n$ шагов. Если свет выключен, то включаем, в противном случае найден цикл.
Однако, если во всех вагонах где я побывал свет горит, а я попал в вагон без света, то цикл гарантированно длиннее. Идея и заключается в том, чтобы оставлять за собой определенную комбинацию освещения так, чтобы в некоторых случаях можно было бы сразу отбросить вариант зацикливания.

Каким образом учёт света при "прямом" проходе может повлиять на количество шагов в худшем случае? Свет может гореть таким образом, что ветка "цикл гарантированно длиннее" ни разу не сработает.

[sup]

Учет света в вагонах позволяет контролировать возможную длину поезда: какая длина поезда возможна, а какая нет. Выигрыш возникает лишь при $\lambda > 1$. При меньших значениях данный учет ничего не дает.
В предложенном алгоритме проверяется гипотеза $L = n$. И, если она провалилась, сразу же заключаем, что $L > m-2$. Вот в этом и дело. Мы можем не проверять $L = n + 1$, $L = n + 2$ и тд. В частности, не проверяется $L = 2n$. В результате меньше проверок. Корень возникает как компромисс. Как только возникает подозрение на зацикливание, не стоит затягивать с проверкой обратным ходом. (Иначе возникает риск пустопорожней ходьбы). С другой стороны, если цикла нет, то стоит повременить с проверкой, поскольку она "отъедает" много ходов.

(Оффтоп)

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

[TOTAL]

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

В предложенном алгоритме проверяется гипотеза $L = n$. И, если она провалилась, сразу же заключаем, что $L > m-2$. Вот в этом и дело. Мы можем не проверять $L = n + 1$, $L = n + 2$ и тд. В частности, не проверяется $L = 2n$. В результате меньше проверок. Корень возникает как компромисс. Как только возникает подозрение на зацикливание, не стоит затягивать с проверкой обратным ходом. (Иначе возникает риск пустопорожней ходьбы). С другой стороны, если цикла нет, то стоит повременить с проверкой, поскольку она "отъедает" много ходов.

Проверил бы кто-нибудь расчетами. Такое впечатление, что дойти до $n+\lambda n$ вагона, не отвергая гипотезу про $n$ вагонов в поезде, не так-то легко, т.е. само $n$ будет много раз увеличиваться. Таким образом, "к.п.д." будет существенно лучше (меньше), чем $5n.$

[nikvic]

TOTAL, а как насчёт май 14, 2013 13:19:12?
Нет резону говорить о вероятности, не введя её явно.

[Corwin]

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

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

Идя в одну сторону, включаем свет во всех вагонах, идя в другую - выключаем. Конечно, можно было бы менять свет только в точках разворота, но тогда бы пришлось запоминать состояние света во всех посещённых вагонах. Проще переключить.

По умолчанию длина шага растёт $x(n) = 2 \cdot x(n-1)$, но можно задать другую прогрессию.
Например, можно "отжать" логарифм N (точнее $4 \cdot \log(2N+6)$), используя $x(n) = 2 \cdot x(n-1) + 4$, но на асимптотику это не влияет.

При первом ("прямом") проходе по вагонам используется оптимизация, но её можно отключить, передав false в конструктор класса. В худшем случае асимптотика остаётся той же (5N), но в среднем при росте N результат приближается к оптимальным 2N. Слишком мала вероятность "ложной тревоги".
Смысл оптимизации - если свет в новом вагоне горит правильно, то мы задумываемся "может ли быть так, что это мы сами его включили".
Реализация оптимизации - добавление одной строки в код.

Test1, Test2, Test3 - методы для тестирования разных аспектов поведения алгоритма. Они же - примеры использования класса.

Проще всего запустить программу с помощью LinqPad (http://en.wikipedia.org/wiki/LINQPad).

Используется синтаксис C#

void Main()
{
//      Test1(12345, true);
//      Test2(1024*8+1);
//      Test3(12345, new Func<int, int>[]{ x => 2*x, x => 2*x + 4, x => 2*x + 5, x => (int)Math.Round(1.98*x), x => (int)Math.Round(2.02*x) }, false);
}

// проверяем для всех n от 1 до nmax включительно
private void Test1(int nmax, bool optimize = true, bool print = false)
{
        var train = new CycleTrain(nmax, optimize);
        decimal maxratio = 0, avgratio = 0;
        for(int n = 1; n <= nmax; n++)
        {
                var res = train.CountLength(n);
                if(res != n) throw new ApplicationException(string.Format("n = {0}, res = {1}, count = {2}", n, res, train.Count));
                var ratio = (decimal)train.Count/n;
                avgratio += ratio;
                if(ratio > maxratio)
                {
                        if(print) Console.WriteLine("n = {0}, res = {1}, count = {2}, ratio = {3:0.00}", n, res, train.Count, ratio);
                        maxratio = ratio;
                }
        }
        avgratio /= nmax;
        Console.WriteLine("maxratio = {0:0.00000}, avgratio = {1:0.00000}", maxratio, avgratio);        
}

// проверяем cnt раз для заданного n
private void Test2(int n, int cnt = 10000)
{
        var train = new CycleTrain(n);
        decimal maxratio = 0, minratio = 8*n, avgratio = 0;
        for(int i = 1; i <= cnt; i++)
        {
                var res = train.CountLength(n);
                if(res != n) throw new ApplicationException(string.Format("n = {0}, res = {1}, count = {2}", n, res, train.Count));
                var ratio = (decimal)train.Count/n;
                avgratio += ratio;
                if(ratio > maxratio) maxratio = ratio;
                if(ratio < minratio) minratio = ratio;
        }
        avgratio /= cnt;
        Console.WriteLine("minratio = {0:0.00000}, maxratio = {1:0.00000}, avgratio = {2:0.00000}", minratio, maxratio, avgratio);      
}

// проверяем с различными прогрессиями для длины шага
private void Test3(int nmax, IEnumerable<Func<int, int>> funcs, bool print = false)
{
        var train = new CycleTrain(nmax, false);
        foreach(var func in funcs)
        {
                decimal maxratio = 0, avgratio = 0;
                for(int n = 1; n <= nmax; n++)
                {
                        var res = train.CountLength(n, func);
                        if(res != n) throw new ApplicationException(string.Format("n = {0}, res = {1}, count = {2}", n, res, train.Count));
                        var ratio = (decimal)train.Count/n;
                        avgratio += ratio;
                        if(ratio > maxratio)
                        {
                                if(print) Console.WriteLine("n = {0}, res = {1}, count = {2}, ratio = {3:0.00}", n, res, train.Count, ratio);
                                maxratio = ratio;
                        }
                }
                avgratio /= nmax;
                Console.WriteLine("maxratio = {0:0.00000}, avgratio = {1:0.00000}", maxratio, avgratio);        
        }
}


public class CycleTrain
{
        private const int defaultCapacity = 10000;
        private readonly Random rnd = new Random();
        private bool[] tt; // train lights
        private int tn;    // train length 
        private int ti;    // current position
        private bool optimize;
        
        public int Count { get; private set; }
        
        public CycleTrain(int capacity = defaultCapacity, bool opt = true)
        {
                tt = new bool[capacity];
                optimize = opt;
        }
        
        public int CountLength(int n)
        {
                return CountLength(n, NextStepLength);
        }
        
        public int CountLength(int n, Func<int, int> nextLen)
        {
                Init(n);
                bool state = true, left = false;
                for(int m = 1, mlast = 0;; state = !state, left = !left, mlast = m, m = nextLen(m))
                {
                        var res = Step(mlast, ref m, state, left);
                        if(res > 0) return res;
                }
        }
        
        private static int NextStepLength(int m) { return 2*m; }
        
        private int Step(int mlast, ref int mcur, bool state, bool left)
        {
                
                for(int i = 1; i <= mlast; i++)
                {
                        tt[ti] = state;
                        Move(left);
                        if(tt[ti] == state) return i;
                }
                for(int i = mlast+1; i <= mcur; i++)
                {
                        tt[ti] = state;
                        Move(left);
                        if(optimize && tt[ti] != state) mcur = i + mlast;
                }
                return 0;
        }
        
        private void Init(int size)
        {
                if(tt.Length < size) tt = new bool[tt.Length*2];
                tn = size;
                ti = 0;
                Count = 0;
                for(int i = 0; i < tn; i++) tt[i] = rnd.Next(2) == 1;
        }
        
        private void Left()
        {
                if(ti == 0) ti = tn;
                ti--;
                Count++;
        }
        
        private void Right()
        {
                ti++;
                if(ti == tn) ti = 0;
                Count++;
        }
        
        private void Move(bool left)
        {
                if(left) Left(); else Right();
        }

}

[sup]

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

[проверил бы кто-нибудь расчетами. Такое впечатление, что дойти до $n+\lambda n$ вагона, не отвергая гипотезу про $n$ вагонов в поезде, не так-то легко, т.е. само $n$ будет много раз увеличиваться. Таким образом, "к.п.д." будет существенно лучше (меньше), чем $5n.$

Да зарядить-то компьютер можно. Не очень ясно, как проверять. Для случайного набора нулей и единиц длинный повтор практически исключен. И "бесполезные" проверки включаться вообще не будут. Поэтому можно ожидать, что в этом случае константа будет вообще $(2 +\sqrt 2 )n$. (Это лишь главная часть. Разумеется, там еще есть и "малая" добавка).
Как я уже упоминал алгоритм можно упростить, а именно свет горит только в 1 вагоне,а во всех остальных - погашен. Ясно, что подозрение на цикл возникает лишь когда мы заходим в вагон с 1-й. Это вполне может быть тот самый 1-й вагон и мы нашли цикл. Если так, то после того, как мы погасим свет, во всем поезде света нет, и сколько бы мы не шли вперед мы будем видеть только 0. Но если мы таки найдем 1, это и будет означать, что цикла не было, в первом вагоне горит свет, и все повторяется. Рано или поздно, но цикл будет найден. После этого единиц в поезде просто не будет и мы пройдем все свои $\lambda n$ шагов.
Сколько будет таких итераций? Каждая проверка обратным ходом в $1 + \lambda$ раз увеличивает возможную длину цикла. Значит таких проверок будет логарифмическое количество (от искомой длины). Корень подкидывает ошибку не более 1. Можно ожидать, что поправка будет что-то типа логарифм в квадрате. Ну в крайнем случае степень логарифма. Маловероятно, что ошибка будет больше.

[nikvic]

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

Слишком мала вероятность "ложной тревоги".

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

[Corwin]

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

А если использовать "монетку" - на каждом шаге случайным образом добавлять от 0 до 4х вагонов, то плохой случай из области "неудачный поезд" переместиться в область "глобальное невезение" ($\frac1_{5^k}$).

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

-- 15.05.2013, 16:49 --

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

Как я уже упоминал алгоритм можно упростить, а именно свет горит только в 1 вагоне,а во всех остальных - погашен.

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