Русская Википедия:Нахождение цикла

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Нахождение цикла — алгоритмическая задача поиска цикла в последовательности значений Шаблон:Не переведено 5.

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

<math> x_0,\ x_1=f(x_0),\ x_2=f(x_1),\ \dots,\ x_i=f(x_{i-1}),\ \dots</math>

должна в конечном счёте использовать одно значение дважды, то есть должна существовать такая пара индексов Шаблон:Mvar и Шаблон:Mvar, что Шаблон:Math. Как только это случится, последовательность будет продолжаться периодически, повторяя ту же самую последовательность значений от Шаблон:Math до Шаблон:Math. Нахождение цикла — это задача поиска индексов Шаблон:Mvar и Шаблон:Mvar при заданной функции Шаблон:Mvar и начальном значении Шаблон:Math.

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

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

Пример

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

Рисунок показывает функцию Шаблон:Mvar, отображающую множество Шаблон:Math} на себя. Если начать с точки Шаблон:Math и повторять применение функции Шаблон:Mvar к получаемым значениям, увидим последовательность значений

Шаблон:Math

Цикл в этой последовательности значений — Шаблон:Math.

Определения

Пусть Шаблон:Mvar — конечное множество, Шаблон:Mvar — некая функция, отображающая Шаблон:Mvar в то же самое множество, а Шаблон:Math — любой элемент из Шаблон:Mvar. Для любого Шаблон:Math пусть Шаблон:Math. Пусть Шаблон:Mvar — наименьший индекс, для которого значение Шаблон:Math повторяется бесконечное число раз в последовательности значений Шаблон:Math, и пусть Шаблон:Mvar (длина цикла) — наименьшее положительное целое число, такое, что Шаблон:Math. Задача нахождения цикла — это задача поиска Шаблон:Mvar и Шаблон:MvarШаблон:Sfn.

Можно рассматривать эту задачу как задачу теории графов, если построить функциональный граф (то есть ориентированный граф, в котором каждая вершина имеет единственную исходящую дугу), вершины которого являются элементами множества Шаблон:Mvar, а рёбра соответствуют отображению элементов в соответствующие значения функции, как показано на рисунке. Множество вершин, достижимых из стартовой вершины Шаблон:Math образуют подграф в форме, похожем на греческую букву ро (Шаблон:Mvar) — путь длины Шаблон:Mvar от Шаблон:Math до цикла из Шаблон:Mvar вершинШаблон:Sfn.

Представление в компьютере

Обычно Шаблон:Mvar не задаётся в виде таблицы значений, как показано на рисунке выше. Скорее алгоритм определения цикла может получить на входе либо последовательность значений Шаблон:Math, либо подпрограмму вычисления Шаблон:Mvar. Задача состоит в нахождении Шаблон:Mvar и Шаблон:Mvar с проверкой малого числа значений последовательности, либо с обращением к процедуре вычисления значения как можно меньшее число раз. Обычно важна также Шаблон:Не переведено 5 алгоритма задачи нахождения цикла: желательно использовать память, значительно меньшую по сравнению с размером последовательности целиком.

В некоторых приложениях, и, в частности, в ро-алгоритме Полларда для факторизации целых чисел, алгоритм имеет очень ограниченный доступ к Шаблон:Mvar и Шаблон:Mvar. В ро-алгоритме Полларда, например, Шаблон:Mvar — это множество сравнимых по неизвестному простому множителю числа, который следует разложить на множители, так что даже размер множества Шаблон:Mvar для алгоритма неизвестен. Чтобы алгоритм нахождения цикла работал в таких стеснённых условиях, он должен разрабатываться на основе следующих возможностей. Первоначально алгоритм имеет в памяти объект, представляющий указатель на начальное значение Шаблон:Math. На любом шаге алгоритм может осуществлять одну из трёх действий: он может копировать любой указатель в любой другой объект памяти, он может вычислить значение Шаблон:Mvar и заменить любой указатель на указатель на вновь образованный объект из последовательности, или использовать процедуру проверки совпадения значений, на которые указывают два указателя.

Тест проверки равенства может повлечь некоторые нетривиальные вычисления. Например, в ро-алгоритме Полларда этот тест проверяет, не имеет ли разность двух запомненных значений нетривиальный наибольший общий делитель с разлагаемым на множители числом Шаблон:Sfn. В этом контексте, по аналогии с моделью вычисления Шаблон:Не переведено 5, алгоритм, использующий только копирование указателей, передвижение в последовательности и тест на равенство, можно назвать алгоритмом указателей.

Алгоритмы

Если вход задан как подпрограмма вычисления Шаблон:Mvar, задачу нахождения цикла можно тривиально решить, сделав только Шаблон:Math вызовов функции просто путём вычисления последовательности значений Шаблон:Math и использования структуры данных такой, как хеш-таблица, для запоминания этих значений и теста, что каждое последующее значение ещё не запомнено. Однако ёмкостная сложность данного алгоритма пропорциональна Шаблон:Math, и эта сложность излишне велика. Кроме того, чтобы использовать этот метод для алгоритма указателей, потребуется использовать тест на равенство для каждой пары значений, что приведёт к квадратичному времени. Таким образом, исследования в этой области преследуют две цели: использовать меньше места, чем этот бесхитростный алгоритм, и найти алгоритм указателей, который использует меньше проверок на равенство.

Черепаха и заяц

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

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

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

Основная идея алгоритма заключается в том, что для любых целых Шаблон:Math и Шаблон:Math, Шаблон:Math, где Шаблон:Mvar — длина цикла, а Шаблон:Mvar — индекс первого элемента в цикле. В частности, Шаблон:Math тогда и только тогда, когда Шаблон:Math.

Таким образом, чтобы найти период Шаблон:Mvar повторения, который будет кратен Шаблон:Mvar, алгоритму нужно проверять на повторение лишь значения этого специального вида — одно значение вдвое дальше от начала, чем второе.

Как только период Шаблон:Mvar будет найден, алгоритм пересматривает последовательность с начальной точки, чтобы найти первое повторяющееся значение Шаблон:Math в последовательности, используя факт, что Шаблон:Mvar делит Шаблон:Mvar, а потому Шаблон:Math. Наконец, как только значение Шаблон:Mvar станет известно, легко найти длину Шаблон:Mvar кратчайшего цикла повторения путём нахождения первой позиции Шаблон:Math, для которой Шаблон:Math.

Алгоритм использует два указателя в заданной последовательности: один (черепаха) идёт по значениям Шаблон:Math, а другой (заяц) по значениям Шаблон:Math. На каждом шаге алгоритма индекс Шаблон:Mvar увеличивается на единицу, передвигая черепаху на один элемент вперёд, а зайца — на два элемента, после чего значения в этих точках сравниваются. Наименьшее значение Шаблон:Math, для которого черепаха и заяц будут указывать на одинаковые значения, является искомым значением Шаблон:Mvar.

Следующая программа на языке 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

Данный код получает доступ к последовательности лишь запоминанием и копированием указателей, вычислением функции и проверкой равенства. Таким образом, алгоритм является алгоритмом указателей. Алгоритм использует Шаблон:Math операций этих типов и Шаблон:Math памяти Шаблон:Sfn.

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

Ричард Брент описал альтернативный алгоритм нахождения цикла, которому, подобно алгоритму черепахи и зайца, требуется лишь два указателя на последовательность Шаблон:Sfn. Однако он основан на другом принципе — поиске наименьшей степени Шаблон:Math числа 2, которая больше как Шаблон:Mvar, так и Шаблон:Mvar.

Для Шаблон:Math, алгоритм сравнивает Шаблон:Math со значениями последовательности вплоть до следующей степени двух, останавливая процесс, когда найдётся совпадение. Алгоритм имеет два преимущества по сравнению с алгоритмом черепахи и зайца: во-первых, он находит правильную длину Шаблон:Mvar цикла сразу и не требуется второй шаг для её определения, а во-вторых, на каждом шаге вызов функции Шаблон:Mvar происходит только один раз, а не три раза Шаблон:Sfn.

Следующая программа на языке 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

Подобно алгоритму черепахи и зайца, этот алгоритм является алгоритмом указателей, использующим Шаблон:Math проверок и вызовов функций и памяти Шаблон:Math. Несложно показать, что число вызовов функции никогда не превзойдёт числа вызовов в алгоритме Флойда.

Брент утверждает, что в среднем его алгоритм работает примерно на 36 % быстрее алгоритма Флойда, и что он обгоняет ро-алгоритм Полларда примерно на 24 %. Он осуществил Шаблон:Не переведено 5 вероятностной версии алгоритма, в котором последовательность индексов, проходимых медленным указателем, не является степенью двойки, а является степенью двойки, умноженной на случайный коэффициент. Хотя основной целью его алгоритма была разложение числа на множители, Брент также обсуждает приложение алгоритма для проверки псевдослучайных генераторовШаблон:Sfn.

Время в обмен на память

Много авторов изучали техники для нахождения цикла, использующих большее количество памяти, чем у методов Флойда и Брента, но, зато, работающих быстрее. В общем случае эти методы запоминают некоторые ранее вычисленные значения последовательности и проверяют, не совпадает ли новое значение с одним из запомненных. Чтобы делать это быстро, обычно они используют хеш-таблицы или подобные структуры данных, а потому такие алгоритмы не являются алгоритмами указателей (в частности, обычно их нельзя приспособить к ро-алгоритму Полларда). Чем эти методы отличаются, так это способом определения, какие значения запоминать. Следуя НивашуШаблон:Sfn, мы кратко рассмотрим эти техники.

БрентШаблон:Sfn уже описывал вариации своей техники, в которых индексы запомненных значений последовательности являются степенями числа Шаблон:Mvar, отличного от двух. При выборе Шаблон:Mvar ближе к единице и, запоминая значения последовательности с индексами, близкими к последовательным степеням Шаблон:Mvar, алгоритм нахождения цикла может использовать число вызовов функции, которое не превосходит произвольно малого множителя оптимального значения Шаблон:MathШаблон:SfnШаблон:Sfn.

Седжвик, Шиманьский и Яо Шаблон:Sfn предложили метод, который использует Шаблон:Mvar ячеек памяти и требует в худшем случае только <math>(\lambda+\mu)(1+cM^{-1/2})</math> вызовов функции с некоторой постоянной Шаблон:Mvar, для которой она показала оптимальность. Техника использует числовой параметр Шаблон:Mvar, запоминая в таблице только те позиции последовательности, которые кратны Шаблон:Mvar. Таблица очищается, а значение Шаблон:Mvar удваивается, если число запомненных значений слишком велико.

Некоторые авторы описали методы отмеченных точек, которые запоминают в таблице значения функции, опираясь на критерии, использующие значения, а не индексы (как в методе Седжвика и др.). Например, могут запоминаться значения по модулю от некоторого числа Шаблон:MvarШаблон:SfnШаблон:Sfn. Более просто, НивашШаблон:Sfn приписывает Вудруфу предложение запоминать случайно выбранное предыдущее значение, делая подходящий случайный выбор на каждом шаге.

НивашШаблон:Sfn описывает алгоритм, который не использует фиксированного количества памяти, но для которого ожидаемое количество используемой памяти (в предположении, что входная функция случайна) логарифмически зависит от длины последовательности. По этой технике элемент записывается в таблицу, если никакой предыдущий элемент не имеет меньшего значения. Как показал Ниваш, элементы в этой технике можно располагать в стеке, и каждое последующее значение нужно сравнивать только с элементом на вершине стека. Алгоритм прекращает работу, когда повторение элемента с меньшим значением найдено. Если использовать несколько стеков и случайную перестановку значений внутри каждого стека, получаем выигрыш в скорости за счёт памяти аналогично предыдущим алгоритмам. Однако даже версия алгоритма с одним стеком не является алгоритмом указателей, поскольку требуется знать, какое из значений меньше.

Любой алгоритм нахождения цикла, запоминающий максимум Шаблон:Mvar значений из входной последовательности, должен сделать по меньшей мере <math>(\lambda+\mu)(1+\frac{1}{M-1})</math> вызовов функцийШаблон:SfnШаблон:Sfn.

Приложения

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

Определение длины цикла генератора псевдослучайных чисел является одной из мер его силы. Об этом приложении говорил Кнут при описании метода ФлойдаШаблон:Sfn. БрентШаблон:Sfn описал результат тестирования линейного конгруэнтного генератора. Период генератора оказался существенно меньше афишированного. Для более сложных генераторов последовательность значений, в которых находят цикл, может не представлять вывод генератора, а лишь его внутреннее состояние.

Некоторые алгоритмы теории чисел опираются на нахождение цикла, включая ро-алгоритм Полларда для факторизации целых чиселШаблон:Sfn и связанный с ним алгоритм «кенгуру» для задачи дискретного логарифмированияШаблон:Sfn.

В криптографии возможность найти два различных значения xμ−1 и xλ+μ−1, отображающихся некоторой криптографической функцией ƒ в одно и то же значение xμ, может говорить о слабости ƒ. Например, Кискатр и ДелессаиллеШаблон:Sfn применили алгоритмы нахождения цикла для поиска сообщения и пары ключей DES, которые отображают это сообщение в одно и то же зашифрованное значение. Калиски, Ривест и Шаблон:Не переведено 5Шаблон:Sfn также использовали алгоритмы нахождения цикла для атаки на DES. Техника может быть использована для поиска коллизий в криптографической хеш-функцииШаблон:Sfn.

Нахождение циклов может быть полезно как путь обнаружения бесконечных циклов в некоторых типах компьютерных программШаблон:Sfn.

Периодические конфигурации в моделировании клеточного автомата можно найти, применив алгоритмы нахождения цикла к последовательности состояний автоматаШаблон:Sfn.

Шаблон:Не переведено 5 связных списков является техникой проверки корректности алгоритма, использующего эти структуры. Если узел в списке ссылается некорректно на более ранний узел в том же списке, структура образует цикл, который может быть найден с помощью таких алгоритмовШаблон:Sfn. В языке Common Lisp принтер S-выражений при переменной *print-circle* обнаруживает зацикленные списковые структуры и печатает их компактно.

ТескеШаблон:Sfn описывает приложение в вычислительной теории групп для вычисления структуры абелевой группы по множеству её генераторов. Криптографические алгоритмы Калиски и др.Шаблон:Sfn можно рассматривать также как попытку раскрыть структуру неизвестной группы.

ФичШаблон:Sfn коротко упомянула применение для компьютерного моделирования небесной механики, которое она приписывает Кэхэну. В этом приложении нахождение цикла в фазововом пространстве системы орбит можно использовать для определения, является ли система периодической с точностью моделиШаблон:Sfn.

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Нахождение_цикла&oldid=10447931