Algoritmo busca-ciclos de Floyd

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 ai 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 |ij| deve ser múltiplo do comprimento do ciclo, porque a definição de uma seqüência cíclica é:

a_{\lambda+m}=a_{\lambda+m+k\mu}.

A diferença entre os dois índices 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_{2m}

então qualquer divisor de 2mm = 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.

Algoritmo Busca-Cíclica de Floyd

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 a6 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.

Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.