Busca por força bruta

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Mergefrom 2.svg
O artigo ou secção Força bruta deverá ser fundido aqui. (desde março de 2013)
(por favor crie o espaço de discussão sobre essa fusão e justifique o motivo aqui; não é necessário criar o espaço em ambas as páginas, crie-o somente uma vez. Perceba que para casos antigos é provável que já haja uma discussão acontecendo na página de discussão de um dos artigos. Cheque ambas (1, 2) e não esqueça de levar toda a discussão quando levar o caso para a central.).
NoFonti.svg
Este artigo ou se(c)ção cita uma ou mais fontes fiáveis e independentes, mas ela(s) não cobre(m) todo o texto (desde Dezembro de 2011).
Por favor, melhore este artigo providenciando mais fontes fiáveis e independentes e inserindo-as em notas de rodapé ou no corpo do texto, conforme o livro de estilo.
Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.

Em ciência da computação, busca por força bruta ou busca exaustiva, também conhecido como gerar e testar, é uma técnica de solução de problemas trivial, porém muito geral que consiste em enumerar todos os possíveis candidatos da solução e checar cada candidato para saber se ele satisfaz o enunciado do problema. Por exemplo, um algoritmo de força bruta que acha os divisores de um número natural n enumera todos os inteiros de 1 até a raiz quadrada de n, e os checa para saber se dividem n sem deixar resto. Outro exemplo, considere o popular problema das oito damas, no qual é preciso colocar 8 damas em um tabuleiro de xadrez de maneira que nenhuma rainha ataque outra. Uma abordagem por força bruta examinaria todas as possíveis combinações das 8 peças nos 64 quadrados, e, para cada arranjo, checar se alguma rainha está atacando outra. Busca por força bruta é de simples implementação, e sempre vai achar a solução se esta existir. Entretanto, ele custará proporcionalmente ao número de candidatos à solução, o que, em muitos problemas práticos, tende a crescer muito rápido à medida que o tamanho do problema aumenta. Desta maneira, busca por força bruta é tipicamente usada quando o tamanho do problema é limitado, ou quando há heurísticas específicas para o problema que podem ser usadas para reduzir a coleção de candidatos á solução a um tamanho manejável. Este método também é usado quando a simplicidade de implementação é mais importante que a velocidade. Este é o caso de, por exemplo, em aplicações críticas onde qualquer erro no algoritmo teria consequências sérias; ou quando estiver usando um computador para provar um teorema matemático. Busca por força bruta também é útil como "método de base" para benchmarking outros algoritmos ou meta-heurísticas. De fato, busca por força bruta pode ser visto como a mais simples meta-heurística. Busca por força bruta não deve ser confundido com backtracking, onde grandes coleções de soluções podem ser descartadas sem serem explicitamente enumerados. O método de força bruta para achar um item em uma tabela — ou seja, checar todas as entradas da tabela, sequencialmente — é chamado busca linear.

Implementando a busca por força bruta[editar | editar código-fonte]

Algoritmo Básico[editar | editar código-fonte]

Para aplicar busca por força bruta para uma classe específica de problemas, é preciso implementar quatro procedimentos, primeiro,próximo, válido, e saída. Estes procedimentos devem ter como parâmetro os dados P para a instancia do problema que será resolvido, e deve fazer o seguinte:

  1. primeiro (P): gera o primeiro candidato à solução de P.
  2. próximo (P, c): gera o próximo candidato de P depois de c.
  3. válido (P, c): checa se o candidato c é a solução de P.
  4. saída (P, c): usa a solução c de P como for conveniente para a aplicação.

O procedimento próximo também deve dizer quando não há mais candidatos à P, após o c atual. Uma maneira conveniente de fazer isto é retornando um "candidato nulo", um valor de dados comum Λ que é distinto de qualquer outro candidato real. Da mesma maneira primeiro deve retornar Λ se não houver nenhum candidato para a instancia P. O método de busca por força bruta é expresso pelo algoritmo

 c \gets primeiro(P)
enquanto c \neq Λ faça se válido(P,c) então saída(P, c)  c \gets próximo(P,c)

Por exemplo, quando buscando os divisores de um inteiro n, a instância de dados P é o número n. A chamada primeiro deverá retornar o inteiro 1 se n \geq 1, ou Λ caso contrário; a chamada próximo(n,c) deverá retornar c + 1 se c < n, e Λ caso contrário; e válido(n,c) deverá retornar verdadeiro se e somente se c é divisor de n. (De fato, se escolhermos Λ para ser n + 1, os testes n \geq 1 e c < n serão desnecessários). O algoritmo de busca por força bruta acima irá chamar saída para cada candidato que é a solução para a dada instancia P. O algoritmo é facilmente modificado para parar após encontrar a primeira solução, ou um número dado de soluções; ou após serem testados um número dado de candidatos, ou após ter gasto uma dada quantidade de tempo da CPU .

Explosão combinatória[editar | editar código-fonte]

A principal desvantagem do método por força bruta é que, para muitos problemas reais, o numero de candidatos naturais é grande. Por exemplo, se olharmos os divisores de um número como descrito acima, o número de candidatos testados será o número n. Então se n tiver dezesseis dígitos decimais, a pesquisa vai requerer pelo menos 1015 instruções no computador, o que iria levar alguns dias em um computador comum. Se n for um número natural aleatório de 64-bit, que teria cerca de 19 dígitos decimais, a busca levaria cerca de 10 anos. Esse exorbitante crescimento do número de candidatos ocorre em todos os tipos de problemas. Por exemplo, se estivermos buscando um reajuste específico de 10 letras, teríamos 10! = 3.628.800 candidatos a considerar, o que um computador comum consegue gerar e testar em menos de um segundo. Entretanto, adicionando uma letra — o que é apenas 10% de aumento no tamanho dos dados — vai multiplicar o número de candidatos por 11 — um aumento de 1000%. Para 20 letras, o número de candidatos é 20!, o que é cerca de 2,4×1018 ou 2,4 quinquilhões; e a busca levaria cerca de 10,000 anos. Este indesejado fenômeno é comumente chamado de explosão combinatória.

Acelerando buscas por força bruta[editar | editar código-fonte]

Uma maneira de acelerar um algoritmo de força bruta é reduzir o espaço de busca, isto é, o conjunto de candidatos à solução, usando meta-heurísticas específicas da classe do problema. Por exemplo, considere o popular problema das oito damas, no qual é preciso colocar 8 damas em um tabuleiro de xadrez de maneira que nenhuma rainha ataque outra. Já que cada dama pode ser colocada em qualquer um dos 64 quadrados, em princípio existem 648 = 281.474.976.710.656 (mais de 281 trilhões) possibilidades a considerar. Entretanto, se observarmos que todas as damas são iguais, e que duas damas não podem ser colocadas num mesmo quadrado, nós concluímos que as candidatas são uma combinação de um conjunto de 8 quadrados em um conjunto de 64; o que quer dizer que há 64!/56!8! = 4.426.165.368 candidatas a solução, 1/60.000 da estimativa anterior. Na verdade, é fácil ver que nenhum arranjo com duas rainhas na mesma linha ou mesma coluna pode ser uma solução. Desta maneira, podemos restringir ainda mais a coleção de candidatas para arranjos onde dama 1 está na linha 1, dama 2 está na linha 2, e assim sucessivamente, e todas em colunas diferentes. Podemos descrever este arranjo usando um array de oito números, c[1] até c[8], cada um deles sendo um número entre 1 e 8, onde c[1] é a coluna da dama 1, c[2] é a coluna da dama 2, e assim sucessivamente. Já que esses números precisam ser todos diferentes, o número de candidatas para buscar é o número de permutações de 1 até 8, chamado 8! = 40.320 — cerca de 1/100.000 da estimative anterior, e 1/7.000.000.000 da primeira. Como este exemplo mostra, uma pequena análise normalmente vai diminuir drasticamente o número de candidatas à solução, e pode transformar um problema intratável em um trivial.

Reordenando o espaço de busca[editar | editar código-fonte]

Em aplicações que requerem somente uma solução, o tempo esperado de uma busca por força bruta vai depender da ordem na qual os candidatos são testados. Em geral, devem-se testar os candidatos mais promissores primeiro. Por exemplo, quando procurando um divisor para um numero n, é melhor enumerar os candidatos em ordem crescente, de 2 até n - 1, do que o contrário — porque a probabilidade de n ser divisível por c é 1/c. Além disso, a probabilidade de um candidato ser válido é comumente afetada por testes anteriores que falharam. Por exemplo, considere o problema de achar um 1 bit em uma dada string P de 1000-bit. Neste caso, as candidatas a solução são os indices 1 até 1000, e o candidato c é válido se P[c] = 1. Agora, suponha que o primeiro bit de P é igualmente provavel ser 0 or 1, mas cada bit depois é igual ao anterior 90% das vezes. Se os candidatos forem enumerados em ordem crescente, 1 até 1000, o número t de candidatos examinados antes do correto será ,em média, 6. De outra maneira, se os candidatos forem enumerados na ordem 1,11,21,31...991,2,12,22,32 etc…, o valor esperado de t sera apenas um pouco maior de 2. No geral, o espaço de busca deve ser enumerado de maneira que o próximo candidato é terá uma maior probabilidade de ser válido, dado que o teste anterior não foi.

Alternativas a busca por força bruta[editar | editar código-fonte]

Existem muitos outros métodos de busca, ou meta-heurísticas, que foram concebidos para tirar vantage de vários tipos de conhecimentos parciais sobre a solução. Heurísticas também podem ser usadas para eliminarem partes da busca. Um exemplo disso é o princípio minimax para buscar árvores de jogo, que elimina muitas sub-árvores no estado inicial da busca. Em algumas áreas, como análise de linguagens, técnicas como análise de gráfico podem explorar as restrições do problema para reduzir um problema de complexidade exponencial em um problema de complexidade polinomial. O espaço de busca dos problemas podem ser reduzidos substituindo o problema inteiro por uma versão simplificada. Por exemplo, no xadrez por computador, ao invés de computar o a árvore minimax de todos os movimentos possíveis para o resto do jogo inteira, uma árvore mais limitada de possibilidades minimax é computada, com a árvore sendo podada a um certo número de movimentos, e o resto da árvore sendo aproximado por uma função de avaliação estática.

Em criptografia[editar | editar código-fonte]

Em criptografia, um ataque de força bruta envolve checar sistematicamente todas as possíveis chaves até a chave correta ser encontrada. Esta estratégia pode ser em teorica usada contra qualquer dado encriptografado1 por um hacker que não pode tirar vantagem de alguma fraqueza na encriptação que faria a tarefa mais fácil.

O comprimento da chave usada na encriptação determina a praticabilidade de se fazer um ataque de força bruta, já que chaves mais longas são exponencialmente mais difíceis do que chaves menores. Uma das medidas da força de encriptação é o tempo que, teoricamente, levaria para um hacker conseguir lançar um ataque de força bruta bem-sucedido contra ela.

Referências

  1. Christof Paar, Jan Pelzl, Bart Preneel. Understanding Cryptography: A Textbook for Students and Practitioners. [S.l.]: Springer, 2010. p. 7. ISBN 3642041000