Задача нахождения цикла

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

В информатике и дискретной математике нахожде́ние ци́кла — это алгоритмическая задача поиска цикла в последовательности значений итеративной функции[en].

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

должна, в конечном счёте, использовать одно значение дважды, то есть должна существовать такая пара индексов i и j, что xi = xj. Как только это случится, последовательность будет продолжаться периодически[en], повторяя ту же самую последовательность значений от xi до xj − 1. Нахождение цикла — это задача поиска индексов i и j при заданной функции f и начальном значении x0.

Известно несколько алгоритмов поиска цикла быстро и при малой памяти. Алгоритм «черепахи и зайца» Флойда передвигает два указателя с различной скоростью через последовательность значений, пока не получит одинаковые значения. Другой алгоритм, алгоритм Брента, основан на идее экспоненциального поиска[en]. Оба алгоритма, Флойда и Брента, используют только фиксированное число ячеек памяти, и число вычислений функции пропорционально расстоянию от стартовой точки до первой точки повторения. Некоторые другие алгоритмы используют большее количество памяти, чтобы получить меньшее число вычислений значений функции.

Задача нахождения цикла используется для проверки качества генераторов псевдослучайных чисел и криптографических хеш-функций, в алгоритмах вычислительной теории чисел[en], для определения бесконечных циклов в компьютерных программах и периодических конфигураций клеточных автоматов, а также для автоматического анализа формы[en] связных списков.

Пример[править | править код]

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

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

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

Цикл в этой последовательности значений — 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 и использования структуры данных такой, как хеш-таблица, для запоминания этих значений и теста, что каждое последующее значение ещё не запомнено. Однако ёмкостная сложность данного алгоритма пропорциональна λ + μ, и эта сложность излишне велика. Кроме того, чтобы использовать этот метод для алгоритма указателей, потребуется использовать тест на равенство для каждой пары значений, что приведёт к квадратичному времени. Таким образом, исследования в этой области преследуют две цели: использовать меньше места, чем этот бесхитростный алгоритм, и найти алгоритм указателей, который использует меньше проверок на равенство.

Черепаха и заяц[править | править код]

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

Алгоритм Флойда поиска цикла — это алгоритм указателей, который использует только два указателя, которые передвигаются вдоль последовательности с разными скоростями. Алгоритм называется также алгоритмом «черепахи и зайца» с намёком на басню Эзопа «Черепаха и заяц»[en].

Алгоритм назван именем Роберта Флойда, которому Дональд Кнут приписывает изобретение метода[3][4]. Однако алгоритм не был опубликован в работах Флойда, и, возможно, это ошибка атрибуции: Флойд описывает алгоритмы для перечисления всех простых циклов в ориентированном графе в статье 1967 года[5], но в этой статье не описана задача нахождения цикла в функциональных графах, являющихся объектами рассмотрения статьи. Фактически утверждение Кнута, сделанное в 1969 году и приписывающее алгоритм Флойду без цитирования, является первым известным упоминанием данного алгоритма в печати, и, таким образом, алгоритм может оказаться математическим фольклором[en], не принадлежащим определённой личности[6].

Основная идея алгоритма заключается в том, что для любых целых iμ и k ≥ 0, xi = xi + , где λ — длина цикла, а μ — индекс первого элемента в цикле. В частности, i = μ тогда и только тогда, когда 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 числа 2, которая больше как λ, так и μ.

Для 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], мы кратко рассмотрим эти техники.

  • Брент[8] уже описывал вариации своей техники, в которых индексы запомненных значений последовательности являются степенями числа R, отличного от двух. При выборе R ближе к единице и, запоминая значения последовательности с индексами, близкими к последовательным степеням R, алгоритм нахождения цикла может использовать число вызовов функции, которое не превосходит произвольно малого множителя оптимального значения λ + μ[11][12].
  • Седжвик, Шиманьский и Яо [13] предложили метод, который использует M ячеек памяти и требует в худшем случае только вызовов функции с некоторой постоянной c, для которой она показала оптимальность. Техника использует числовой параметр d, запоминая в таблице только те позиции последовательности, которые кратны d. Таблица очищается, а значение d удваивается, если число запомненных значений слишком велико.
  • Некоторые авторы описали методы отмеченных точек, которые запоминают в таблице значения функции, опираясь на критерии, использующие значения, а не индексы (как в методе Седжвика и др.). Например, могут запоминаться значения по модулю от некоторого числа d[14][15]. Более просто, Ниваш[10] приписывает Вудруфу предложение запоминать случайно выбранное предыдущее значение, делая подходящий случайный выбор на каждом шаге.
  • Ниваш[10] описывает алгоритм, который не использует фиксированного количества памяти, но для которого ожидаемое количество используемой памяти (в предположении, что входная функция случайна) логарифмически зависит от длины последовательности. По этой технике элемент записывается в таблицу, если никакой предыдущий элемент не имеет меньшего значения. Как показал Ниваш, элементы в этой технике можно располагать в стеке, и каждое последующее значение нужно сравнивать только с элементом на вершине стека. Алгоритм прекращает работу, когда повторение элемента с меньшим значением найдено. Если использовать несколько стеков и случайную перестановку значений внутри каждого стека, получаем выигрыш в скорости за счёт памяти аналогично предыдущим алгоритмам. Однако даже версия алгоритма с одним стеком не является алгоритмом указателей, поскольку требуется знать, какое из значений меньше.

Любой алгоритм нахождения цикла, запоминающий максимум M значений из входной последовательности, должен сделать по меньшей мере вызовов функций[16][17].

Приложения[править | править код]

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

Примечания[править | править код]

  1. Joux, 2009, p. 223.
  2. 1 2 Joux, 2009, p. 224.
  3. 1 2 Knuth, 1969, p. 7, ex. 6, 7.
  4. Menezes, van Oorschot, Vanstone, 1996, p. 125.
  5. Floyd, 1967, p. 636—644.
  6. Aumasson, Meier, Phan, Henzen, 2015, p. 21, сноска 8.
  7. Joux, 2009, p. 225—226, Section 7.1.1, Floyd's cycle-finding algorithm.
  8. 1 2 3 4 Brent, 1980, p. 176—184.
  9. Joux, 2009, p. 226—227, Section 7.1.2, Brent's cycle-finding algorithm.
  10. 1 2 3 4 Nivasch, 2004, p. 135—140.
  11. Schnorr, Lenstra, 1984, p. 289—311.
  12. 1 2 Teske, 1998, p. 1637—1663.
  13. Sedgewick, Szymanski, Yao, 1982, p. 376—390.
  14. van Oorschot, Wiener, 1999, p. 1—28.
  15. 1 2 Quisquater, Delescaille, 1989, p. 429—434.
  16. 1 2 Fich, 1981, p. 96—105.
  17. Allender, Klawe, 1985, p. 231—237.
  18. Pollard, 1975, p. 331—334.
  19. Pollard, 1978, p. 918—924.
  20. 1 2 Kaliski, Rivest, Sherman, 1988, p. 3—36.
  21. Joux, 2009, p. 242—245, Section 7.5, Collisions in hash functions.
  22. Van Gelder, 1987, p. 23—31.
  23. Auguston, Hon, 1997, p. 37—42.
  24. Fich, 1981.

Литература[править | править код]

Ссылки[править | править код]