Rilevamento dei cicli

Da Wikipedia, l'enciclopedia libera.
una funzione da e a un insieme {0,1,2,3,4,5,6,7,8} e corrispondente al grafo funzionale

Il Rilevamento dei cicli, in informatica è 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.

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[modifica | modifica wikitesto]

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 xi = xi+kλ

dove:

λ rappresenta la lunghezza del ciclo che vogliamo individuare.

In particolare, nel caso in cui i=kλ, abbiamo che xi = x2i

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 xi e l'altro (la lepre) puntato ad x2i

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 unitaà 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[modifica | modifica wikitesto]

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
Informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica