В інформатиці виявлення циклу — це алгоритмічна задача пошуку циклу в послідовності ітераційних значень функції.
Для будь-якої функції , яка відображає скінченну множину на саму себе, і будь-якого початкового значення з , послідовність ітераційних значень функції
зрештою буде двічі використовувати одне й те ж значення, тобто знайдеться пара різних індексів та таких, що . Як тільки це трапиться, послідовність буде періодично продовжуватися, повторюючи ту саму послідовність значень від до . Виявлення циклу — це задача пошуку та для заданих та .
Відомо кілька алгоритмів швидкого знаходження циклів з незначним використанням пам'яті. Алгоритм черепахи та зайця Роберта У. Флойда переміщує два вказівника з різною швидкістю по послідовності значень, поки обидва не вкажуть на рівні значення. Алгоритм Брента базується на ідеї . Алгоритми Флойда і Брента використовують сталий об'єм пам'яті, а кількість разів обчислення значеннь функції пропорційна відстані від початку послідовності до першого повторення. Кілька інших алгоритмів використовують більший об'єм пам'яті для меншої кількості обчислень значень функції.
Серед застосунків виявлення циклів є перевірка якості генераторів псевдовипадкових чисел та криптографічних хеш-функцій, алгоритмів обчислювальної теорії чисел, виявлення нескінченних циклів у комп'ютерних програмах та періодичних конфігурацій у клітинних автоматах, автоматизований в таких структурах даних, як зв'язаний список, взаємне блокування при обробці транзакцій в СУБД.
Приклад
На малюнку показана функція , яка відображає множину } саму до себе. Якщо починати з і послідовно знаходити , отримаємо послідовність значень функції:
Циклом у цій послідовності буде підпослідовність .
Визначення Нехай — будь-яка скінченна множина, — будь-яка функція, що відображає на саму себе, — будь-який елемент з . Для будь-якого нехай . Нехай — найменший індекс, для якого значення знову з'являється нескінченно часто в межах послідовності значень , а (довжина петлі) — це найменше натуральне число, що . Проблема виявлення циклу — це задача пошуку і ..
Цю ж задачу розглянемо с точки зору теорії графів: побудуємо орієнтований граф (у якому кожна вершина має єдине вихідне ребро), якому відповідає граф функції нашої задачі, та вершинами якого є елементи множини , а ребра якого відображають елемент на відповідне значення функції, як показано на малюнку. Набір вершин доступних від початкової вершини утворюють підграф форми, що нагадує грецьку букву rho (): шлях довжини від до цикла, який складається з вершин..
Комп'ютерне представлення Як правило, не буде вказано таблицею значень, як це показано на малюнку вище. Швидше за все, алгоритму виявлення циклу може бути наданий доступ або до послідовності значень , або до підпрограми для обчислення . Завдання полягає в тому, щоб знайти і , перевіряючи якомога менше значень з послідовності або виконуючи якомога менше викликів підпрограм. Як правило, також важлива просторова складність алгоритму для проблеми виявлення циклу: бажано вирішити цю проблему, використовуючи обсяг пам'яті, значно менший, ніж потрібно для збереження всієї послідовності.
У деяких додатках, і зокрема в ρ-алгоритм Полларда для факторізації цілих чисел, алгоритм має набагато обмежений доступ до та . Наприклад, в ρ-алгоритмі Полларда — це набір цілих чисел за модулем невідомого простого множника числа, що підлягає факторизації, тому навіть розмір невідомий алгоритму. Щоб дозволити алгоритмам виявлення циклу використовувати такі обмежені знання, вони можуть бути розроблені на основі наступних можливостей. Спочатку передбачається, що алгоритм має у своїй пам'яті об'єкт, що представляє вказівник на початкове значення . На будь-якому етапі він може виконати одну з трьох дій: він може скопіювати будь-який вказівник, який він має, на інший об'єкт у пам'яті, він може застосувати і замінити будь-який з його покажчиків на вказівник на наступний об'єкт у послідовності, або він може застосувати підпрограма для визначення того, чи є два її покажчики рівними значеннями в послідовності. Дія тестування рівності може включати деякі нетривіальні обчислення: наприклад, в ρ-алгоритмі Полларда це реалізується шляхом перевірки того, чи має різниця між двома збереженими значеннями нетривіальний найбільший спільний дільник з числом, яке потрібно врахувати. У цьому контексті, за аналогією до моделі обчислень , алгоритм, який використовує лише копіювання покажчика, просування в межах послідовності та тести рівності, можна назвати алгоритмом покажчика.
Алгоритми Якщо вхід подається як підпрограма для обчислення , задачу виявлення циклу можна тривіально вирішити, використовуючи лише , просто обчисливши послідовність значень та використовуючи структуру даних, таку як хеш-таблицю для їх зберігання значення та перевірити, чи кожне наступне значення вже збережено. Проте просторова складність цього алгоритму пропорційна , надмірно велика. Крім того, для реалізації цього методу як знадобиться застосувати тест рівності до кожної пари значень, що призведе до загального квадратичного часу. Таким чином, дослідження в цій галузі зосереджені на двох цілях: використати менше місця, ніж цей наївний алгоритм, і знайти алгоритми покажчиків, які використовують менше тестів рівності.
Черепаха і заєць Флойда
Алгоритм пошуку циклу Флойда — це алгоритм покажчиків, який використовує лише два покажчики, які рухаються по послідовності з різною швидкістю. Його також називають «алгоритмом черепахи та зайця», натякаючи на байку Езопа про «Черепаху та зайця».
Алгоритм названий на честь Роберта У. Флойда, якому його винахід приписував Дональд Кнут.Handbook of Applied Cryptography, by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, p. 125 , describes this algorithm and others Однак алгоритм не з'являється у опублікованій роботі Флойда, і це може бути хибним віднесенням: Флойд описує алгоритми перерахування всіх простих циклів в орієнтованому графі у роботі 1967 року але ця робота не описує проблему пошуку циклу у графах функцій, що є темою цієї статті. Насправді, твердження Кнута (1969 року), яке він приписує Флойду без цитування, є першим відомим згадуванням у друкованому вигляді, і, отже, він може належати до і не належати окремій особі.The Hash Function BLAKE, by Jean-Philippe Aumasson, Willi Meier, Raphael C.-W. Phan, Luca Henzen (2015), p. 21 , footnote 8
Ключове розуміння алгоритму наступне. Якщо існує цикл, то для будь-яких цілих чисел і , , де — довжина петлі, яку потрібно знайти, а — індекс першого елемента циклу. Виходячи з цього, тоді можна показати, що для деякого тоді і тільки тоді, коли .
Таким чином, алгоритму потрібно лише перевірити наявність повторюваних значень цієї спеціальної форми, одна вдвічі далі від початку послідовності, ніж інша, щоб знайти період повторення, кратний . Як тільки буде знайдено, алгоритм відновлює послідовність від її початку, щоб знайти перше повторене значення у послідовності, використовуючи той факт, що ділить і, отже, . Нарешті, як тільки значення стало відомим, тривіально знайти довжину найкоротшого повторюваного циклу шляхом пошуку першого положення для якого .
Таким чином, алгоритм утримує два вказівники у даній послідовності: один (черепаха) у точці , а інший (заєць) у точці . На кожному кроці алгоритму він збільшується на один, рухаючи черепаху на один крок вперед, а зайця на два кроки вперед у послідовності, а потім порівнює значення послідовності за цими двома вказівниками. Найменше значення для якого черепаха та заєць вказують на рівні значення, є бажаним значенням .
Наступний код Python показує, як ця ідея може бути реалізована як алгоритм.def floyd(f, x0): # Основна фаза алгоритму: пошук повторень x_i = x_2i. # Заєць рухається вдвічі швидше черепахи та # відстань між ними збільшується на 1 на кожному кроці. # Врешті -решт вони обидва опиняться всередині циклу, а потім, # в певний момент відстань між ними буде # ділиться на крапку λ. tortoise = 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) # Заєць і черепаха рухаються з однаковою швидкістюd mu += 1
# Знайдіть довжину найкоротшого циклу, починаючи з x_μ # Заєць рухається крок за кроком, поки черепаха нерухома. # lam збільшується, поки не знайдеться λ.
lam = 1 hare = f(tortoise) while tortoise != hare: hare = f(hare) lam += 1
return lam, muЦей код звертається лише до послідовності шляхом зберігання та копіювання покажчиків, оцінок функцій та тестів рівності; тому він кваліфікується як алгоритм вказівників. Алгоритм використовує цих типів та простір для зберігання., Section 7.1.1, Floyd's cycle-finding algorithm, pp. 225—226.
Алгоритм Брента описав альтернативний алгоритм виявлення циклу, який, як і алгоритм черепахи та зайця, вимагає лише двох вказівників у послідовності.. Однак він базується на іншому принципі: пошук найменшої потужності з двох , більшої як за і за .
Для , алгоритм порівнює з кожним наступним значенням послідовності до наступного степеня двох, зупиняючись, коли знаходить відповідність. Він має дві переваги порівняно з алгоритмом черепахи та зайця: він безпосередньо знаходить правильну довжину циклу, замість того, щоб шукати його на наступному етапі, а його кроки передбачають лише одну оцінку , а не три., Section 7.1.2, Brent's cycle-finding algorithm, pp. 226—227.
Наступний код 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 for i in range(lam): # range(lam) створює список зі значеннями 0, 1, ..., lam-1 hare = f(hare) # Відстань між зайцем і черепахою тепер λ.
# Далі заєць і черепаха рухаються з однаковою швидкістю, поки вони не домовляться mu = 0 while tortoise != hare: tortoise = f(tortoise) hare = f(hare) mu += 1
return lam, muЯк і алгоритм черепахи та зайця, це алгоритм вказівників, який використовує та оцінки функцій та простір для зберігання. Не важко показати, що кількість оцінок функцій ніколи не може бути вище, ніж для алгоритму Флойда. Брент стверджує, що в середньому його алгоритм пошуку циклу працює приблизно на 36 % швидше, ніж алгоритм Флойда, і що він швидше ρ-алгоритму Полларда приблизно на 24 %. Він також виконує для рандомізованої версії алгоритму, в якому послідовність індексів, відстежена повільнішим із двох покажчиків, — це не повноваження двох самих, а скоріше рандомізоване кратне ступеням двох. Хоча його основне призначення — алгоритми цілочисельної факторизації, Брент також обговорює застосування для тестування генераторів псевдовипадкових чисел.
Алгоритм Госпера Алгоритм знаходить період і нижню і верхню межу вихідної точки першого циклу. Різниця між нижньою та верхньою межею має той самий порядок, що й період, наприклад. .