Saltar para o conteúdo

Algoritmos/Reconhecimento de padrões/Algoritmo de Força Bruta

Origem: Wikilivros, livros abertos por um mundo aberto.

Algoritmo de Força Bruta

[editar | editar código-fonte]

O algoritmo de força bruta, (também conhecido por algoritmo ingênuo ou busca exaustiva) no campo de reconhecimento de padrões, é um teste exaustivo de atributos em uma base de dados. Esta é uma técnica trivial, uma solução geral, onde são testadas todas as possibilidades de solução existentes de um determinado problema. A busca por força bruta é fácil de ser implementada, e sempre vai achar a solução do problema se a mesma existir. Porém, sendo o custo proporcional ao número de instâncias, quanto mais candidatos à solução o problema tem, maior é o custo de execução do seu algoritmo. Por esse motivo, o algoritmo de força bruta só é utilizado em casos onde o tamanho do problema é limitado, quando há o uso preliminar de alguma heurística/técnica de redução a ser aplicada nos candidatos à solução do problema, ou quando a facilidade de implementação tem mais importância que a velocidade de execução.

Implementação

[editar | editar código-fonte]

O algoritmo de força bruta pode ser reproduzido em quatro passos simples:

  1. primeiro(S): seleciona o primeiro candidato à solução S.
  2. próximo(S, c): seleciona o próximo candidato à solução S depois de c.
  3. validar(S,c): testa se candidato c é uma solução de S.
  4. fim(S,c): usa a solução c de S como resposta ao problema.

Quando não há mais possíveis candidatos, o passo 2 retorna um candidato nulo.

Pseudo-código

[editar | editar código-fonte]
c ← primeiro(S)
enquanto c ≠ vazio faça
    se validar(S,c) então fim(S, c)
    c ← próximo(S,c)
fim enquanto
c = primeiro(S);
while (c != null) {
    if (validar(S,c)) {
        fim(S, c);
    }
    c = próximo(S,c);
}

Aplicações atuais

[editar | editar código-fonte]

O exemplo de aplicação ineficiente do algoritmo de força bruta é dado muitas vezes nas disciplinas de Algoritmos e Estruturas de Dados II, Algoritmo em Grafos, Projeto e Análise de Algoritmos e Laboratório de Projeto e Análise de Algoritmos. Temos como principais aplicações exemplificadas os problemas de Caixeiro Viajante (TSP), o Problema das Oito Damas, o Passeio do Cavalo e o ataque de força bruta na área da criptografia (onde são testadas todas as chaves de modo sistemático até que se encontre a correta).

Aplicação em reconhecimento de padrões

[editar | editar código-fonte]

O força bruta é o método mais óbvio para casamento de padrão, o que não necessariamente é algo bom. Na verdade ele tem um custo muito ruim pois há sobreposição exaustiva (e desnecessária) de padrão por sobre posições do texto, já que o método resume-se em testar cada posição do texto, sobrepondo um padrão e testando se ambos casam.

Por obrigatoriamente ter que percorrer todas as soluções possíveis, o algoritmo de força bruta é sempre um pior caso, e sua complexidade é exponencial (podendo ser reduzida à polinomial com o uso de heurísticas como é feito no algoritmo minimax).