В информатике нахождение цикла — это алгоритмическая задача поиска цикла в последовательности значений итеративной функции[en].
Для любой функции функции f, отображающей конечное множество S в себя и для любого начального значения x0 из S последовательность итеративных значений функции
должна, в конечном счёте, использовать одно значение дважды — должна существовать такая пара индексов i и j, что xi = xj. Как только это случится, последовательность должна продолжаться периодически[en], повторяя ту же самую последовательность значений от xi до xj − 1. Нахождение цикла — это задача поиска i и j при заданной функции f и начальном значении x0.
Известно несколько алгоритмов поиска цикла быстро и при малой памяти. Алгоритм «черепахи и зайца» Флойда передвигает два указателя с различной скоростью через последовательность значений, пока не получит одинаковые значения. Другой алгоритм, алгоритм Брента, основан на идее экспоненциального поиска[en]. Оба алгоритма, Флойда и Брента, используют только фиксированное число ячеек памяти и число вычислений функции пропорционально расстоянию от стартовой точки до первой точки повторения. Некоторые другие алгоритмы используют большее количество памяти, чтобы получить меньшее число вычислений значений функции.
Задача нахождения цикла используется для проверки качества генераторов псевдослучайных чисел и криптографических хеш-функций, в алгоритмах вычислительной теории чисел[en], для определения бесконечных циклов в компьютерных программах и периодических конфигураций клеточных автоматов, а также для автоматического анализа формы[en] связных списков.
Рисунок показывает функцию f, отображающую множество S = {0,1,2,3,4,5,6,7,8} на себя. Если начать с точки x0 = 2 и повторять применение функции f к получаемым значениям, увидим последовательность значений
Цикл в этой последовательности значений — 6, 3, 1.
Пусть S — конечное множество, f — некая функция на S в то же множество, а x0 — любой элемент из S. Для любого i > 0 пусть xi = f(xi − 1). Пусть μ — наименьший индекс, для которого значение xμ повторяется бесконечное число раз в последовательности значений xi, и пусть λ (длина цикла) — наименьшее положительное целое число, такое, что xμ = xλ + μ. Задача нахождения цикла — это задача поиска λ и μ[1].
Можно рассматривать эту задачу как задачу теории графов, если построить функциональный граф (то есть ориентированный граф, в котором каждая вершина имеет единственную исходящую дугу), вершины которого являются элементами множества S, а рёбра соответствуют отображению элементов в соответствующие значения функции, как показано на рисунке. Множество вершин, достижимых[en] из стартовой вершины x0 образуют подграф в форме, похожем на греческую букву ро (ρ) — путь длины μ от x0 до цикла из λ вершин[2].
Обычно f не задаётся в виде таблицы значений, как показано на рисунке выше. Скорее алгоритм определения цикла может получить либо последовательность значений xi, либо подпрограмму вычисления f. Задача состоит в нахождении λ и μ с проверкой малого числа значений последовательности, либо с обращением к процедуре вычисления значения как можно меньшее число раз. Обычно важна также ёмкостная сложность[en] алгоритма задачи нахождения цикла — желательно использовать память, значительно меньшую по сравнению с размером последовательности целиком.
В некоторых приложениях, и, в частности, в ро-алгоритме Полларда для факторизации целых чисел, алгоритм имеет очень ограниченный доступ к S и f. В ро-алгоритме Полларда, например, S — это множество сравнимых по неизвестному простому множителю числа, который следует разложить на множители, так что даже размер множества S для алгоритма неизвестен. Чтобы алгоритм нахождения цикла работал в таких стеснённых условиях, он должен разрабатываться, основываясь на следующих возможностях. Первоначально алгоритм имеет в памяти объект, представляющий указатель на начальное значение x0. На любом шаге алгоритм может осуществлять одну из трёх действий: он может копировать любой указатель в любой другой объект памяти, он может вычислить значение f и заменить любой указатель на указатель на вновь образованный объект из последовательности, или использовать процедуру проверки совпадения значений, на которые указывают два указателя. Тест проверки равенства может повлечь некоторые нетривиальные вычисления. Например, в ро-алгоритме Полларда этот тест проверяет, не имеет ли разность двух запомненных значений нетривиальный наибольший общий делитель с разлагаемым на множители числом [2]. В этом контексте, по аналогии с моделью вычисления машины указателей[en], алгоритм, использующий только копирование указателей, передвижение в последовательности и тест на равенство, можно назвать алгоритмом указaтелей.
Если вход задан как подпрограмма вычисления f, задачу нахождения цикла можно тривиально решить, сделав только λ + μ вызовов функции просто путём вычисления последовательности значений xi и использования структуры данных, такой как хеш-таблица, для запоминания этих значений и теста, что каждое последующее значение ещё не запомнено. Однако ёмкостная сложность этого алгоритма пропорциональна λ + μ, и эта сложность излишне велика. Кроме того, чтобы использовать этот метод для алгоритма указателей, потребуется использовать тест равенства каждой пары значений, что приведёт к квадратичному времени. Таким образом, исследования в этой области преследуют две цели: использовать меньше места, чем этот бесхитростный алгоритм, и найти алгоритм указателей, который использует меньше проверок на равенство.
Алгоритм Флойда поиска цикла — это алгоритм указателей, который использует только два указателя, которые передвигаются вдоль последовательности с разными скоростями. Алгоритм называется также алгоритмом "черепахи и зайца " с намёком на басню Эзопа «Черепаха и заяц»[en].
Алгоритм назван именем Роберта Флойда, которому Дональд Кнут приписывает изобретение метода[3][4]. Однако алгоритм не был опубликован в работах Флойда, и, возможно, это ошибка атрибуции — Флойд описывает алгоритмы для перечисления всех простых циклов в ориентированном графе в статье 1967 года[5], но в статье не описывается задача нахождения цикла в функциональных графах, являющихся объектами рассмотрения статьи. Фактически утверждение Кнута (в 1969), приписывающее алгоритм Флойду без цитирования, является первым известным появление в печати, и, таким образом, алгоритм может оказаться математическим фольклором[en], не принадлежащим определённой личности[6].
Основная идея алгоритма заключается в том, что для любых целых i ≥ μ и k ≥ 0, xi = xi + kλ, где λ — длина цикла, а μ — индекс первого элемента в цикле. В частности, i = kλ ≥ μ тогда и только тогда, когда xi = x2i. Таким образом, чтобы найти период ν повторения, который будет кратен λ, алгоритму нужно проверять на повторение лишь значения этого специального вида — одно значение вдвое дальше от начала, чем второе. Как только ν нашли, алгоритм пересматривает последовательность с начальной точки, чтобы найти первое повторяющееся значение xμ в последовательности, используя факт, что λ делит ν, а потому xμ = xμ + v. Наконец, как только значение μ известно, легко найти длину λ кратчайшего цикла повторения путём нахождения первой позиции μ + λ, для которой xμ + λ = xμ.
Алгоритм использует два указателя в заданной последовательности, один (черепаха) идёт по значениям xi, а другой (заяц) по значениям x2i. На каждом шаге алгоритма индекс i увеличивается на единицу, передвигая черепаху на один элемент вперёд, а зайца — на два элемента, после чего значения в этих точках сравниваются. Наименьшее значение i > 0, для которого черепаха и заяц будут указывать на одинаковые значения, является желаемым значением ν.
Следующая программа на языке Python показывает, каким образом идея может быть имплементирована.
def floyd(f, x0):
# Основная часть алгоритма: находим повторение x_i = x_2i.
# Заяц движется вдвое быстрее черепахи
# и расстояние между ними увеличивается на единицу от шага к шагу.
# Однажды они окажутся внутри цикла, и тогда расстояние между ними
# будет делиться на λ.
tortoise = f(x0) # f(x0) является элементом, следующим за x0.
hare = f(f(x0))
while tortoise != hare:
tortoise = f(tortoise)
hare = f(f(hare))
# В этот момент позиция черепахи ν,
# которая равна расстоянию между черепахой и зайцем,
# делится на период λ. Таким образом, заяц, двигаясь
# по кольцу на одну позицию за один раз,
# и черепаха, опять начавшая движение со стартовой точки x0 и
# приближающаяся к кольцу, встретятся в начале кольца
# Находим позицию μ встречи.
mu = 0
tortoise = x0
while tortoise != hare:
tortoise = f(tortoise)
hare = f(hare) # Заяц и черепаха двигаются с одинаковой скоростью
mu += 1
# Находим длину кратчайшего цикла, начинающегося с позиции x_μ
# Заяц движется на одну позицию вперёд,
# в то время как черепаха стоит на месте.
lam = 1
hare = f(tortoise)
while tortoise != hare:
hare = f(hare)
lam += 1
return lam, mu
Данный код получает доступ к последовательности лишь запоминанием и копированием указателей, вычислением функции и проверкой равенства. Таким образом, алгоритм является алгоритмом указателей. Алгоритм использует O(λ + μ) операций этих типов и O(1) памяти [7].
Ричард Брент описал альтернативный алгоритм нахождения цикла, которому, подобно алгоритму черепахи и зайца, требуется лишь два указателя на последовательность [8]. Однако он основан на другом принципе — поиске наименьшей степени двойки 2i, которая больше как λ, так и μ. Для i = 0, 1, 2, ..., алгоритм сравнивает x2i−1 со значениями последовательности вплоть до следующей степени двух, останавливая процесс, когда найдётся совпадение. Алгоритм имеет два преимущества по сравнению с алгоритмом черепахи и зайца — во-первых, он находит правильную длину λ цикла сразу и не требуется второй шаг для её определения, а во-вторых, на каждом шаге осуществляется вызов функции f только один раз, а не три раза [9].
Следующая программа на языке Python более детально показывает, как эта техника работает.
def brent(f, x0):
# Остновная фаза: ищем степень двойки
power = lam = 1
tortoise = x0
hare = f(x0) # f(x0) — элемент/узел, следующий за x0.
while tortoise != hare:
if power == lam: # время начать новую степень двойки?
tortoise = hare
power *= 2
lam = 0
hare = f(hare)
lam += 1
# Находим позицию первого повторения длины λ
mu = 0
tortoise = hare = x0
for i in range(lam):
# range(lam) образует список со значениями 0, 1, ... , lam-1
hare = f(hare)
# расстояние между черепахой и зайцем теперь равно λ.
# Теперь черепаха и заяц движутся с одинаковой скоростью, пока не встретятся
while tortoise != hare:
tortoise = f(tortoise)
hare = f(hare)
mu += 1
return lam, mu
Подобно алгоритму черепахи и зайца, этот алгоритм является алгоритмом указателей, использующим O(λ + μ) проверок и вызовов функций и памяти O(1). Несложно показать, что число вызовов функции никогда не превзойдёт числа вызовов в алгоритме Флойда. Брент утверждает, что в среднем его алгоритм работает примерно на 36 % быстрее алгоритма Флойда, и что он обгоняет ро-алгоритм Полларда примерно на 24%. Он осуществил анализ среднего варианта[en] вероятностной версии алгоритма, в котором последовательность индексов, проходимых медленным указателем, не является степенью двойки, а является степенью двойки, умноженной на случайный коэффициент. Хотя основной целью его алгоритма была разложение числа на множители, Брент также обсуждает приложение алгоритма для проверки псевдослучайных генераторов[8].
Много авторов изучали техники для нахождения цикла, использующих большее количество памяти, чем у методов Флойда и Брента, но, зато, работающих быстрее. В общем случае эти методы запоминают некоторые ранее вычисленные значения последовательности и проверяют, не совпадает ли новое значение с одним из запомненных. Чтобы делать это быстро, обычно они используют хэш-таблицы или подобные структуры данных, а потому алгоритмы не являются алгоритмами указателей. В частности, обычно их нельзя приспособить к ро-алгоритму Полларда. Чем эти методы отличаются, так это способом определения, какие значения запоминать. Следуя Нивашу[10], мы кратко рассмотрим эти техники.
Любой алгоритм нахождения цикла, запоминающий максимум M значений из входной последовательности, должен сделать по меньшей мере вызовов функций[16][17].
Нахождение цикла используется во многих приложениях.
*print-circle* обнаруживает зацикленные списковые структуры и печатает их компактно.Задача нахождения цикла.