Алгоритм обнаружения цикла - PullRequest
Новая
       13

Алгоритм обнаружения цикла

0 голосов
/ 18 июня 2011

Скажем, у меня есть функция f: 

f(0) = 0
f(i) = (i - 1) % 4

f (0..12): 

0 0 1 2 3 0 1 2 3 0 1 2 3

Я хочу найти начало цикла и длину цикла, которые1 и 4 соответственно.Алгоритм черепахи и зайца работает с итеративными функциями, но у меня нет итеративной функции.Существуют ли другие алгоритмы, которые работают с не повторяющимися функциями, или алгоритм черепахи и зайца может быть изменен для этого?

Редактировать:

Используя ответ Джейсона С, мне удалось придумать это,который, кажется, работает: 

public static Tuple<int, int> ModifiedTortoiseHare(Func<int, int> f, int x0 = 0, int checks = 4)
{
    for (; ; x0++)
    {
        int lam = 0, tortoise, hare;

        do
        {
            lam++;
            tortoise = f(x0 + lam);
            hare = f(x0 + 2 * lam);
        } while (tortoise != hare);

        int mu = -1;

        do
        {
            mu++;
            tortoise = f(x0 + mu);
            hare = f(x0 + mu + lam);
        } while (tortoise != hare);

        if (mu != 0) continue;

        bool correct = true;
        int lamCheckMax = lam * checks;

        for (int x = 0; x < lamCheckMax; x++)
        {
            if (f(x0 + x + mu) != f(x0 + x + mu + lam))
            {
                correct = false;
                if (mu != 0) x0 += mu - 1;
                break;
            }
        }

        if (correct) return Tuple.Create(x0 + mu, lam);
    }
}

Ответы [ 2 ]

7 голосов
/ 18 июня 2011

Если функция является «черным ящиком», и у вас есть возможность найти f (x) для любого отдельного x (допустимо ли для действительных чисел или только целых чисел), но вы ничего не знаете, есть нет общего способа найти начало и длину цикла. Например, рассмотрим функцию 

f(k) = (k - 1) % 4 + g(k)
g(k) = max(0, k-1000000)

тогда f (k) выглядит так, как будто оно повторяется каждые 4 целых числа, но затем, когда вы достигаете k = 1000000, шаблон останавливается.

Если функция имеет конечный диапазон, и вы можете проверить все целые числа, алгоритм черепахи / зайца (= алгоритм Флойда для нахождения цикла ) может помочь.

Вместо того, чтобы повторять оценку функции, вычислите f (k0 + k) и f (k0 + 2 * k), пока они не совпадут, и в этот момент предполагаемый период равен k, и вам просто нужно повторить все значения, чтобы убедиться, что цикл продолжается.

Ваш вопрос, по-видимому, эквивалентен «Как найти повторяющиеся последовательности слов?» , в котором есть несколько ответов.

0 голосов
/ 18 июня 2011

для fn, который вы указали с момента его деления на 4, длина равна четырем, и, поскольку к нему нет добавленной стоимости, 0 фактически является началом цикла, а не 1. Вы действительно можете наблюдать это, если реализуете его, используяграфик, как было указано.Так как это значения fn, вы можете вместо этого использовать связанный список, и для каждого значения, которое возвращает fn, добавьте его в список, если его там еще нет, иначе вы можете иметь цикл. Предполагая, что существует только 1 цикл.

...