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

Algoritmo de Força Bruta

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

Lógica

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

c ← primeiro(S)
enquanto c ≠ vazio faça
    se validar(S,c) então fim(S, c)
    c ← próximo(S,c)
fim enquanto

Java

c = primeiro(S);
while (c != null) {
    if (validar(S,c)) {
        fim(S, c);
    }
    c = próximo(S,c);
}

Aplicações atuais

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

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).

Bibliografia

• FABRO, João Alberto. Técnicas de Projeto de Algoritmos - Força Bruta. Acessado em: 20 de maio de 2017.
• SOUZA, Jairo Francisco de. Strings (Casamento de padrões). Acessado em: 22 de maio de 2017.
• MENOTTI, David. Aprendizado de Máquinas, Aprendizagem Evolucionária. Acessado em: 22 de maio de 2017.