Черепаха и заяц: как поймать цикл, имея память всего на два указателя

Чтобы поймать зацикливание, не нужна таблица посещённых мест — достаточно двух бегунов с разной скоростью на одной дорожке.

Идею приписывают Роберту Флойду; за элегантность её прозвали «алгоритм черепахи и зайца» в честь басни Эзопа.

Задача: есть ли петля

Представьте односвязный список — цепочку узлов, где каждый ссылается на следующий. Обычно она заканчивается «ничем». Но что, если где-то ссылка ведёт назад, образуя петлю? Тогда обход никогда не завершится — вы будете вечно бегать по кругу. Как это обнаружить? Та же задача возникает для последовательностей вида $x_{n+1} = f(x_n)$: рано или поздно значения зацикливаются, и надо найти период.

Наивное решение и его цена

Очевидный путь — запоминать все посещённые узлы в множестве. Дошли до узла, которого ещё не видели, — запомнили; встретили знакомый — значит, цикл. Работает, но требует памяти на каждый узел — $O(n)$. А если узлов миллиарды или это бесконечная последовательность? Памяти не хватит. Флойд показал, как обойтись двумя указателями — $O(1)$ памяти, сколько бы ни было узлов.

Идея: два бегуна, разная скорость

Пускаем по списку двух «бегунов» из одной точки. Черепаха делает один шаг за такт, заяц — два. Если список конечен и без петли, заяц добежит до конца — цикла нет. А если петля есть, заяц в неё войдёт первым и начнёт нарезать круги. Когда черепаха тоже войдёт в петлю, заяц уже там — и с каждым тактом дистанция между ними внутри кольца сокращается ровно на единицу (заяц приближается на 2, черепаха уходит на 1, итог −1). Раз разрыв уменьшается на целое число каждый такт, он неминуемо обнулится: указатели встретятся в одной и той же точке. Встретились — значит, цикл точно есть.

def has_cycle(start, succ):
    slow = fast = start
    while True:
        slow = succ(slow)          # черепаха: 1 шаг
        fast = succ(succ(fast))    # заяц: 2 шага
        if fast is None:           # заяц упёрся в конец — цикла нет
            return False
        if slow == fast:           # встретились внутри петли
            return True

# Последовательность с зацикливанием: f(x) = (x*x + 1) mod 255
def f(x):
    return (x * x + 1) % 255

print(has_cycle(3, f))   # True — рано или поздно зациклится

# Поиск начала цикла (вторая фаза Флойда)
def cycle_start(start, succ):
    slow = succ(start)
    fast = succ(succ(start))
    while slow != fast:            # фаза 1: найти точку встречи
        slow = succ(slow)
        fast = succ(succ(fast))
    slow = start                  # фаза 2: один из начала, шаг в шаг
    while slow != fast:
        slow = succ(slow)
        fast = succ(fast)
    return slow                   # это и есть вход в петлю

print("Цикл начинается в:", cycle_start(0, f))

Бонус: где петля начинается

Флойд придумал и вторую фазу, чтобы найти вход в цикл, а не просто факт его наличия. Магия в числах: пусть до входа в петлю $\mu$ шагов, а длина петли $\lambda$. К моменту встречи черепаха прошла $\mu + k$ шагов внутри петли, заяц — вдвое больше; разность их путей кратна $\lambda$. Из этого следует красивое: если теперь поставить одного бегуна обратно в начало, а другого оставить в точке встречи и двигать обоих по одному шагу, они встретятся ровно во входе в петлю.

$$\text{путь зайца} = 2 \cdot \text{путь черепахи} \;\Rightarrow\; \text{расстояние от старта до входа} \equiv \text{от встречи до входа} \pmod{\lambda}$$

Где это применяют

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

Мораль

Алгоритм Флойда — урок о том, что иногда вместо «запомнить всё» достаточно «двигаться с умом». Два указателя и разные скорости заменяют целую таблицу истории. Это та самая инженерная красота, когда жёсткое ограничение по памяти не ломает задачу, а подсказывает неожиданно изящное решение.