Algoritmo Randomizado - Randomized algorithm

Um algoritmo aleatório é um algoritmo que emprega um certo grau de aleatoriedade como parte de sua lógica ou procedimento. O algoritmo normalmente usa bits uniformemente aleatórios como uma entrada auxiliar para guiar seu comportamento, na esperança de obter um bom desempenho no "caso médio" sobre todas as escolhas possíveis de aleatório determinado pelos bits aleatórios; portanto, o tempo de execução ou a saída (ou ambos) são variáveis aleatórias.

É preciso distinguir entre algoritmos que usam a entrada aleatória para que sempre terminem com a resposta correta, mas onde o tempo de execução esperado é finito ( algoritmos de Las Vegas , por exemplo Quicksort ), e algoritmos que têm uma chance de produzir um resultado incorreto ( Algoritmos de Monte Carlo , por exemplo, o algoritmo de Monte Carlo para o problema MFAS ) ou falham em produzir um resultado sinalizando uma falha ou não encerrando. Em alguns casos, os algoritmos probabilísticos são os únicos meios práticos de resolver um problema.

Na prática comum, algoritmos aleatórios são aproximados usando um gerador de números pseudo - aleatórios no lugar de uma fonte verdadeira de bits aleatórios; tal implementação pode desviar-se do comportamento teórico esperado e das garantias matemáticas que podem depender da existência de um gerador de número aleatório verdadeiro ideal.

Motivação

Como um exemplo motivador, considere o problema de encontrar um ' a ' em uma matriz de n elementos.

Entrada : Uma matriz de n ≥2 elementos, em que metade é ' a ' se a outra metade é ' b ' s.

Saída : Encontre um ' a ' na matriz.

Fornecemos duas versões do algoritmo, um algoritmo de Las Vegas e um algoritmo de Monte Carlo .

Algoritmo de Las Vegas:

findingA_LV(array A, n)
begin
    repeat
        Randomly select one element out of n elements.
    until 'a' is found
end

Este algoritmo é bem-sucedido com a probabilidade 1. O número de iterações varia e pode ser arbitrariamente grande, mas o número esperado de iterações é

{\ displaystyle \ lim _ {n \ to \ infty} \ sum _ {i = 1} ^ {n} {\ frac {i} {2 ^ {i}}} = 2}

Como é constante, o tempo de execução esperado em muitas chamadas é . (Veja a notação Big Theta ) ${\ displaystyle \ Theta (1)}$

Algoritmo de Monte Carlo:

findingA_MC(array A, n, k)
begin
    i := 0
    repeat
        Randomly select one element out of n elements.
        i := i + 1
    until i = k or 'a' is found
end

Se um ' a ' for encontrado, o algoritmo é bem-sucedido, caso contrário, o algoritmo falha. Após k iterações, a probabilidade de encontrar um ' a ' é:

${\ displaystyle \ Pr [\ mathrm {find ~ a}] = 1- (1/2) ^ {k}}$

Este algoritmo não garante sucesso, mas o tempo de execução é limitado. O número de iterações é sempre menor ou igual a k. Tomando k como constante, o tempo de execução (esperado e absoluto) é . ${\ displaystyle \ Theta (1)}$

Algoritmos randomizados são particularmente úteis quando confrontados com um "adversário" ou invasor mal-intencionado que tenta deliberadamente fornecer uma entrada incorreta ao algoritmo (consulte a complexidade do pior caso e análise competitiva (algoritmo online) ), como no dilema do Prisioneiro . É por essa razão que a aleatoriedade é onipresente na criptografia . Em aplicações criptográficas, números pseudoaleatórios não podem ser usados, uma vez que o adversário pode predizê-los, tornando o algoritmo efetivamente determinístico. Portanto, é necessária uma fonte de números verdadeiramente aleatórios ou um gerador de números pseudo-aleatórios criptograficamente seguro . Outra área em que a aleatoriedade é inerente é a computação quântica .

No exemplo acima, o algoritmo de Las Vegas sempre produz a resposta correta, mas seu tempo de execução é uma variável aleatória. O algoritmo Monte Carlo (relacionado ao método Monte Carlo para simulação) tem garantia de conclusão em um período de tempo que pode ser limitado por uma função de tamanho de entrada e seu parâmetro k , mas permite uma pequena probabilidade de erro . Observe que qualquer algoritmo de Las Vegas pode ser convertido em um algoritmo de Monte Carlo (via desigualdade de Markov ), fazendo com que ele produza uma resposta arbitrária, possivelmente incorreta, se não for concluído dentro de um tempo especificado. Por outro lado, se existe um procedimento de verificação eficiente para verificar se uma resposta está correta, um algoritmo de Monte Carlo pode ser convertido em um algoritmo de Las Vegas executando o algoritmo de Monte Carlo repetidamente até que uma resposta correta seja obtida.

Complexidade computacional

A teoria da complexidade computacional modela algoritmos aleatórios como máquinas de Turing probabilísticas . Os algoritmos de Las Vegas e Monte Carlo são considerados e várias classes de complexidade são estudadas. A classe de complexidade aleatória mais básica é RP , que é a classe de problemas de decisão para a qual existe um algoritmo aleatório eficiente (tempo polinomial) (ou máquina de Turing probabilística) que reconhece NO-instâncias com certeza absoluta e reconhece SIM-instâncias com uma probabilidade de pelo menos 1/2. A classe complementar para RP é co-RP. Classes de problemas que têm algoritmos (possivelmente não terminantes) com tempo de execução médio de caso polinomial cuja saída é sempre correta são ditas em ZPP .

A classe de problemas para os quais as instâncias SIM e NÃO podem ser identificadas com algum erro é chamada de BPP . Esta classe atua como o equivalente aleatório de P , ou seja, BPP representa a classe de algoritmos aleatórios eficientes.

História

Historicamente, o primeiro algoritmo aleatório foi um método desenvolvido por Michael O. Rabin para o problema do par mais próximo em geometria computacional . O estudo de algoritmos aleatórios foi estimulado pela descoberta de 1977 de um teste de primalidade aleatório (ou seja, determinando a primalidade de um número) por Robert M. Solovay e Volker Strassen . Logo depois, Michael O. Rabin demonstrou que o teste de primalidade de Miller de 1976 pode ser transformado em um algoritmo aleatório. Naquela época, nenhum algoritmo determinístico prático para a primalidade era conhecido.

O teste de primalidade de Miller-Rabin se baseia em uma relação binária entre dois inteiros positivos k e n que pode ser expressa dizendo que k "é uma testemunha da composição de" n . Pode-se mostrar que

Se houver uma testemunha da composição de n , então n é composto (ou seja, n não é primo ), e
Se n for composto, então pelo menos três quartos dos números naturais menores que n são testemunhas de sua composição, e
Existe um algoritmo rápido que, dados k e n , verifica se k é uma testemunha da composição de n .

Observe que isso implica que o problema de primalidade está em Co- RP .

Se alguém escolhe aleatoriamente 100 números menores do que um número composto n , então a probabilidade de não conseguir encontrar tal "testemunha" é (1/4) ^{100, de} modo que para a maioria dos propósitos práticos, este é um bom teste de primalidade. Se n for grande, pode não haver outro teste prático. A probabilidade de erro pode ser reduzida a um grau arbitrário com a realização de testes independentes suficientes.

Portanto, na prática, não há penalidade associada à aceitação de uma pequena probabilidade de erro, uma vez que com um pouco de cuidado a probabilidade de erro pode ser reduzida astronomicamente. Na verdade, embora um teste de primalidade de tempo polinomial determinístico tenha sido encontrado (consulte o teste de primalidade AKS ), ele não substituiu os testes probabilísticos mais antigos em software criptográfico nem é esperado que o faça em um futuro previsível.

Exemplos

Ordenação rápida

Quicksort é um algoritmo conhecido e comumente usado no qual a aleatoriedade pode ser útil. Muitas versões determinísticas deste algoritmo requerem tempo O ( n ² ) para classificar n números para alguma classe bem definida de entradas degeneradas (como uma matriz já classificada), com a classe específica de entradas que geram esse comportamento definido pelo protocolo para seleção de pivô. No entanto, se o algoritmo seleciona elementos de pivô uniformemente ao acaso, ele tem uma probabilidade comprovadamente alta de terminar em tempo O ( n log n ), independentemente das características da entrada.

Construções incrementais randomizadas em geometria

Na geometria computacional , uma técnica padrão para construir uma estrutura como um casco convexo ou triangulação de Delaunay é permutar aleatoriamente os pontos de entrada e então inseri-los um por um na estrutura existente. A randomização garante que o número esperado de mudanças na estrutura causadas por uma inserção seja pequeno e, portanto, o tempo de execução esperado do algoritmo pode ser limitado a partir de cima. Esta técnica é conhecida como construção incremental aleatória .

Corte mínimo

Entrada : um gráfico G ( V , E )

Saída : Um corte compartimentar os vértices em L e R , com o número mínimo de arestas entre L e R .

Recorde-se que a contracção de dois nós, u e v , num gráfico (multi-) produz um novo nó u 'com extremidades que a união do incidente arestas em ambos u ou v , excepto a partir de qualquer extremidade (s) de ligação u e v . A Figura 1 dá um exemplo de contracção do vértice A e B . Após a contração, o gráfico resultante pode ter bordas paralelas, mas não contém loops próprios.

Figura 2: Execução bem-sucedida do algoritmo de Karger em um gráfico de 10 vértices. O corte mínimo tem tamanho 3 e é indicado pelas cores dos vértices.

Figura 1: Contração dos vértices A e B

Algoritmo básico de Karger:

begin
    i = 1
    repeat
        repeat
            Take a random edge (u,v) ∈ E in G
            replace u and v with the contraction u'
        until only 2 nodes remain
        obtain the corresponding cut result C_i
        i = i + 1
    until i = m
    output the minimum cut among C₁, C₂, ..., C_m.
end

Em cada execução do loop externo, o algoritmo repete o loop interno até que apenas 2 nós permaneçam, o corte correspondente é obtido. O tempo de execução de uma execução é , en denota o número de vértices. Após m execuções do loop externo, produzimos o corte mínimo entre todos os resultados. A figura 2 dá um exemplo de uma execução do algoritmo. Após a execução, obtemos um corte de tamanho 3. ${\ displaystyle O (n)}$

Lema 1 - Seja k o tamanho de corte mínimo e seja $C = {e 1, e 2, ..., e k}$ o corte mínimo. Se, durante a iteração i , nenhuma aresta $e \in C$ é seleccionado para a contracção, então $C i = C$ .

Prova -

Se G não estiver conectado, então G pode ser particionado em L e R sem nenhuma aresta entre eles. Portanto, o corte mínimo em um gráfico desconectado é 0. Agora, suponha que G esteja conectado. Seja $V = L \cup R$ a partição de V induzida por $C : C = {{u, v} \in E : u \in L, v \in R}$ (bem definido uma vez que G está conectado). Considere-se uma borda { u , v } de C . Inicialmente, u , v são vértices distintos. Enquanto nós escolhemos uma vantagem , $u$ e $v$ não se fundiram. ${\ displaystyle f \ neq e}$ Assim, no final do algoritmo, que tem dois nós compostos que abrangem o gráfico inteiro, um consistindo nos vértices de G e a outra consistindo nos vértices de R . Como na figura 2, o tamanho do corte mínimo é 1 e C = {( A , B )}. Se não selecionarmos ( A , B ) para a contração, podemos obter o corte mínimo.

Lema 2 - Se G é um multigrafo com p vértices e cujo corte mínimo tem tamanho k , então G tem pelo menos pk / 2 arestas.

Prova -

Como o corte mínimo é k , todo vértice v deve satisfazer o grau ( v ) ≥ k . Portanto, a soma do grau é pelo menos pk . Mas é bem sabido que a soma dos graus do vértice é igual a 2 | E |. O lema segue.

Análise de algoritmo

A probabilidade de que o algoritmo seja bem-sucedido é 1 - a probabilidade de que todas as tentativas falhem. Por independência, a probabilidade de que todas as tentativas falhem é

{\ displaystyle \ prod _ {i = 1} ^ {m} \ Pr (C_ {i} \ neq C) = \ prod _ {i = 1} ^ {m} (1- \ Pr (C_ {i} = C)).}

Pelo lema 1, a probabilidade de $C i = C$ é a probabilidade de que nenhuma aresta de C seja selecionada durante a iteração i . Considere o loop interno e deixe $G j$ denotar o gráfico após j contrações de aresta, onde $j \in {0, 1,\dots, n - 3}$ . $G j$ tem $n - j$ vértices. Usamos a regra da cadeia de possibilidades condicionais . A probabilidade de que a aresta escolhida na iteração j não esteja em C , dado que nenhuma aresta de C foi escolhida antes, é . Observe que $G$ $j$ ainda tem um corte mínimo de tamanho k , então pelo Lema 2, ele ainda tem pelo menos arestas. ${\ displaystyle 1 - {\ frac {k} {| E (G_ {j}) |}}}$ ${\ displaystyle {\ frac {(nj) k} {2}}}$

Assim ,. ${\ displaystyle 1 - {\ frac {k} {| E (G_ {j}) |}} \ geq 1 - {\ frac {2} {nj}} = {\ frac {nj-2} {nj}} }$

Então, pela regra da cadeia, a probabilidade de encontrar o corte mínimo C é

{\ displaystyle \ Pr [C_ {i} = C] \ geq \ left ({\ frac {n-2} {n}} \ right) \ left ({\ frac {n-3} {n-1}} \ right) \ left ({\ frac {n-4} {n-2}} \ right) \ ldots \ left ({\ frac {3} {5}} \ right) \ left ({\ frac {2} {4}} \ direita) \ esquerda ({\ frac {1} {3}} \ direita).}

O cancelamento dá . Portanto, a probabilidade de que o algoritmo seja bem-sucedido é de pelo menos . Pois , isso é equivalente a . O algoritmo encontra o corte mínimo com probabilidade , no tempo . ${\ displaystyle \ Pr [C_ {i} = C] \ geq {\ frac {2} {n (n-1)}}}$ ${\ displaystyle 1- \ left (1 - {\ frac {2} {n (n-1)}} \ right) ^ {m}}$ ${\ displaystyle m = {\ frac {n (n-1)} {2}} \ ln n}$ ${\ displaystyle 1 - {\ frac {1} {n}}}$ ${\ displaystyle 1 - {\ frac {1} {n}}}$ ${\ displaystyle O (mn) = O (n ^ {3} \ log n)}$

Desrandomização

A aleatoriedade pode ser vista como um recurso, como espaço e tempo. A desrandomização é, então, o processo de remover a aleatoriedade (ou usar o mínimo possível). Não se sabe atualmente se todos os algoritmos podem ser desaleatorizados sem aumentar significativamente seu tempo de execução. Por exemplo, na complexidade computacional , não se sabe se P = BPP , ou seja, não sabemos se podemos pegar um algoritmo aleatório arbitrário que é executado em tempo polinomial com uma pequena probabilidade de erro e desrandomizá-lo para ser executado em tempo polinomial sem usar aleatoriedade .

Existem métodos específicos que podem ser empregados para desregulamentar algoritmos aleatórios particulares:

o método das probabilidades condicionais e sua generalização, estimadores pessimistas
teoria da discrepância (que é usada para desregular algoritmos geométricos)
a exploração de independência limitada nas variáveis aleatórias usadas pelo algoritmo, como a independência de pares usada em hashing universal
o uso de gráficos expansores (ou dispersores em geral) para amplificar uma quantidade limitada de aleatoriedade inicial (esta última abordagem também é conhecida como geração de bits pseudo-aleatórios de uma fonte aleatória e leva ao tópico relacionado de pseudo-aleatoriedade)
alterar o algoritmo aleatório para usar uma função hash como uma fonte de aleatoriedade para as tarefas do algoritmo e, em seguida, desrandomizar o algoritmo por força bruta de todos os parâmetros possíveis (sementes) da função hash. Esta técnica é geralmente usada para pesquisar exaustivamente um espaço de amostra e tornar o algoritmo determinístico (por exemplo, algoritmos de gráfico aleatório)

Onde a aleatoriedade ajuda

Quando o modelo de computação é restrito a máquinas de Turing , atualmente é uma questão em aberto se a habilidade de fazer escolhas aleatórias permite que alguns problemas sejam resolvidos em tempo polinomial que não podem ser resolvidos em tempo polinomial sem essa habilidade; esta é a questão de saber se P = BPP. No entanto, em outros contextos, existem exemplos específicos de problemas em que a randomização produz melhorias estritas.

Com base no exemplo motivador inicial: dada uma string exponencialmente longa de 2 ^k caracteres, meio a e meio b, uma máquina de acesso aleatório requer 2 ^{k −1} pesquisas no pior caso para encontrar o índice de um a ; se for permitido fazer escolhas aleatórias, ele pode resolver esse problema em um número polinomial esperado de pesquisas.
A maneira natural de realizar um cálculo numérico em sistemas embarcados ou sistemas ciberfísicos é fornecer um resultado que se aproxime do correto com alta probabilidade (ou Computação Provavelmente Aproximadamente Correta (PACC)). O difícil problema associado à avaliação da perda de discrepância entre o cálculo aproximado e correto pode ser resolvido de forma eficaz recorrendo à randomização
Na complexidade da comunicação , a igualdade de duas strings pode ser verificada para alguma confiabilidade usando bits de comunicação com um protocolo aleatório. Qualquer protocolo determinístico requer bits para se defender de um oponente forte. ${\ displaystyle \ log n}$ ${\ displaystyle \ Theta (n)}$
O volume de um corpo convexo pode ser estimado por um algoritmo aleatório com precisão arbitrária em tempo polinomial. Bárány e Füredi mostraram que nenhum algoritmo determinístico pode fazer o mesmo. Isso é verdade incondicionalmente, ou seja, sem depender de quaisquer suposições da teoria da complexidade, assumindo que o corpo convexo pode ser consultado apenas como uma caixa preta.
Um exemplo mais teórico da complexidade de um lugar onde a aleatoriedade parece ajudar é a classe IP . IP consiste em todas as linguagens que podem ser aceitas (com alta probabilidade) por uma interação polinomialmente longa entre um provador todo-poderoso e um verificador que implementa um algoritmo BPP. IP = PSPACE . No entanto, se for necessário que o verificador seja determinístico, então IP = NP .
Em uma rede de reação química (um conjunto finito de reações como A + B → 2C + D operando em um número finito de moléculas), a capacidade de chegar a um determinado estado-alvo a partir de um estado inicial é decidível, embora até mesmo se aproxime da probabilidade de Sempre atingir um determinado estado alvo (usando a probabilidade baseada na concentração padrão para a qual a reação ocorrerá a seguir) é indecidível. Mais especificamente, uma máquina de Turing limitada pode ser simulada com probabilidade arbitrariamente alta de funcionar corretamente o tempo todo, apenas se uma rede de reação química aleatória for usada. Com uma rede de reação química não-determinística simples (qualquer reação possível pode acontecer a seguir), o poder computacional é limitado a funções recursivas primitivas .

Veja também

Notas

Referências

Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest e Clifford Stein . Introdução aos algoritmos , segunda edição. MIT Press e McGraw-Hill, 1990. ISBN 0-262-03293-7 . Capítulo 5: Probabilistic Analysis and Randomized Algorithms, pp. 91-122.
Dirk Draheim. " Semantics of the Probabilistic Typed Lambda Calculus (Markov Chain Semantics, Termination Behavior, and Denotational Semantics). " Springer, 2017.
Jon Kleinberg e Éva Tardos . Projeto de algoritmo . Capítulo 13: "Algoritmos aleatórios".
Fallis, D. (2000). “A confiabilidade dos algoritmos randomizados”. The British Journal for the Philosophy of Science . 51 (2): 255–271. doi : 10.1093 / bjps / 51.2.255 .
M. Mitzenmacher e E. Upfal . Probabilidade e computação: algoritmos randomizados e análise probabilística . Cambridge University Press, Nova York (NY), 2005.
Rajeev Motwani e P. Raghavan. Algoritmos Randomizados . Cambridge University Press, New York (NY), 1995.
Rajeev Motwani e P. Raghavan. Algoritmos Randomizados . Uma pesquisa sobre algoritmos randomizados.
Christos Papadimitriou (1993), Computational Complexity (1ª ed.), Addison Wesley, ISBN 978-0-201-53082-7 Capítulo 11: Randomized computation, pp. 241-278.
Rabin, Michael O. (1980). "Algoritmo probabilístico para testar a primalidade" . Journal of Number Theory . 12 : 128–138. doi : 10.1016 / 0022-314X (80) 90084-0 .
AA Tsay, WS Lovejoy, David R. Karger, Random Sampling in Cut, Flow, and Network Design Problems , Mathematics of Operations Research, 24 (2): 383-413, 1999.

Languages

In other projects