Обнаружение цикла

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

Для любой функции f, которая отображает конечный набор S на себя, и любое начальное значение x 0 в S, последовательность повторенных значения функции

$x\; 0,\; x\; 1\; =\; f\; (x\; 0),\; x\; 2\; =\; f\; (x\; 1),\dots ,\; xi\; =\; f\; (xi\; -\; 1),\dots \; \{\backslash \; displaystyle\; x\_\; \{0\},\; \backslash \; x\_\; \{1\; \}\; =\; f\; (x\_\; \{0\}),\; \backslash \; x\_\; \{2\}\; =\; f\; (x\_\; \{1\}),\; \backslash \; \backslash \; dots,\; \backslash \; x\_\; \{i\}\; =\; f\; (x\_\; \{i-1\}),\; \backslash \; \backslash \; dots\}$

в конечном итоге должен использовать одно и то же значение дважды: должна существовать пара различных индексов i и j, такая, что x i = x j. Как только это произойдет, последовательность должна продолжаться периодически, повторяя ту же последовательность значений от x i до x j - 1. Обнаружение цикла - это проблема поиска i и j при заданных f и x 0.

Известно несколько алгоритмов для быстрого поиска циклов с небольшим объемом памяти. Алгоритм черепахи и зайца Роберта Флойда перемещает два указателя с разной скоростью через последовательность значений, пока они оба не укажут на равные значения. В качестве альтернативы алгоритм Брента основан на идее экспоненциального поиска. Алгоритмы как Флойда, так и Брента используют только постоянное количество ячеек памяти и выполняют ряд вычислений функций, которые пропорциональны расстоянию от начала последовательности до первого повторения. Некоторые другие алгоритмы жертвуют большим объемом памяти за меньшее количество вычислений функций.

Применения обнаружения цикла включают проверку качества генераторов псевдослучайных чисел и криптографических хеш-функций, алгоритмов теории чисел, обнаружение бесконечные циклы в компьютерных программах и периодические конфигурации в клеточных автоматах, автоматический анализ формы из структур данных связанного списка, обнаружение взаимоблокировок для управления транзакциями в СУБД.

• 1 Пример
• 2 Определения
• 3 Компьютерное представление
• 4 Алгоритмы
  • 4.1 Черепаха и Заяц Флойда
  • 4.2 Алгоритм Брента
  • 4.3 Алгоритм Госпера
  • 4.4 Компромисс между пространством и временем
• 5 Приложения
• 6 Ссылки
• 7 Внешние ссылки

Функция от и до множества {0,1,2,3,4,5,6,7,8} и соответствующий функциональный граф

На рисунке показана функция f, которая отображает множество S = {0,1,2,3,4, 5,6,7,8} себе. Если начать с x 0 = 2 и многократно применить f, вы увидите последовательность значений

2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1,....

Цикл в этой последовательности значений равен 6, 3, 1.

Пусть S - любое конечное множество, f - любая функция от S до самой себя, и x 0 - любой элемент S. Для любого i>0 пусть x i = f (x i - 1). Пусть μ будет наименьшим индексом, так что значение x μ повторяется бесконечно часто в последовательности значений x i, и пусть λ (длина цикла) будет наименьшим положительным целым числом, таким, что x μ = x λ + μ. Задача обнаружения цикла - это задача нахождения λ и μ.

Можно рассмотреть ту же проблему теоретически, построив функциональный граф (то есть, ориентированный граф, в котором каждая вершина имеет одно исходящее ребро), вершины которого являются элементами S, а ребра которого отображают элемент на соответствующее значение функции, как показано на рисунке. Множество вершин , достижимых из начальной вершины x 0, образуют подграф с формой, напоминающей греческую букву ро (ρ): путь длиной μ от x От 0 до цикла из λ вершин.

Как правило, f не указывается в виде таблицы значений, так как показано на рисунке выше. Напротив, алгоритму обнаружения цикла может быть предоставлен доступ либо к последовательности значений x i, либо к подпрограмме для вычисления f. Задача состоит в том, чтобы найти λ и μ, исследуя как можно меньше значений из последовательности или выполняя как можно меньше вызовов подпрограмм. Как правило, также важна пространственная сложность алгоритма для задачи обнаружения цикла: мы хотим решить эту проблему, используя объем памяти, значительно меньший, чем потребуется для хранения всей последовательности.

В некоторых приложениях, и в частности в алгоритме ро Полларда для целочисленной факторизации, алгоритм имеет гораздо более ограниченный доступ к S и к f. В алгоритме Ро Полларда, например, S - это набор целых чисел по модулю неизвестного простого множителя числа, которое нужно разложить на множители, поэтому даже размер S неизвестен алгоритму. Чтобы позволить использовать алгоритмы обнаружения цикла с такими ограниченными знаниями, они могут быть разработаны на основе следующих возможностей. Первоначально предполагается, что алгоритм имеет в своей памяти объект, представляющий указатель на начальное значение x 0. На любом этапе он может выполнить одно из трех действий: он может скопировать любой указатель, который он имеет, на другой объект в памяти, он может применить f и заменить любой из своих указателей указателем на следующий объект в последовательности, или он может применить подпрограмма для определения, представляют ли два из ее указателя равные значения в последовательности. Действие проверки на равенство может включать в себя некоторые нетривиальные вычисления: например, в алгоритме ро Полларда оно реализуется путем проверки того, имеет ли разница между двумя сохраненными значениями нетривиальный наибольший общий делитель с числом, которое нужно факторизовать. В этом контексте, по аналогии с моделью вычислений машины указателя, алгоритм, который использует только копирование указателя, продвижение в последовательности и проверки равенства, может называться алгоритмом указателя.

Если ввод задан как подпрограмма для вычисления f, проблема обнаружения цикла может быть тривиально решена с использованием только приложений функции λ + μ, просто путем вычисления последовательности значений x i и с использованием структуры данных , такой как хэш-таблица, для хранения этих значений и проверки того, было ли уже сохранено каждое последующее значение. Однако пространственная сложность этого алгоритма пропорциональна λ + μ, что неоправданно велико. Кроме того, для реализации этого метода в виде алгоритма указателя потребуется применить проверку равенства к каждой паре значений, что приведет к квадратичному времени в целом. Таким образом, исследования в этой области сосредоточены на двух целях: использование меньшего пространства, чем этот наивный алгоритм, и поиск алгоритмов указателей, которые используют меньше тестов на равенство.

Черепаха и Заяц Флойда

Алгоритм обнаружения цикла «черепаха и заяц» Флойда, примененный к последовательности 2, 0, 6, 3, 1, 6, 3, 1,...

Флойда Алгоритм поиска цикла - это алгоритм указателя, который использует только два указателя, которые перемещаются по последовательности с разной скоростью. Его также называют "алгоритмом черепахи и зайца", отсылая к басне Эзопа Черепаха и Заяц.

. Алгоритм назван в честь Роберта У. Флойда, которому приписывают его изобретение Дональда Кнута. Однако алгоритм не появляется в опубликованной работе Флойда, и это может быть неправильной атрибуцией: Флойд описывает алгоритмы для перечисления всех простых циклов в ориентированном графе в статье 1967 года, но эта статья не описывает цикл -нахождение проблемы в функциональных графах, которой и посвящена данная статья. Фактически, заявление Кнута (1969 г.), приписывающее его Флойду, без цитирования, является первым известным печатным словом, и, таким образом, может быть народной теоремой, не относящейся к одному человеку <91.>

Ключевое понимание алгоритма заключается в следующем. Если цикл существует, то для любых целых чисел i ≥ μ и k ≥ 0 x i = x i + kλ, где λ - длина найденного цикла. а μ - номер первого элемента цикла. На основании этого можно затем показать, что i = kλ ≥ μ для некоторого k тогда и только тогда, когда x i = x 2i. Таким образом, алгоритму нужно только проверить повторяющиеся значения этой специальной формы, одно в два раза дальше от начала последовательности, чем другое, чтобы найти период ν повторения, кратный λ. Как только ν найдено, алгоритм повторяет последовательность от ее начала, чтобы найти первое повторяющееся значение x μ в последовательности, используя тот факт, что λ делит ν, и, следовательно, x μ = х μ + v. Наконец, как только значение μ известно, становится тривиальным найти длину λ кратчайшего повторяющегося цикла путем поиска первой позиции μ + λ, для которой x μ + λ = x μ.

Таким образом, алгоритм поддерживает два указателя на заданную последовательность, один (черепаха) в x i, а другой (заяц) в x 2i. На каждом шаге алгоритма он увеличивает i на единицу, перемещая черепаху на один шаг вперед, а зайца на два шага вперед по последовательности, а затем сравнивает значения последовательности на этих двух указателях. Наименьшее значение i>0, для которого черепаха и заяц указывают на равные значения, является искомым значением ν.

Следующий код Python показывает, как эту идею можно реализовать в виде алгоритма.

def floyd (f, x0): # Основная фаза алгоритма: поиск повторения x_i = x_2i. # Заяц движется вдвое быстрее черепахи и # расстояние между ними увеличивается на 1 с каждым шагом. # В конце концов они оба окажутся внутри цикла, а затем, # в какой-то момент, расстояние между ними будет # делиться на период λ. черепаха = f (x0) # f (x0) - это элемент / узел рядом с x0. hare = f (f (x0)) while tortoise! ​​= hare: tortoise = f (tortoise) hare = f (f (hare)) # В этой точке положение черепахи, ν, которое также равно # расстоянию между зайцами и черепаха, делится на # период λ. Таким образом, заяц, перемещающийся по кругу по одному шагу за раз, # и черепаха (сброшен на x0), двигаясь к кругу, # пересекутся в начале круга. Поскольку # расстояние между ними постоянно и равно 2ν, кратно λ, # они согласятся, как только черепаха достигнет индекса μ. # Найдите позицию μ первого повторения. mu = 0 tortoise = x0 while tortoise! ​​= hare: tortoise = f (tortoise) hare = f (hare) # Заяц и черепаха движутся с одинаковой скоростью mu + = 1 # Найдите длину самого короткого цикла, начиная с x_μ # Заяц делает шаг за шагом, пока черепаха неподвижна. # lam увеличивается до тех пор, пока не будет найдено λ. lam = 1 hare = f (черепаха) while tortoise! ​​= hare: hare = f (hare) lam + = 1 return lam, mu

Этот код обращается к последовательности только путем сохранения и копирования указателей, оценок функций и тестов на равенство ; поэтому он квалифицируется как алгоритм указателя. Алгоритм использует O (λ + μ) операций этих типов и O (1) дискового пространства.

Алгоритм Брента

Ричард П. Брент описал альтернативный алгоритм обнаружения цикла, который, как и Алгоритм черепахи и зайца требует только двух указателей в последовательности. Однако он основан на другом принципе: поиск наименьшей степени двойки 2, которая больше, чем λ и μ. Для i = 0, 1, 2,... алгоритм сравнивает x 2−1 с каждым последующим значением последовательности до следующей степени двойки и останавливается, когда находит совпадение. Он имеет два преимущества по сравнению с алгоритмом черепахи и зайца: он находит правильную длину цикла λ напрямую, вместо того, чтобы искать ее на следующем этапе, и его шаги включают только одну оценку f, а не три.

Следующий код 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 # Найти позицию первого повторения длины λ tortoise = hare = x0 для i in range (lam): # range (lam) производит список со значениями 0, 1,..., lam-1 hare = f (hare) # Теперь расстояние между зайцем и черепахой равно λ. # Затем заяц и черепаха движутся с одинаковой скоростью, пока не согласятся, что mu = 0, а черепаха! = Hare: tortoise = f (tortoise) hare = f (hare) mu + = 1 return lam, mu

Как черепаха и hare алгоритм, это алгоритм указателя, который использует O (λ + μ) тестов и оценок функций и O (1) дискового пространства. Нетрудно показать, что количество вычислений функций никогда не может быть больше, чем для алгоритма Флойда. Брент утверждает, что в среднем его алгоритм поиска циклов работает примерно на 36% быстрее, чем алгоритм Флойда, и что он ускоряет алгоритм Полларда примерно на 24%. Он также выполняет анализ среднего случая для рандомизированной версии алгоритма, в которой последовательность индексов, отслеживаемых более медленным из двух указателей, не является степенью двойки, а скорее рандомизированным кратным степеням. из двух. Хотя его основное предполагаемое применение было в алгоритмах целочисленной факторизации, Брент также обсуждает приложения для тестирования генераторов псевдослучайных чисел.

алгоритм Госпера

R. Алгоритм У. Госпера находит период $\lambda \; \{\backslash \; displaystyle\; \backslash \; lambda\}$, а также нижнюю и верхнюю границу начальной точки $\mu \; l\; \{\backslash \; displaystyle\; \backslash \; mu\; \_\; \{l\}\}$и $\mu \; u\; \{\backslash \; displaystyle\; \backslash \; mu\; \_\; \{u\}\}$первого цикла. Разница между нижней и верхней границей того же порядка, что и период, например. $\mu \; l\; +\; \lambda \; \sim \; \mu \; h\; \{\backslash \; displaystyle\; \backslash \; mu\; \_\; \{l\}\; +\; \backslash \; lambda\; \backslash \; sim\; \backslash \; mu\; \_\; \{h\}\}$.

Основная особенность алгоритма Госпера заключается в том, что он никогда не выполняет резервное копирование для переоценки генератора функции и экономичен как в пространстве, так и во времени. Это можно примерно описать как параллельную версию алгоритма Брента. В то время как алгоритм Брента постепенно увеличивает разрыв между черепахой и зайцем, алгоритм Госпера использует несколько черепах (сохраняются несколько предыдущих значений), которые расположены примерно по экспоненте. Согласно примечанию в элементе 132 HAKMEM, этот алгоритм обнаружит повторение перед третьим появлением любого значения, например. цикл будет повторяться не более двух раз. В этом примечании также говорится, что достаточно сохранить $\Theta \; (log\; \; \lambda )\; \{\backslash \; displaystyle\; \backslash \; Theta\; (\backslash \; log\; \backslash \; lambda)\}$предыдущие значения; однако предоставленная реализация хранит значения $\Theta \; (log\; \; (\mu \; +\; \lambda ))\; \{\backslash \; displaystyle\; \backslash \; Theta\; (\backslash \; log\; (\backslash \; mu\; +\; \backslash \; lambda))\}$. Например: значения функции представляют собой 32-битные целые числа, и априори известно, что вторая итерация цикла заканчивается после не более чем двух вычислений функции с начала, т.е. $\mu \; +\; 2\; \lambda \; \le \; 2\; 32\; \{\backslash \; displaystyle\; \backslash \; mu\; +2\; \backslash \; lambda\; \backslash \; leq\; 2\; ^\; \{32\}\}$. Тогда достаточно сохранить 33 32-битных целых числа.

После $i\; \{\backslash \; displaystyle\; i\}$-ой оценки функции генератора алгоритм сравнивает сгенерированное значение с $O\; (log\; \; i)\; \{\backslash \; displaystyle\; O\; (\backslash \; log\; i)\}$предыдущие значения; обратите внимание, что $i\; \{\backslash \; displaystyle\; i\}$возрастает не менее $\mu \; +\; \lambda \; \{\backslash \; displaystyle\; \backslash \; mu\; +\; \backslash \; lambda\}$и не более $\mu \; +\; 2\; \lambda \; \{\backslash \; displaystyle\; \backslash \; mu\; +2\; \backslash \; lambda\}$. Следовательно, временная сложность этого алгоритма составляет $O\; ((\mu \; +\; \lambda )\; \cdot \; log\; \; (\mu \; +\; \lambda ))\; \{\backslash \; displaystyle\; O\; ((\backslash \; mu\; +\; \backslash \; lambda)\; \backslash \; cdot\; \backslash \; log\; (\backslash \; mu\; +\; \backslash \; lambda))\}$. Поскольку он хранит значения $\Theta \; (log\; \; (\mu \; +\; \lambda ))\; \{\backslash \; displaystyle\; \backslash \; Theta\; (\backslash \; log\; (\backslash \; mu\; +\; \backslash \; lambda))\}$, его пространственная сложность составляет $\Theta \; (\; журнал\; \; (\mu \; +\; \lambda ))\; \{\backslash \; Displaystyle\; \backslash \; Theta\; (\backslash \; log\; (\backslash \; mu\; +\; \backslash \; lambda))\}$. Это происходит при обычном предположении, присутствующем в этой статье, что размер значений функции постоянен. Без этого предположения сложность пространства равна $\Omega \; (log\; 2\; \; (\mu \; +\; \lambda ))\; \{\backslash \; displaystyle\; \backslash \; Omega\; (\backslash \; log\; ^\; \{2\}\; (\backslash \; mu\; +\; \backslash \; lambda))\}$, поскольку нам нужно по крайней мере $\mu \; +\; \lambda \; \{\backslash \; displaystyle\; \backslash \; mu\; +\; \backslash \; lambda\}$различных значений, и поэтому размер каждого значения составляет $\Omega \; (log\; \; (\mu \; +\; \lambda ))\; \{\backslash \; displaystyle\; \backslash \; Omega\; (\backslash \; log\; (\backslash \; mu\; +\; \backslash \; lambda))\}$.

Компромисс между пространством и временем

Ряд авторов изучили методы обнаружения цикла, которые используют больше памяти, чем методы Флойда и Брента, но обнаруживают циклы быстрее. Как правило, эти методы хранят несколько ранее вычисленных значений последовательности и проверяют, равно ли каждое новое значение одному из ранее вычисленных значений. Чтобы сделать это быстро, они обычно используют хэш-таблицу или аналогичную структуру данных для хранения ранее вычисленных значений и, следовательно, не являются алгоритмами указателя: в частности, они обычно не могут быть применены к алгоритму rho Полларда.. Эти методы различаются тем, как они определяют, какие значения хранить. Следуя Nivasch, мы кратко рассмотрим эти методы.

• Брент уже описывает варианты своей техники, в которых индексы сохраненных значений последовательности являются степенями числа R, отличного от двух. Выбирая R как число, близкое к единице, и сохраняя значения последовательности в индексах, которые близки к последовательности последовательных степеней R, алгоритм обнаружения цикла может использовать ряд оценок функций, которые находятся в пределах произвольно малого коэффициента оптимального λ + μ.
• Седжвик, Шимански и Яо предлагают метод, использующий M ячеек памяти и требующий в худшем случае только $(\lambda \; +\; \mu )\; (1\; +\; c\; M\; -\; 1/2)\; \{\; \backslash \; displaystyle\; (\backslash \; lambda\; +\; \backslash \; mu)\; (1\; +\; cM\; ^\; \{-\; 1/2\})\}$оценки функции для некоторой константы c, которая, по их мнению, является оптимальной. Этот метод включает поддержание числового параметра d, сохранение в таблице только тех позиций в последовательности, которые кратны d, очистку таблицы и удвоение d всякий раз, когда было сохранено слишком много значений.
• Несколько авторов описали методы выделенных точек, которые хранят значения функций в таблице на основе критерия, включающего значения, а не (как в методе Седжевика и др.) на основе их положения. Например, могут быть сохранены значения, равные нулю по модулю некоторого значения d. Проще говоря, Nivasch доверяет Д.П. Вудраффу предложение хранить случайную выборку ранее увиденных значений, делая соответствующий случайный выбор на каждом этапе, чтобы выборка оставалась случайной.
• Nivasch описывает алгоритм, который не использует фиксированный объем памяти, но для которого ожидаемый объем используемой памяти (в предположении, что функция ввода является случайной) является логарифмическим по длине последовательности. При использовании этого метода элемент сохраняется в таблице памяти, когда ни один из последующих элементов не имеет меньшего значения. Как показывает Nivasch, элементы с помощью этого метода могут поддерживаться с использованием структуры данных стека , и каждое последующее значение последовательности необходимо сравнивать только с вершиной стека. Алгоритм завершается, когда обнаруживается повторяющийся элемент последовательности с наименьшим значением. Выполнение того же алгоритма с несколькими стеками, используя случайные перестановки значений для изменения порядка значений в каждом стеке, позволяет найти компромисс между пространством и временем, аналогичный предыдущим алгоритмам. Однако даже версия этого алгоритма с одним стеком не является алгоритмом указателя из-за сравнений, необходимых для определения, какое из двух значений меньше.

Любой алгоритм обнаружения цикла, который хранит не более M значений из входной последовательности, должен выполнить не менее $(\lambda \; +\; \mu )\; (1\; +\; 1\; M\; -\; 1)\; \{\backslash \; displaystyle\; (\backslash \; lambda\; +\; \backslash \; mu)\; \backslash \; left\; (1\; +\; \{\backslash \; frac\; \{1\}\; \{M-1\}\}\; \backslash \; right)\}$оценка функций.

Обнаружение цикла использовалось во многих приложениях.

• Определение длины цикла генератора псевдослучайных чисел является одним из показателей его силы. Это приложение, которое цитирует Кнут при описании метода Флойда. Брент описывает результаты тестирования линейного конгруэнтного генератора таким образом; его срок оказался значительно меньше заявленного. Для более сложных генераторов последовательность значений, в которой должен быть найден цикл, может представлять не выход генератора, а его внутреннее состояние.
• Некоторые алгоритмы теории чисел являются основан на обнаружении цикла, включая алгоритм ро Полларда для целочисленной факторизации и связанный с ним алгоритм кенгуру для задачи дискретного логарифма.
• In криптографические приложения, способность находить два различных значения x μ −- 1 и x λ + μ −- 1, сопоставленных некоторой криптографической функцией ƒ с одним и тем же значением x μ может указывать на слабость ƒ. Например, Quisquater и Delescaille применяют алгоритмы обнаружения цикла при поиске сообщения и пару ключей Data Encryption Standard, которые отображают это сообщение в одно и то же зашифрованное значение; Калиски, Ривест и Шерман также используют алгоритмы обнаружения цикла для атаки на DES. Этот метод также можно использовать для поиска коллизии в криптографической хеш-функции .
• Обнаружение цикла может быть полезным как способ обнаружения бесконечных циклов в определенных типах компьютерные программы.
• Периодические конфигурации в моделировании клеточного автомата могут быть найдены путем применения алгоритмов обнаружения цикла к последовательности состояний автомата.
• Анализ формы из связан Структуры данных list - это метод проверки правильности алгоритма с использованием этих структур. Если узел в списке неправильно указывает на более ранний узел в том же списке, структура сформирует цикл, который может быть обнаружен этими алгоритмами. В Common Lisp принтер S-выражения под управлением переменной * print-circle *обнаруживает кольцевую структуру списка и печатает ее компактно.
• Теске описывает приложения в теории вычислительных групп : определение структуры абелевой группы по набору ее образующих. Криптографические алгоритмы Калиски и др. также может рассматриваться как попытка вывести структуру неизвестной группы.
• Fich (1981) кратко упоминает приложение к компьютерному моделированию небесной механики, которое она атрибуты Уильяма Кахана. В этом приложении обнаружение цикла в фазовом пространстве орбитальной системы может использоваться для определения того, является ли система периодической с точностью до точности моделирования.
• В наборе фракталов Мандельброта некоторые методы производительности используются для ускорения генерации изображения. Один из них называется «проверка периода» и в основном заключается в нахождении циклов на точечной орбите. В этой статье описывается техника «проверки периода », а здесь вы можете найти лучшее объяснение. Для реализации этого необходимо реализовать несколько алгоритмов обнаружения цикла.

• Габриэль Ниваш, Проблема обнаружения цикла и алгоритм стека
• Черепаха и Заяц, Портлендский репозиторий паттернов
• Алгоритм обнаружения цикла Флойда (Черепаха и Заяц)
• Алгоритм обнаружения цикла Брента (Телепортирующаяся черепаха)