Algoritmos Probabilísticos, Parte 3: Las Vegas

Fonte: Mathieu Lebreton

Os algoritmos Monte Carlo tem como principal característica executarem em tempo determinístico, mas darem uma resposta probabilística. Isto significa que o tempo entre diferentes execuções não se altera, mas a resposta pode se alterar e há uma probabilidade de estar incorreta.

Considere o problema de, dado um vetor v contendo inteiros, retornar o índice da posição que contém um valor específico (x). Podemos construir um algoritmo Monte Carlo para este problema, como segue:

def MC(v,x):
   i = randint(0, len(v))
   return i

Ainda que não seja um algoritmo particularmente eficiente para este problema, ele tem todas características de um algoritmo Monte Carlo e há uma probabilidade de que a resposta retornada estará incorreta. Porém, antes de retornar, podemos verificar a resposta e apenas retorná-la se esta estiver correta. Isso é possível pois o custo da verificação, neste problema, é muito baixo. Podemos então construir um outro algoritmo para este problema:

def LV(v,x):
   while True:
      i = randint(0, len(v))
      if v[i]==x:
         return i

Este é um algoritmo Las Vegas. Observe que ele apenas retorna quando encontra a solução correta e, portanto, nunca retorna uma resposta incorreta. Porém, o tempo de execução é incerto! O algoritmo pode ter sorte e encontrar a solução correta na primeira tentativa, ou ter que tentar múltiplas vezes até encontrar a solução. Um algoritmo Las Vegas é de certa forma complementar a um algoritmo Monte Carlo. Um algoritmo Las Vegas tem tempo de execução probabilístico, mas resposta determinística.

Nem todo algoritmo Las Vegas é um Monte Carlo com uma etapa de verificação. Possivelmente o algoritmo Las Vegas mais conhecido é o algoritmo de ordenação Quick Sort. Este escolhe um elemento aleatório no vetor (denominado pivô) e separa o vetor entre os elementos menores e maiores que o pivô, chamando o algoritmo recursivamente em cada metade.

Se o pivô escolhido dividir de forma excessivamente desbalanceada o vetor, o algoritmo executa em O(n²). No entanto, para vetores grandes, é esperado que, em média, a escolha aleatória acabe por selecionar pivôs relativamente bons (i.e. que dividem o vetor em partes aproximadamente iguais) e, assim, o algoritmo tem tempo médio de execução O(nlogn).

Note que não há nenhuma verificação ocorrendo no algoritmo, mas ele tem as características de um Las Vegas: o vetor resultante sempre estará ordenado, mas o tempo de execução é incerto e varia a cada execução mesmo para a mesma entrada. Diz-se que neste caso o algoritmo Las Vegas é completo, pois há um tempo máximo de execução que depende do tamanho da entrada. Em contraste, o algoritmo anterior, para encontrar um índice no vetor, é dito aproximadamente completo: para um tempo que se aproxima de infinito, o algoritmo garante encontrar a solução. Algoritmos que podem nunca terminar são ditos essencialmente incompletos.

Uma outra vantagem de selecionar o pivô aleatoriamente é que o algoritmo torna-se imune a piores casos. Considere o Quick Sort que simplesmente pega o primeiro elemento do vetor como pivô. Desde que o vetor de entrada esteja ordenado aleatoriamente, o resultado é equivalente a uma escolha aleatória. Porém, o que acontece se o vetor estiver ordenado ou invertido? Nesse caso, o algoritmo garantidamente executará no seu pior caso, sempre escolhendo o pior pivô possível.

Com a escolha aleatória do pivô, não há nenhuma instância da entrada que force o algoritmo a executar no seu pior caso. Isso é importante quando não sabemos características das instâncias sobre as quais algoritmo terá que executar e evita instâncias adversariais, construídas por um atacante que deseja tornar o algoritmo lento.

A desvantagem é que para qualquer entrada o algoritmo pode ter azar e rodar em tempo equivalente a seu pior caso.

Quando algoritmos de ordenação são introduzidos para estudantes de Computação, por vezes se menciona, como piada, o chamado “Bozo Sort”: com o vetor de entrada, gera-se uma permutação aleatória dos elementos e verifica-se se o vetor resultante está ordenado. Se não estiver, repete-se o processo até que o vetor esteja ordenado.

Ao contrário do Quick Sort, que é um dos algoritmos mais eficientes na prática para ordenação apesar da possibilidade do pior caso ser pior que alternativas como Merge Sort, o Bozo Sort é extremamente ineficiente. Ainda assim, ele é um algoritmo Las Vegas: ele só retorna quando a solução for correta, mas o tempo de retorno pode variar consideravelmente entre execuções.

Na mesma linha do Bozo Sort, um outro exemplo de aplicação de um algoritmo Las Vegas é no Problema das N Rainhas. Em um tabuleiro de xadrez NxN, desejamos colocar N rainhas sem que estas se ataquem. Você pode experimentar com este problema aqui. Dada uma configuração com N rainhas, é simples verificar se ela é válida, mas encontrar uma solução não é trivial.

Um algoritmo Las Vegas ineficiente coloca N rainhas em posições aleatórias e verifica se esta é uma solução. Porém, podemos tornar esta solução mais eficiente considerando que duas rainhas nunca podem ocupar a mesma coluna (ou linha). Assim, podemos posicionar as rainhas uma por uma, uma por coluna, escolhendo uma linha aleatória para cada. Para cada rainha colocada, verificamos se esta não está sob ataque das anteriores. Se estiver, retornamos ao início (para a primeira rainha) e tentamos de novo.

Interessantemente, este algoritmo é bastante eficiente e em média exige testar menos configurações do que a abordagem clássica determinística baseada em backtracking.