Algoritmo de Las Vegas - Las Vegas algorithm

Na computação , um algoritmo de Las Vegas é um algoritmo aleatório que sempre fornece resultados corretos ; ou seja, sempre produz o resultado correto ou informa sobre a falha. No entanto, o tempo de execução de um algoritmo de Las Vegas difere dependendo da entrada. A definição usual de um algoritmo de Las Vegas inclui a restrição de que o tempo de execução esperado seja finito, onde a expectativa é realizada sobre o espaço de informação aleatória, ou entropia, usado no algoritmo. Uma definição alternativa requer que um algoritmo de Las Vegas sempre termine (é eficaz ), mas pode gerar um símbolo que não faz parte do espaço de solução para indicar falha em encontrar uma solução. A natureza dos algoritmos de Las Vegas os torna adequados em situações onde o número de soluções possíveis é limitado e onde verificar a exatidão de uma solução candidata é relativamente fácil, enquanto encontrar uma solução é complexo.

Os algoritmos de Las Vegas são proeminentes no campo da inteligência artificial e em outras áreas da ciência da computação e pesquisa operacional . Em AI, os algoritmos de pesquisa local estocástica (SLS) são considerados do tipo Las Vegas. Algoritmos SLS têm sido usados ​​para resolver problemas de decisão NP-completos e problemas de otimização combinatória NP-difíceis . No entanto, alguns métodos de pesquisa sistemática, como as variantes modernas do algoritmo Davis-Putnam para satisfatibilidade proposicional (SAT), também utilizam decisões não determinísticas e, portanto, também podem ser considerados algoritmos de Las Vegas.

História

Os algoritmos de Las Vegas foram introduzidos por László Babai em 1979, no contexto do problema de isomorfismo de grafos , como um algoritmo dual para os de Monte Carlo . Babai introduziu o termo "algoritmo de Las Vegas" junto com um exemplo envolvendo cara ou coroa: o algoritmo depende de uma série de cara ou coroa independente e há uma pequena chance de falha (sem resultado). No entanto, ao contrário dos algoritmos de Monte Carlo, o algoritmo de Las Vegas pode garantir a exatidão de qualquer resultado relatado.

Exemplo

// Las Vegas algorithm
repeat:
    k = RandInt(n)
    if A[k] == 1,
        return k;

Conforme mencionado acima, os algoritmos de Las Vegas sempre retornam resultados corretos. O código acima ilustra essa propriedade. Uma variável k é gerada aleatoriamente; após k é gerado, k é utilizado para indexar a matriz A . Se este índice contém o valor 1, então k é retornado; caso contrário, o algoritmo repete esse processo até encontrar 1. Embora seja garantido que esse algoritmo de Las Vegas encontre a resposta correta, ele não tem um tempo de execução fixo; devido à randomização (na linha 3 do código acima), é possível que muito tempo passe arbitrariamente antes que o algoritmo termine.

Definição

Esta seção fornece as condições que caracterizam um algoritmo ser do tipo Las Vegas.

Um algoritmo A é um algoritmo de Las Vegas para a classe de problema X, se

  1. sempre que para uma determinada instância de problema x∈X ele retorna uma solução s, s é garantido ser uma solução válida de x
  2. em cada instância x dada, o tempo de execução de A é uma variável aleatória RT A, x

Existem três noções de integridade para algoritmos de Las Vegas:

  • algoritmos completos de Las Vegas podem ser garantidos para resolver cada problema solucionável dentro do tempo de execução t max, onde t max é uma constante dependente da instância.

Seja P (RT A, x ≤ t) a probabilidade de que A encontre uma solução para uma instância solúvel x no tempo dentro de t, então A é completo exatamente se para cada x existe

algum t máx de modo que P (RT A, x ≤ t máx ) = 1.

  • algoritmos de Las Vegas aproximadamente completos resolvem cada problema com uma probabilidade convergindo para 1 conforme o tempo de execução se aproxima do infinito. Assim, A é aproximadamente completo, se para cada instância x, lim t → ∞ P (RT A, x ≤ t) = 1.
  • algoritmos de Las Vegas essencialmente incompletos são algoritmos de Las Vegas que não são aproximadamente completos.

A completude aproximada é principalmente de interesse teórico, uma vez que os prazos para encontrar soluções são geralmente muito grandes para serem úteis.

Cenários de aplicação

Os algoritmos de Las Vegas têm critérios diferentes para a avaliação com base na configuração do problema. Esses critérios são divididos em três categorias com diferentes limites de tempo, uma vez que os algoritmos de Las Vegas não têm complexidade de tempo definida. Aqui estão alguns cenários de aplicação possíveis:

Tipo 1: Não há limites de tempo, o que significa que o algoritmo roda até encontrar a solução.

Tipo 2: existe um limite de tempo t máx para encontrar o resultado.

Tipo 3: A utilidade de uma solução é determinada pelo tempo necessário para encontrar a solução.

Observe que o Tipo 1 e o Tipo 2 são casos especiais do Tipo 3.

Para o Tipo 1, onde não há limite de tempo, o tempo médio de execução pode representar o comportamento do tempo de execução. Este não é o mesmo caso para o Tipo 2.

Aqui, P ( RTt max ), que é a probabilidade de encontrar uma solução dentro do tempo, descreve seu comportamento em tempo de execução.

No caso do Tipo 3, seu comportamento em tempo de execução só pode ser representado pela função de distribuição de tempo de execução rtd : R → [0,1] definida como rtd ( t ) = P ( RTt ) ou sua aproximação.

A distribuição de tempo de execução (RTD) é a maneira distinta de descrever o comportamento de tempo de execução de um algoritmo de Las Vegas.

Com esses dados, podemos obter facilmente outros critérios, como tempo médio de execução, desvio padrão, mediana, percentis ou probabilidades de sucesso P ( RTt ) para limites de tempo arbitrários t .

Formulários

Analogia

Os algoritmos de Las Vegas surgem com frequência em problemas de pesquisa . Por exemplo, alguém que procura algumas informações online pode pesquisar sites relacionados para obter as informações desejadas. A complexidade do tempo, portanto, varia de ter "sorte" e encontrar o conteúdo imediatamente, a ser "azarado" e gastar muito tempo. Assim que o site correto for encontrado, não haverá possibilidade de erro.

Randomized QuickSort

INPUT: 
    # A is an array of n elements
def randomized_quicksort(A):
    if n == 1:
        return A  # A is sorted.
    else:
        i = random.randrange(1, n)  # Will take a random number in the range 1~n
        X = A[i]  # The pivot element
    """Partition A into elements < x, x, and >x  # as shown in the figure above.
    Execute Quicksort on A[1 to i-1] and A[i+1 to n].
    Combine the responses in order to obtain a sorted array."""

Um exemplo simples é QuickSort randomizado , onde o pivô é escolhido aleatoriamente e divide os elementos em três partições: elementos menores que pivô, elementos iguais a pivô e elementos maiores que pivô. O QuickSort aleatório requer muitos recursos, mas sempre gera a matriz classificada como uma saída.

É óbvio que QuickSort sempre gera a solução, que neste caso o array ordenado. Infelizmente, a complexidade do tempo não é tão óbvia. Acontece que o tempo de execução depende de qual elemento escolhemos como pivô.

  • O pior caso Θ ( n 2 ) quando o pivô é o menor ou o maior elemento.
  • Porém, por meio da randomização, onde o pivô é escolhido aleatoriamente e tem exatamente um valor médio a cada vez, o QuickSort pode ser feito em Θ ( n log n ).

O tempo de execução do QuickSort depende muito de quão bem o pivô é selecionado. Se um valor de pivô for muito grande ou pequeno, a partição ficará desequilibrada. Este caso dá um tempo de execução ruim. No entanto, se o valor do pivô estiver próximo ao meio da matriz, a divisão será razoavelmente bem balanceada. Assim, seu tempo de execução será bom. Como o pivô é escolhido aleatoriamente, o tempo de execução será bom na maioria das vezes e, ocasionalmente, ruim.

No caso do caso médio, é difícil determinar uma vez que a análise não depende da distribuição de entrada, mas das escolhas aleatórias que o algoritmo faz. A média do QuickSort é calculada sobre todas as escolhas aleatórias possíveis que o algoritmo pode fazer ao fazer a escolha do pivô.

Embora o pior caso de tempo de execução seja Θ ( n 2 ), o caso médio de tempo de execução é Θ ( n log n ). Acontece que o pior caso não acontece com frequência. Para grandes valores de n , o tempo de execução é Θ ( n log n ) com alta probabilidade.

Observe que a probabilidade de que o pivô seja o elemento de valor médio a cada vez é um de n números, o que é muito raro. No entanto, ainda é o mesmo tempo de execução quando a divisão é de 10% -90% em vez de 50% -50% porque a profundidade da árvore de recursão ainda será O (log n ) com O ( n ) vezes tomado cada nível de recursão.

Algoritmo ganancioso randomizado para o problema das oito rainhas

O problema das oito rainhas geralmente é resolvido com um algoritmo de retrocesso. No entanto, um algoritmo de Las Vegas pode ser aplicado; na verdade, é mais eficiente do que retroceder.

Coloque 8 rainhas em um tabuleiro de xadrez para que ninguém ataque a outra. Lembre-se de que uma rainha ataca outras peças na mesma linha, coluna e diagonais.

Suponha que k linhas, 0 ≤ k ≤ 8, sejam ocupadas com sucesso por rainhas.

Se k = 8, pare com sucesso. Caso contrário, prossiga para ocupar a linha k + 1.

Calcule todas as posições nesta linha não atacadas por rainhas existentes. Se não houver nenhum, então falhe. Caso contrário, escolha um aleatoriamente, incremente ke repita.

Observe que os algoritmos simplesmente falham se uma rainha não puder ser colocada. Mas o processo pode ser repetido e cada vez gerará um arranjo diferente.

Classe de complexidade

A classe de complexidade dos problemas de decisão que possuem algoritmos de Las Vegas com tempo de execução polinomial esperado é o ZPP .

Acontece que

que está intimamente ligado à maneira como os algoritmos de Las Vegas às vezes são construídos. A saber, a classe RP consiste em todos os problemas de decisão para os quais existe um algoritmo de tempo polinomial aleatório que sempre responde corretamente quando a resposta correta é "não", mas pode estar errado com uma certa probabilidade limitada a um quando a resposta é " sim". Quando tal algoritmo existe para um problema e seu complemento (com as respostas "sim" e "não" trocadas), os dois algoritmos podem ser executados simultaneamente e repetidamente: execute cada um por um número constante de etapas, revezando-se, até um deles retorna uma resposta definitiva. Esta é a maneira padrão de construir um algoritmo de Las Vegas que é executado no tempo polinomial esperado. Observe que, em geral, não há limite superior de pior caso no tempo de execução de um algoritmo de Las Vegas.

Algoritmo ideal de Las Vegas

Para tornar um algoritmo de Las Vegas ideal, o tempo de execução esperado deve ser minimizado. Isso pode ser feito por:

  1. O algoritmo A ( x ) de Las Vegas é executado repetidamente por alguns passos t 1 . Se A ( x ) parar durante o tempo de execução, A ( x ) estará concluído; caso contrário, repita o processo desde o início para mais t 2 etapas e assim por diante.
  2. Projetar uma estratégia que seja ótima entre todas as estratégias para A ( x ), dadas as informações completas sobre a distribuição de T A ( x ).

A existência da estratégia ótima pode ser uma observação teórica fascinante. No entanto, não é prático na vida real porque não é fácil encontrar a informação de distribuição de T A ( x ). Além disso, não adianta executar o experimento repetidamente para obter as informações sobre a distribuição, pois, na maioria das vezes, a resposta é necessária apenas uma vez para qualquer x .

Relação com algoritmos de Monte Carlo

Os algoritmos de Las Vegas podem ser contrastados com os algoritmos de Monte Carlo , nos quais os recursos usados ​​são limitados, mas a resposta pode estar incorreta com uma certa probabilidade (normalmente pequena) . Um algoritmo de Las Vegas pode ser convertido em um algoritmo de Monte Carlo executando-o por um tempo definido e gerando uma resposta aleatória quando ele falha ao terminar. Por uma aplicação da desigualdade de Markov , podemos definir o limite da probabilidade de que o algoritmo de Las Vegas ultrapasse o limite fixo.

Aqui está uma tabela que compara os algoritmos de Las Vegas e Monte Carlo:

Tempo de execução Exatidão
Algoritmo de Las Vegas probabilístico certo
Algoritmo de Monte Carlo certo probabilístico

Se uma maneira determinística de testar a correção estiver disponível, é possível transformar um algoritmo de Monte Carlo em um algoritmo de Las Vegas. No entanto, é difícil converter um algoritmo de Monte Carlo em um algoritmo de Las Vegas sem uma maneira de testar o algoritmo. Por outro lado, mudar um algoritmo de Las Vegas para um algoritmo de Monte Carlo é fácil. Isso pode ser feito executando um algoritmo de Las Vegas por um período específico de tempo dado pelo parâmetro de confiança. Se o algoritmo encontrar a solução dentro do tempo, ele foi bem-sucedido; caso contrário, a saída pode ser simplesmente "desculpe".

Este é um exemplo dos algoritmos de Las Vegas e Monte Carlo para comparação:

Suponha que haja uma matriz com o comprimento par n . Metade das entradas na matriz são 0's e a outra metade são 1's. O objetivo aqui é encontrar um índice que contenha 1.

//Las Vegas algorithm
repeat:
    k = RandInt(n)
    if A[k] == 1,
        return k;
        
//Monte Carlo algorithm
repeat 300 times:
    k = RandInt(n)
    if A[k] == 1
        return k
return "Failed"

Uma vez que Las Vegas não termina até encontrar 1 na matriz, não aposta com a correção, mas com o tempo de execução. Por outro lado, Monte Carlo é executado 300 vezes, o que significa que é impossível saber se Monte Carlo encontrará "1" na matriz dentro de 300 vezes de loops até que ele realmente execute o código. Ele pode encontrar a solução ou não. Portanto, ao contrário de Las Vegas, Monte Carlo não aposta com o tempo de execução, mas com a correção.

Veja também

Referências

Citações

Origens

  • Algorithms and Theory of Computation Handbook , CRC Press LLC, 1999.
  • "Algoritmo de Las Vegas", no Dicionário de Algoritmos e Estruturas de Dados [online], Paul E. Black, ed., Instituto Nacional de Padrões e Tecnologia dos EUA . 17 de julho de 2006. (acessado em 9 de maio de 2009) Disponível em: [1]