Algoritmo Busca-Cíclica de Floyd

Origem: Wikipédia, a enciclopédia livre.

Algoritmo para Busca de Cíclos de Floyd é um algoritmo inventado por Robert W. Floyd em 1967 para detectar ciclos em seqüências arbitrárias, seja em estruturas de dados ou geradas ao vivo (especialmente grafos e seqüências pseudo-aleatórias) usando espaço O(1). Algumas vezes este algoritmo é chamado de algoritmo-"tartaruga e a lebre".

A discussão a seguir é construída em termos de seqüências aleatórias em particular, de grande importância na análise de geradores de número pseudo-aleatórios e nas aplicações de algoritmos tais como fatoração o algoritmo rho de Pollard.

Seja

$f\colon S\mapsto S$

uma função pseudo-aleatória, com S um conjunto de cardinalidade finita n. Define-se uma seqüência a_i como:

a i + 1 = f (a i)

Evidentemente tal seqüência deve ter um ciclo após pelo menos n interações da função pseudo-aleatória, porque há somente n possíveis valores para um elemento. A maneira de naïve para encontrar o tamanho deste ciclo é guardar cada elemento da seqüência e, após cada iteração, procurar entre todos eles por duplicações. Isto significa que a necessidade de armazenamento é O(μ + λ), onde μ é o tamanho do ciclo e λ é o tamanho da cauda (isto é, da parte da seqüência que não é cíclica).

Note que se nos encontramos dois elementos de seqüência tal que

a i = a j

então |i − j| deve ser múltiplo do comprimento do ciclo, porque a definição de uma seqüência cíclica é:

a λ + m = a λ + m + k μ .

A diferença entre os dois indices que armazenam elementos iguais é kμ, um múltiplo do comprimento do ciclo. Algoritmo de busca-cíclica de Floyd encontra tal igualdade pelo processamento de duas instâncias de seqüências em paralelo, uma das quais é mais rápida mais "rápida" do que a outra; isto é uma instância processa duas iterações enquanto a outra processa uma. Então, quando

a m = a 2 m

então qualquer divisor de 2m − m = m deve ser o comprimento do ciclo. Se m é composto, pode-se deixar o algoritmo continuar a processar até que ele encontre mais valores de m para os quais a igualdade acima é verdadeira, e obter o maior divisor comum de m. Neste processo, a lista de possíveis μ's pode ser preparada.

A melhor maneira de visualizar este algoritmo é construir um diagrama da seqüência. Ele se parecerá com a letra Grega ρ. A seqüência inicia-se no fim da cauda, e move-=se para cima girando na direção oposta aos ponteiros do relógio. Acompanhando o algoritmo, as duas instâncias da seqüência irão se encontrar em a₆ depois de 6 iterações. Se o algoritmo continuar, as seqüências se encontram novamente, após outras seis iterações, no mesmo elemento. Desde que o comprimento do ciclo seja de fato 6, o mesmo resultado continuará ocorrendo.

No melhor caso, este algoritmo necessita λ comparações (com λ > 1), desde que a seqüência mais lenta tenha de percorrer ao menos a parte inicial do ciclo. O pior caso necessita λ + μ/2 comparações; a seqüência lenta não alcançará mais do que a metade do círculo sem que encontrar a seqüência rápida. O algoritmo usa um armazenamento de O(1).

Talvez a mais difundida variante deste algoritmo seja o algoritmo rho de Pollard, um algoritmo de fatoração inteira que usa números pseudo-aleatórios para fatorar inteiros. Há também um algoritmo para cálculo de logaritmo discretos baseado no Algoritmo de busca-ciclica de Floyd.