Detekcija ciklusa

U računarskoj nauci, detekcija ciklusa je algoritamski problem pronalaženja ciklusa u sekvenci iterativnih vrednosti funkcije.

Za bilo koju funkciju ƒ koja mapira konačni skup S za sebe, i bilo koja inicijalna vrednost x₀ u S, sekvenca iterativnih vrednosti funkcije

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

mora na kraju da iskoristi istu vrednost dva puta: mora biti neko i ≠ j takvo da x_i = x_j. Jednom kada se to dogodi, sekvenca mora periodično da se nastavi, ponavljajući iste vrednosti od x_i do x_j−1. Detekcija ciklusa je problem pronalaženja i i j, za dato ƒ i x₀.

Primer

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

Figura pokazuje funkciju ƒ koja mapira set S = {0,1,2,3,4,5,6,7,8} za sebe. ako neka kreće od x₀ = 2 i u više navrata primenjuje ƒ, ona vidi sekvencu vrednosti

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

Ciklus u je u ovom slučaju 6, 3, 1.

Definicije

Neka S bude bilo koji konačni skup, ƒ bilo koja funkcija od S za sebe, i x₀ bilo koji element S. Za svako i > 0, neka je x_i = ƒ(x_i−1). Neka je μ najmanji indeks takav da se vrednost x_μ ponovno pojavljuje beskonačno često unutar sekvence vrednosti x_i, i neka je λ (dužina ciklusa) najmanji pozitivni ceo broj takav da x_μ = x_λ+μ. Problem detekcije ciklusa je zadatak traženja λ i μ.

Isti problem možemo gledati iz ugla teorije grafova, konstruišući funkcionalni graf (što znači, usmereni graf u kojem svako teme ima jednu odlaznu ivicu) čija temena su elementi od S i ivice koje preslikavaju element na odgovarajuću vrednost funkcije, kao što je prikazano. Skup temena dostižnih od bilo kojeg startnog temena x₀ iz podgrafa oblika koji liči na grčko slovo ro(ρ): put dužine μ od x₀ u ciklusu od λ temena.

Računarska reprezentacija

Generalno, ƒ neće biti specificirano kao spisak vrednosti, kao što je dato iznad. Nego, ili nam je dat pristup sekvenci vrednosti x_i, ili podrutini za računanje ƒ. Zadatak je da se pronađeλ i μ proveravajući što manje vrednosti iz sekvence ili izvođenjem što je moguće manje podrutinskih poziva. Tipično, takođe, vremenska kompleksnost algoritma za problem detekcije ciklusa nije važna: želimo da rešimo problem dok koristimo memoriju znatno manju nego što je potrebno da se smesti cela sekvenca.

U nekim primenama, i u Pollard's rho algoritmu za faktorizaciju celih brojeva, algoritam ima mnogo više ograničenog pristupa S i ƒ. U Pollard's rho algoritmu, na primer, S je set celih brojeva modulovanih sa nepoznatim prostim faktorom da bi se broj faktorizovao, tako čak i veličina S je nepoznata algoritmu.

Možemo gledati na algoritam za detekciju ciklusa u ovoj primeni kao imanje sledećih mogućnosti: on inicijalno ima u svojoj memoriji objekat koji reprezentuje pokazivač na početnu vrednost x₀. U bilo kom koraku, može izvesti tri akcije: može da kopira bilo koji pokazivač koji ima na drugi objekat u memoriji, može da primeni ƒ i zameni bilo koji od svojih pokazivača sa pokazivačem na sledeći objekat u sekvenci, ili može da primeni podrutinu za određivanje da li dva njegova pokazivača predstavljaju iste vrednosti u sekvenci. Akcija testiranja jednakosti može da uključuje neke netrivijalne komputacije: u Pollard's rho algoritmu, je to implementirano testiranjem da li razlika između dve ubačene vrednosti ima netrivijalni gcd sa brojem sa kojim treba da se faktoriše. U ovom kontekstu, pozvaćemo algoritam koji koristi samo kopiranje pokazivača, napredak unutar sekvence, i testove jednakosti s pokazivačkim algoritmom.

Algoritmi

Ako je ulaz dat kao podrutina za izračunavanje ƒ, problem detekcije ciklusa može biti trivijalno rešen korišćenjem samo λ+μ u funkciji, jednostavno računanjem sekvence vrednosti x_i i korišćenjem strukture podataka kao što je heš mapa da se čuvaju ove vrednosti i testira da li je svaka sledeća vrednost već sačuvana. Međutim, prostorna kompleksnost ovog algoritma je λ+μ, nepotrebno velika. Dodatno, da bi se implementirala ova metoda kao pokazivački algoritam bilo bi potrebno da se primeni test jednakosti za svaki par vrednosti, rezultujući ukupnom kvadratnom vremenu. Tako, istraživanje u ovoj oblasti se koncentrisalo na dva cilja: korišćenje manje prostora nego što koristi ovaj naivni algoritam, i pronalaženje pokazivačkih algoritama koji koriste manje testova jednakosti.

Kornjača i zec

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

Flojdov algoritam za pronalaženje ciklusa, takođe poznat kao "algoritam kornjača i zec", aludirajući na Ezopovu basnu o kornjači i zecu, je pokazivački algoritam koji koristi dva pokazivača, koji se pomeraju kroz sekvencu različitim brzinama.

Algoritam je nazvan po Robert W. Floyd, koji je nagrađen za svoj izum od strane Donald Knuth. Međutim, algoritam se ne pojavljuje u Flojdovom objavljenom radu, i ovo može biti misatribucija: Flojd opisuje algoritme za slaganje svih jednostavnih ciklusa u usmerenom grafu u objavi 1967 godine, ali ova objava ne opisuje problem pronalaženja ciklusa u funkcionalnim grafovima koji su predmet ovog članka. Zapravo, Kuntova izjava (u 1969), pripisujući je Flojdu, bez citata, je prvo poznato pojavljivanje u štampi, i ovo može zapravo biti folkova teorema, nepripisiva na jednog  individualca.

Ključni uvid u algoritam je to da za bilo kojiceo broj i ≥ μ i k ≥ 0, x_i = x_{i + kλ}, gde λ je dužina pronađenog ciklusa i μ je indeks prvog elementa u ciklusu. Naročito, kad god i = kλ ≥ μ, sledi da je x_i = x_2i. Tako, algoritam treba samo da proveri ponavljajuće vrednosti specijalne forme, jedne duplo dalje od početka sekvence nego druga, da bi pronašli period ν ponavljanja koje se množi sa λ. Kada se ν pronađe, algoritam se vraća na početak sekvence da bi pronašao svoju prvu ponavljajuću vrednost  x_μ u sekvenci, koristeći činjenicu da λ deli ν i premda je x_μ = x_{μ + v}. Konačno, jednom kada je vrednost μ poznata trivijalno je pronći dužinu λ najkraćeg ponavljajućeg ciklusa, pronalaženjem prve pozicije μ + λ za koju je x_{μ + λ} = x_μ.

Tako algoritam održava dva pokazivača u datoj sekvenci, jednog (kornjaču) na x_i, i drugi (zeca) na x_2i. Na svakom koraku algoriitma, on povećava i za jedan, pomerajući kornjaču jedan korak unapred i zeca dva koraka unapred u sekvenci, i onda upoređuje vrednosti sekvence na koje pokazuju ova dva pokazivača. Najmanja vrednost i > 0 za koju i kornjača i zec pokazuju istu vrednost je željena vrednost ν.

Sledeći Python kod pokazuje kako ova ideja može biti implementirana kao algoritam.

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

Ovaj kod pristupa sekvenci samo čuvajući i kopirajući pokazivače, evaluaciije funkcije, i testove jednakosti; premda, kvalifikuje se kao pokazivački algoritam. Algoritam koristi O(λ + μ) operacija ovih tipova, i O(1) mesta za čuvanje.

Brentov algoritam

Richard P. Brent je opisao alternativni algoritam za detekciju ciklusa, koji kao kornjača i zec algoritam, zahteva samo dva pokazivača u sekvenci. Međutim, zasnovan je na druačijem principu: traženjem najmanjeg kvadrata 2ⁱ koji je veći od λ i μ. Za i = 0, 1, 2, itd., algoritam upoređuje x_2ⁱ−1 sa svakom sledećom vrednošću sekvence do sledećeg kvadrata, stajući kada pronađe podudaranje. Ima dve prednosti u odnosu na algoritam kornjače i zeca: pronalazi tačnu dužinu λ ciklusa direktno, pre nego da treba da ga pronađe u narednoj fazi, i njegovi koraci uključuju samo jednu evaluaciju ƒ pre nego tri.

Sledeći Python kod pokazuje kako ova tehnika radi detaljnije.

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

Kao algoritam kornjača i zec, ovo je pokazivački algoritam koji koristi O(λ + μ) testova i evaluacija funkcije i O(1) memorije. Nije teško pokazati da broj evaluacija funkcije nikada ne može da bude veći od Flojdovog algoritma. Brent tvrdi da, u proseku, njegov algoritam za pronalaženje ciklusa radi oko 36% brže nego Flojdov i da ubrzava Pollard rho algoritam za oko 24%. On takođe izvodi analizu prosečnog slučaja za nasumičnu verziju algoritma u kojoj sekvenca indeksa praćena od strane sporijeg od dva pokazivača nije kvadrat njih dvoje, nego nasumičan sadržalac kvadrata. Iako je njegova glavna nameravajuća aplikacija bila u algoritmima za faktorizaciju celih brojeva, Brent takođe diskutuje primene u testiranju pseudonasumičnih generatora brojeva.

Vreme-prostor razmene

Mnoštvo autora su proučavali tehnike detekcije ciklusa za detekciju ciklusa koja koristi manje memorije od Flojdovog i Brentovog algoritma, ali da detektuju ciklus brže. Generalno ove metode čuvaju nekoliko prethodno izračunatih vrednosti sekvence, i testiraju da li je svaka nova vrednost jednaka nekoj od prethodno izračunatih vrednosti. Da bi radili tako brzo, često koriste heš tabeleili slične strukture podataka za skladištenje prethodno izračunatih vrednosti, i premda nisu pokazivački algoritmi: naročito, oni obično ne mogu da budu primenjeni u Pollard's rho algoritmu. Gde se ove metode razlikuju je to kako odlučuju koju vrednost da čuvaju. Prateći Nivasch, pregledali smo ukratko ove tehnike.

• Brent već opisuje varijacije svoje tehnike u kojima se indeksi zapamćene sekvence gde su vrednosti kvadrati broja R različitog od dva. Birajući R da bude broj blizu jedinice, i čuvajući vrednosti sekvence na tim indeksima koji su blizu sekvence uzastopnih kvadrata od R, algoritam za detekciju ciklusa može da koristi broj evaluacija funkcije koje su u arbitrarno malom faktoru optimuma λ+μ.

• Sedgewick, Szymanski, i Yao su doprineli metod koji koristi M memorijskih ćelija i zahteva u najgorem slučaju samo $(\lambda +\mu )(1+cM^{-1/2})$ evaluacija funkcije, za neku konstantu c, za koju oni pokazuju da je optimalna. Tehnika uključuje zadržavanje numeričkog parametra  d, čuvajući u tabeli samo one pozicije u sekvenci koje su množioci d, i čišćenjem tabele i udvostručavanjem d  kad god je previše vrednosti sačuvano.

• Nekoliko autora su opisali istaknute pokazivačke metode koje čuvaju vrednosti funkcije u tabeli zasnovano na kriterijumu uključujući vrednosti, pre nego (kao što je metod Sedgewick et al.) zasnovano na njihovim pozicijama. Na primer, vrednosti jednake nuli po modu neke vrednosti d mogu biti sačuvane. Jednostavnije, Nivasch pohvaljuje D. P. Woodruff sa sugestijom čuvanja nasumičnog primerka prethodno viđenih vrednosti, stvarajući odgovarajući nasumični izbor na svakom koraku tako da uzorak ostaje nasumičan.

• Nivasch opisuje algoritam koji ne koristi fiksiranu količinu memorije, ali za koji je očekivana količina memorije iskorišćena (pod pretpostavkom da je ulazna funkcia nasumična) je logaritamska u dužini sekvence. Predmet sačuvan u memorijskoj tabeli, sa ovom tehnikom, kada nijedan kasniji predmet nema manju vrednost. Kako Nivasch pokazuje, predmeti ovom tehnikom mogu biti održavani korišćenjem stek strukture podataka, i svaka sledeća vrednost sekvence treba da se uporedi sa vrhom steka. Algoritam se završava kada se pronađe ponovljen element sekvence sa najmanjom vrednosti. Koristeći isti algoritam sa više stekova, koristeći nasumične permutacije vrednosti da bi se premestile vrednosti u steku, dozvoljava vreme-prostor razmenu sličnu prethodnim algoritmima. Međutim, čak i verzije algoritma sa jednim stekom nije pointerski algoritam, zbog poređenja potrebnog da se odredi koja od dve vrednosti je manja.

Bilo koji algoritam za detekciju ciklusa koi čuva najviše M vrednosti od ulazne sekvence mora da izvrši bar $\scriptstyle (\lambda +\mu )(1+{\frac {1}{M-1}})$ evaluacija funkcije.

Primene

Detekcija ciklusa se koristi u puno primena.

• Određivanje dužine ciklusa pseudonasumičnog generatora brojeva je jedna mera njegove snage. Ovo je primena citirana od strane Kunta opisujući Flojdov metod. Brent opisuje rezultate testiranja  linearnog kongruencijskog generatora u ovom pogledu; ispostavilo se da je njegov period znatno manji nego što se pričalo. Za kompleksnije generatore, sekvenca vrednosti u kojoj pronađeni ciklus ne mora da reprezentuje izlaz  generatora, nego njegovo unutrašnje stanje.
• Nekoliko brojno teoretskih algoritama se zasniva na detekciji ciklusa, uključujući Pollard's rho algoritam za faktorizaciju celih brojeva i povezan je sa kengur algoritmom za problem diskretnog logaritma.
• U kriptografijskim primenama, mogućnost da se pronađu dve slične vrednosti x_μ−-1 i x_λ+μ−-1 preslikaniih uz pomoć neke kriptografske funkcije ƒ za istu vrednost x_μ može da indikuje slabost u ƒ. Na primer, Quisquater i Delescaille primenjuju algoritme za detekciju ciklusa u potrazi za porukom i parom Data Encryption Standard ključeva koji mapiraju tu poruku na istu enkriptovanu vrednost; Kaliski, Rivest, i Sherman takođe koriste algoritme za detekciju ciklusa da napadnu DES. Tehnika takođe može biti iskorišćena da se pronađe sudar u kriptografskoj heš funkciji.
• Detekcija ciklusa može biti od pomoći kao način otkrivanja beskonačnih petlji u određenim tipovima računarskih programa.
• Periodične konfiguracije u simuliranju celularne automatizacije mogu biti pronađene primenom algoritama za detekciju ciklusa na sekvenci automatonskih stanja.
• Analiza oblika strukture podataka povezanih lista je tehnika za verifikovanje ispravnosti algoritma korišćenjem ovih struktura. Ako čvor u listi nepravilno pokazuje na prethodni čvor u istoj listi, struktura će formirati ciklus koi može biti detektovan od strane ovih algoritama.
• Teske opisuje primene u teoriji računanja grupa: proveravajući strukturu Abelove grupe iz seta njegovih generatora. Kriptografski algoritmi Kaliski et al. mogu takođe biti posmatrani kao pokušavanje  da se zaključi struktura nepoznate grupe.
• Fich ukratko pominje primenu u računarskoj simulaciji celestijalne mehanike, koju ona pripisuje William Kahan. U ovoj primeni, detekcija ciklusa u faznom prostoru orbitalnog sistema može biti iskorišćena da se odredi da li je sistem periodičan unutar preciznosti simulacije.
• U Common Lisp, S-expression štampač, pod kontrolom *print-circle* promenljive, detektuje cirkularnu strukturu liste i štampa je kompaktno.

Spoljašnje veze

• 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)