Rilevamento dei cicli

Una funzione da e a un insieme {0,1,2,3,4,5,6,7,8} e corrispondente al grafo funzionale

In informatica, il rilevamento dei cicli è un problema algoritmico riguardante la ricerca di un ciclo in una sequenza di valori di funzione iterata. Per ogni funzione ƒ che mappa un insieme finito S su se stesso, ed ogni valore iniziale x0 in S, la sequenza dei valori della funzione iterata.

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

deve infine usare lo stesso valore 2 volte: ci deve essere qualcosa i ≠ j come xi = xj. Una volta che ciò accade, la sequenza deve continuare dal ciclo ripetuto di valori da xi a xj-1. La rilevazione dei cicli è il problema di trovare i e j dato ƒ e x0.

Algoritmo di ricerca del ciclo di Floyd

Sia μ l'indice del primo elemento del ciclo.

Per ogni intero i ≥ μ e per ogni intero k ≥ 0, abbiamo che per tutti gli elementi all'interno del ciclo vale la relazione x_i = x_i+kλ, dove λ rappresenta la lunghezza del ciclo che vogliamo individuare.

In particolare, nel caso in cui i=kλ, abbiamo che x_i = x_2i

Quindi l'algoritmo deve solo trovare dei valori ripetuti di questa particolare forma, in cui uno dei valori si trova al doppio della distanza dall'inizio del ciclo rispetto all'altro, in maniera tale da individuare un periodo di ripetizione v che sia un multiplo di λ.

L'algoritmo quindi mantiene 2 puntatori nella sequenza, uno (la tartaruga) puntato ad x_i e l'altro (la lepre) puntato ad x_2i

Ad ogni passo dell'algoritmo, i viene aumentato di uno, facendo sì che la tartaruga si muova di 1 passo, e la lepre di 2 passi in avanti nella sequenza. Quindi vengono comparati i valori dei due puntatori. Il più piccolo valore di i > 0 per cui la tartaruga e la lepre puntano a valori uguali è il valore desiderato di v.

Una volta che v è stato individuato, l'algoritmo ripercorre la sequenza dall'inizio per trovare il primo valore ripetuto x_μ nella sequenza, sfruttando il fatto che v è un multiplo di λ. Quindi possiamo dire che x_μ=x_μ+v

Infine, una volta che il valore di μ è conosciuto, è facile trovare la lunghezza λ del più piccolo dei cicli, cercando il primo valore μ+λ per cui x_μ+λ = x_μ

def floyd(f, x0):
    # Prima fase dell'algoritmo, trovare il ciclo x_mu = x_2mu
    # La lepre si muove 2 volte più velocemente della tartaruga
    # Eventualmente la lepre e la tartaruga si troveranno entrambi all'interno 
    # del ciclo e la distanza tra loro aumenterà di 1 unità alla volta fino a 
    # quando questa distanza sarà divisibile per la lunghezza del ciclo, ossia
    # la lepre e la tartaruga si incontrano in un nodo del ciclo
    tortoise = f(x0) # f(x0) è l'elemento/nodo dopo x0.
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))
  
    # a questo punto la tartaruga e la lepre si trovano nello stesso nodo
    # all'interno del ciclo. Si mette la tartaruga all'inizio della sequenza,
    # lasciando ferma la lepre. Poi si fanno muovere entrambe di 1 unità alla volta
    # fino a quando non si incontrano di nuovo. A questo punto si incontrano
    # all'inizio del ciclo

    # Trova la posizione della prima ripetizione di lunghezza mu
    # La lepre e la tartaruga si muovono alla stessa velocità di 1 unità
    mu = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        mu += 1
 
    # Trova la lunghezza del ciclo più corto a partire da x_mu
    # La lepre si muove e la tartaruga sta ferma
    lam = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        lam += 1
 
    return lam, mu

Algoritmo di Brent

Codice Python che mostra come funziona la tecnica:

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 lambda
    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)
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        mu += 1
 
    return lam, mu