Детекција циклуса

У рачунарској науци, детекција циклуса је алгоритамски проблем проналажења циклуса у секвенци итеративних вредности функције.

За било коју функцију ƒ која мапира коначни скуп S за себе, и било која иницијална вредност x₀ у S, секвенца итеративних вредности функције

$x_{0},\ x_{1}=f(x_{0}),\ x_{2}=f(x_{1}),\ \dots ,\ x_{i}=f(x_{i-1}),\ \dots$

мора на крају да искористи исту вредност два пута: мора бити неко i ≠ j такво да x_i = x_j. Једном када се то догоди, секвенца мора периодично да се настави, понављајући исте вредности од x_i до x_j−1. Детекција циклуса је проблем проналажења i и j, за дато ƒ и x₀.

Пример

A function from and to the set {0,1,2,3,4,5,6,7,8} and the corresponding functional graph

Фигура показује функцију ƒ која мапира сет S = {0,1,2,3,4,5,6,7,8} за себе. ако нека креће од x₀ = 2 и у више наврата примењује ƒ, она види секвенцу вредности

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

Циклус у је у овом случају 6, 3, 1.

Дефиниције

Нека S буде било који коначни скуп, ƒ било која функција од S за себе, и x₀ било који елемент S. За свако i > 0, нека је x_i = ƒ(x_i−1). Нека је μ најмањи индекс такав да се вредност x_μ поновно појављује бесконачно често унутар секвенце вредности x_i, и нека је λ (дужина циклуса) најмањи позитивни цео број такав да x_μ = x_λ+μ. Проблем детекције циклуса је задатак тражења λ и μ.

Исти проблем можемо гледати из угла теорије графова, конструишући функционални граф (што значи, усмерени граф у којем свако теме има једну одлазну ивицу) чија темена су елементи од S и ивице које пресликавају елемент на одговарајућу вредност функције, као што је приказано. Скуп темена достижних од било којег стартног темена x₀ из подграфа облика који личи на грчко слово ро(ρ): пут дужине μ од x₀ у циклусу од λ темена.

Рачунарска репрезентација

Генерално, ƒ неће бити специфицирано као списак вредности, као што је дато изнад. Него, или нам је дат приступ секвенци вредности x_i, или подрутини за рачунање ƒ. Задатак је да се пронађеλ и μ проверавајући што мање вредности из секвенце или извођењем што је могуће мање подрутинских позива. Типично, такође, временска комплексност алгоритма за проблем детекције циклуса није важна: желимо да решимо проблем док користимо меморију знатно мању него што је потребно да се смести цела секвенца.

У неким применама, и у Pollard's rho алгоритму за факторизацију целих бројева, алгоритам има много више ограниченог приступа S и ƒ. У Pollard's rho алгоритму, на пример, S је сет целих бројева модулованих са непознатим простим фактором да би се број факторизовао, тако чак и величина S је непозната алгоритму.

Можемо гледати на алгоритам за детекцију циклуса у овој примени као имање следећих могућности: он иницијално има у својој меморији објекат који репрезентује показивач на почетну вредност x₀. У било ком кораку, може извести три акције: може да копира било који показивач који има на други објекат у меморији, може да примени ƒ и замени било који од својих показивача са показивачем на следећи објекат у секвенци, или може да примени подрутину за одређивање да ли два његова показивача представљају исте вредности у секвенци. Акција тестирања једнакости може да укључује неке нетривијалне компутације: у Pollard's rho алгоритму, је то имплементирано тестирањем да ли разлика између две убачене вредности има нетривијални gcd са бројем са којим треба да се факторише. У овом контексту, позваћемо алгоритам који користи само копирање показивача, напредак унутар секвенце, и тестове једнакости с показивачким алгоритмом.

Алгоритми

Ако је улаз дат као подрутина за израчунавање ƒ, проблем детекције циклуса може бити тривијално решен коришћењем само λ+μ у функцији, једноставно рачунањем секвенце вредности x_i и коришћењем структуре података као што је хеш мапа да се чувају ове вредности и тестира да ли је свака следећа вредност већ сачувана. Међутим, просторна комплексност овог алгоритма је λ+μ, непотребно велика. Додатно, да би се имплементирала ова метода као показивачки алгоритам било би потребно да се примени тест једнакости за сваки пар вредности, резултујући укупном квадратном времену. Тако, истраживање у овој области се концентрисало на два циља: коришћење мање простора него што користи овај наивни алгоритам, и проналажење показивачких алгоритама који користе мање тестова једнакости.

Корњача и зец

Floyd's "tortoise and hare" cycle detection algorithm, applied to the sequence 2, 0, 6, 3, 1, 6, 3, 1, ...

Флојдов алгоритам за проналажење циклуса, такође познат као "алгоритам корњача и зец", алудирајући на Езопову басну о корњачи и зецу, је показивачки алгоритам који користи два показивача, који се померају кроз секвенцу различитим брзинама.

Алгоритам је назван по Robert W. Floyd, који је награђен за свој изум од стране Donald Knuth. Међутим, алгоритам се не појављује у Флојдовом објављеном раду, и ово може бити мисатрибуција: Флојд описује алгоритме за слагање свих једноставних циклуса у усмереном графу у објави 1967 године, али ова објава не описује проблем проналажења циклуса у функционалним графовима који су предмет овог чланка. Заправо, Кунтова изјава (у 1969), приписујући је Флојду, без цитата, је прво познато појављивање у штампи, и ово може заправо бити фолкова теорема, неприписива на једног  индивидуалца.

Кључни увид у алгоритам је то да за било којицео број i ≥ μ и k ≥ 0, x_i = x_{i + kλ}, где λ је дужина пронађеног циклуса и μ је индекс првог елемента у циклусу. Нарочито, кад год i = kλ ≥ μ, следи да је x_i = x_2i. Тако, алгоритам треба само да провери понављајуће вредности специјалне форме, једне дупло даље од почетка секвенце него друга, да би пронашли период ν понављања које се множи са λ. Када се ν пронађе, алгоритам се враћа на почетак секвенце да би пронашао своју прву понављајућу вредност  x_μ у секвенци, користећи чињеницу да λ дели ν и премда је x_μ = x_{μ + v}. Коначно, једном када је вредност μ позната тривијално је пронћи дужину λ најкраћег понављајућег циклуса, проналажењем прве позиције μ + λ за коју је x_{μ + λ} = x_μ.

Тако алгоритам одржава два показивача у датој секвенци, једног (корњачу) на x_i, и други (зеца) на x_2i. На сваком кораку алгориитма, он повећава i за један, померајући корњачу један корак унапред и зеца два корака унапред у секвенци, и онда упоређује вредности секвенце на које показују ова два показивача. Најмања вредност i > 0 за коју и корњача и зец показују исту вредност је жељена вредност ν.

Следећи Python код показује како ова идеја може бити имплементирана као алгоритам.

def floyd(f, x0):
    # Main phase of algorithm: finding a repetition x_i = x_2i
    # The hare moves twice as quickly as the tortoise and
    # the distance between them increases by 1 at each step.
    # Eventually they will both be inside the cycle and then,
    # at some point, the distance between them will be
    # divisible by the period λ.
    tortoise = f(x0) # f(x0) is the element/node next to x0.
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))
  
    # At this point the tortoise position, ν, which is also equal
    # to the distance between hare and tortoise, is divisible by
    # the period λ. So hare moving in circle one step at a time, 
    # and tortoise (reset to x0) moving towards the circle, will 
    # intersect at the beginning of the circle. Because the 
    # distance between them is constant at 2ν, a multiple of λ,
    # they will agree as soon as the tortoise reaches index μ.

    # Find the position μ of first repetition.    
    mu = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)   # Hare and tortoise move at same speed
        mu += 1
 
    # Find the length of the shortest cycle starting from x_μ
    # The hare moves one step at a time while tortoise is still.
    # lam is incremented until λ is found.
    lam = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        lam += 1
 
    return lam, mu

Овај код приступа секвенци само чувајући и копирајући показиваче, евалуациије функције, и тестове једнакости; премда, квалификује се као показивачки алгоритам. Алгоритам користи O(λ + μ) операција ових типова, и O(1) места за чување.

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

Richard P. Brent је описао алтернативни алгоритам за детекцију циклуса, који као корњача и зец алгоритам, захтева само два показивача у секвенци. Међутим, заснован је на друачијем принципу: тражењем најмањег квадрата 2ⁱ који је већи од λ и μ. За i = 0, 1, 2, итд., алгоритам упоређује x_2ⁱ−1 са сваком следећом вредношћу секвенце до следећег квадрата, стајући када пронађе подударање. Има две предности у односу на алгоритам корњаче и зеца: проналази тачну дужину λ циклуса директно, пре него да треба да га пронађе у наредној фази, и његови кораци укључују само једну евалуацију ƒ пре него три.

Следећи Python код показује како ова техника ради детаљније.

def brent(f, x0):
    # main phase: search successive powers of two
    power = lam = 1
    tortoise = x0
    hare = f(x0)  # f(x0) is the element/node next to x0.
    while tortoise != hare:
        if power == lam:  # time to start a new power of two?
            tortoise = hare
            power *= 2
            lam = 0
        hare = f(hare)
        lam += 1

    # Find the position of the first repetition of length λ
    mu = 0
    tortoise = hare = x0
    for i in range(lam):
    # range(lam) produces a list with the values 0, 1, ... , lam-1
        hare = f(hare)
    # The distance between the hare and tortoise is now λ.

    # Next, the hare and tortoise move at same speed till they agree
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        mu += 1
 
    return lam, mu

Као алгоритам корњача и зец, ово је показивачки алгоритам који користи O(λ + μ) тестова и евалуација функције и O(1) меморије. Није тешко показати да број евалуација функције никада не може да буде већи од Флојдовог алгоритма. Брент тврди да, у просеку, његов алгоритам за проналажење циклуса ради око 36% брже него Флојдов и да убрзава Pollard rho алгоритам за око 24%. Он такође изводи анализу просечног случаја за насумичну верзију алгоритма у којој секвенца индекса праћена од стране споријег од два показивача није квадрат њих двоје, него насумичан садржалац квадрата. Иако је његова главна намеравајућа апликација била у алгоритмима за факторизацију целих бројева, Брент такође дискутује примене у тестирању псеудонасумичних генератора бројева.

Време-простор размене

Мноштво аутора су проучавали технике детекције циклуса за детекцију циклуса која користи мање меморије од Флојдовог и Брентовог алгоритма, али да детектују циклус брже. Генерално ове методе чувају неколико претходно израчунатих вредности секвенце, и тестирају да ли је свака нова вредност једнака некој од претходно израчунатих вредности. Да би радили тако брзо, често користе хеш табелеили сличне структуре података за складиштење претходно израчунатих вредности, и премда нису показивачки алгоритми: нарочито, они обично не могу да буду примењени у Pollard's rho алгоритму. Где се ове методе разликују је то како одлучују коју вредност да чувају. Пратећи Nivasch, прегледали смо укратко ове технике.

• Брент већ описује варијације своје технике у којима се индекси запамћене секвенце где су вредности квадрати броја R различитог од два. Бирајући R да буде број близу јединице, и чувајући вредности секвенце на тим индексима који су близу секвенце узастопних квадрата од R, алгоритам за детекцију циклуса може да користи број евалуација функције које су у арбитрарно малом фактору оптимума λ+μ.

• Sedgewick, Szymanski, и Yao су допринели метод који користи M меморијских ћелија и захтева у најгорем случају само $(\lambda +\mu )(1+cM^{-1/2})$ евалуација функције, за неку константу c, за коју они показују да је оптимална. Техника укључује задржавање нумеричког параметра  d, чувајући у табели само оне позиције у секвенци које су множиоци d, и чишћењем табеле и удвостручавањем d  кад год је превише вредности сачувано.

• Неколико аутора су описали истакнуте показивачке методе које чувају вредности функције у табели засновано на критеријуму укључујући вредности, пре него (као што је метод Sedgewick et al.) засновано на њиховим позицијама. На пример, вредности једнаке нули по моду неке вредности d могу бити сачуване. Једноставније, Nivasch похваљује D. P. Woodruff са сугестијом чувања насумичног примерка претходно виђених вредности, стварајући одговарајући насумични избор на сваком кораку тако да узорак остаје насумичан.

• Nivasch описује алгоритам који не користи фиксирану количину меморије, али за који је очекивана количина меморије искоришћена (под претпоставком да је улазна функциа насумична) је логаритамска у дужини секвенце. Предмет сачуван у меморијској табели, са овом техником, када ниједан каснији предмет нема мању вредност. Како Nivasch показује, предмети овом техником могу бити одржавани коришћењем стек структуре података, и свака следећа вредност секвенце треба да се упореди са врхом стека. Алгоритам се завршава када се пронађе поновљен елемент секвенце са најмањом вредности. Користећи исти алгоритам са више стекова, користећи насумичне пермутације вредности да би се преместиле вредности у стеку, дозвољава време-простор размену сличну претходним алгоритмима. Међутим, чак и верзије алгоритма са једним стеком није поинтерски алгоритам, због поређења потребног да се одреди која од две вредности је мања.

Било који алгоритам за детекцију циклуса кои чува највише M вредности од улазне секвенце мора да изврши бар $\scriptstyle (\lambda +\mu )(1+{\frac {1}{M-1}})$ евалуација функције.

Примене

Детекција циклуса се користи у пуно примена.

• Одређивање дужине циклуса псеудонасумичног генератора бројева је једна мера његове снаге. Ово је примена цитирана од стране Кунта описујући Флојдов метод. Брент описује резултате тестирања  линеарног конгруенцијског генератора у овом погледу; испоставило се да је његов период знатно мањи него што се причало. За комплексније генераторе, секвенца вредности у којој пронађени циклус не мора да репрезентује излаз  генератора, него његово унутрашње стање.
• Неколико бројно теоретских алгоритама се заснива на детекцији циклуса, укључујући Pollard's rho алгоритам за факторизацију целих бројева и повезан је са кенгур алгоритмом за проблем дискретног логаритма.
• У криптографијским применама, могућност да се пронађу две сличне вредности x_μ−-1 и x_λ+μ−-1 пресликаниих уз помоћ неке криптографске функције ƒ за исту вредност x_μ може да индикује слабост у ƒ. На пример, Quisquater и Delescaille примењују алгоритме за детекцију циклуса у потрази за поруком и паром Data Encryption Standard кључева који мапирају ту поруку на исту енкриптовану вредност; Kaliski, Rivest, и Sherman такође користе алгоритме за детекцију циклуса да нападну DES. Техника такође може бити искоришћена да се пронађе судар у криптографској хеш функцији.
• Детекција циклуса може бити од помоћи као начин откривања бесконачних петљи у одређеним типовима рачунарских програма.
• Периодичне конфигурације у симулирању целуларне аутоматизације могу бити пронађене применом алгоритама за детекцију циклуса на секвенци аутоматонских стања.
• Анализа облика структуре података повезаних листа је техника за верификовање исправности алгоритма коришћењем ових структура. Ако чвор у листи неправилно показује на претходни чвор у истој листи, структура ће формирати циклус кои може бити детектован од стране ових алгоритама.
• Teske описује примене у теорији рачунања група: проверавајући структуру Абелове групе из сета његових генератора. Криптографски алгоритми Kaliski et al. могу такође бити посматрани као покушавање  да се закључи структура непознате групе.
• Fich укратко помиње примену у рачунарској симулацији целестијалне механике, коју она приписује William Kahan. У овој примени, детекција циклуса у фазном простору орбиталног система може бити искоришћена да се одреди да ли је систем периодичан унутар прецизности симулације.
• У Common Lisp, S-expression штампач, под контролом *print-circle* променљиве, детектује циркуларну структуру листе и штампа је компактно.

Спољашње везе

• Gabriel Nivasch, The Cycle Detection Problem and the Stack Algorithm
• Tortoise and Hare, Portland Pattern Repository
• Floyd's Cycle Detection Algorithm (The Tortoise and the Hare)
• Brent's Cycle Detection Algorithm (The Teleporting Turtle)