Força Bruta

Força bruta

Em ciência da computação, força bruta (ou busca exaustiva) é uma algoritmo trivial, mas de uso muito geral que consiste em enumerar todos os possíveis candidatos de uma solução e verificar se cada um satisfaz o problema.

Por exemplo, um algoritmo para encontrar os divisores de um número natural n é enumerar todos os inteiros de 1 a n, e verificar para cada um se ele dividido por n resulta em resto 0.

Esse algoritmo possui uma implementação muito simples, e sempre encontrará uma solução se ela existir. Entretanto, seu custo computacional é proporcional ao número de candidatos a solução, que, em problemas reais, tende a crescer exponencialmente. Portanto, a força bruta é tipicamente usada em problemas cujo tamanho é limitado, ou quando há uma heurística usada para reduzir o conjunto de candidatos para uma espaço aceitável. Também pode ser usado quando a simplicidade da implementação é mais importante que a velocidade de execução, como nos casos de aplicações críticas em que os erros de algoritmo possuem em sérias conseqüências.

Aplicação na ordenação

Um exemplo clássico de aplicação de algoritmos da classe da força bruta é a ordenação, que pode ser aplicada nos mais diferentes tipos de dados.

Por exemplo, uma das formas de resolver o problema consiste em procurar o menor elemento e colocá-lo na primeira posição, operando sucessivamente com os demais elementos da lista a ser classificada até finalizar a operação, um método conhecido como ordenação por inserção.

Outro exemplo é a busca de padrões. Dada uma cadeia de caracteres de tamanho n (o "texto") e outra cadeia com tamanho m menor ou igual chamada "padrão". É realizada uma procura no "texto" pelo "padrão", verificando-se todo o texto em busca de múltiplas ocorrências. O funcionamento da busca de padrão é simples: se o primeiro caractere é idêntico à um referente no texto, todos os sucessores devem ser idênticos também, até finalizar o padrão. Caso ocorra que um caractere não seja igual, desloca-se o padrão em um caractere até chegar ao fim do texto ou encontrar o padrão.

rotina BuscaPadrao(texto[0 ... n-1], padrao[0 ... m-1])

para i ← 0 até n – m faça

j ← 0

enquanto j <>

j ← j + 1

se j = m então

retorne i

retorne -1

Note que o algoritmo desloca-se após a comparação do primeiro caractere, porém nem sempre é assim. O pior caso é "muito pior": o algoritmo tem que comparar todos os m caracteres antes de se deslocar, e isso pode ocorrer para cada uma das n − m + 1 tentativas. Portanto, o pior caso para este algoritmo está em θ(n.m). Para textos de linguagem natural, o caso médio é melhor (pois ocorre nas primeiras comparações). Até em textos aleatórios, o comportamento se mostra linear, θ(n + m) = θ(n).