Força bruta

Origem: Wikipédia, a enciclopédia livre.

A força bruta é uma abordagem simples para resolver um determinado problema, geralmente baseado diretamente na declaração do mesmo e nas definições dos conceitos envolvidos. Trata-se da técnica de projeto de algoritmos de mais fácil codificação, porém quase sempre de complexidade elevada.

Geralmente consistem em soluções simples e diretas ao problema. Exemplo:

Problema: Dado um número a e um inteiro n não-negativo, calcule aⁿ.

Definição da exponenciação: aⁿ = a . a . a ... a (n vezes)

Solução: Simplesmente fazer a multiplicação de a por a n vezes.

Outros Exemplos:

• mdc(m,n)
• multiplicação de matrizes.

Embora raramente seja uma fonte de esperteza ou eficiência, a força bruta não deve ser deixada de lado. Esta consiste em uma estratégia importante no projeto de algoritmos. Uma característica importante é que a força bruta é aplicada a uma grande variedade de problemas, característica a qual outras técnicas não possuem. Outra característica é que, para alguns problemas, a força bruta produz algoritmos razoáveis de pelo menos alguns valores práticos sem limitação no tamanho da instância. Por último, quando raramente o ataque por força bruta for utilizado, ou para projetar algoritmos melhores é injustificável, ou até para pequenas instâncias, a técnica de força bruta é uma boa abordagem.

[editar] Aplicando a Força Bruta 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 itens (números, caracteres [letras do alfabeto], strings, etc.). Assim, com a definição do problema, atacamos este de maneira simples e direta (ignorando os algoritmos já conhecidos e mais eficientes).

[editar] Ordenação por Inserção

Uma das formas de resolver o problema é atacá-lo assim: Procuramos o melhor elemento e o colocamos na primeira posição, operando sucessivamente até finalizar a operação. Portanto, o algoritmo trabalha da seguinte maneira: dado um passo 0 ≤ i < n-1

[editar] Busca de Padrões

A busca de padrões (amplamente utilizada na informática) consiste em dado um conjunto de caracteres de tamanho n (que alguns chamam de “texto”) e outro conjunto menor ou igual chamado de padrão (com tamanho m). Assim, é realizada a procura no texto da posição (se ocorrer) referente ao padrão dado. Mais precisamente, queremos achar o índice o qual inicia o padrão no texto. Se for o caso, podemos verificar o texto todo para 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. Algoritmo:

           BuscaPadraoBF(T[0 ... n-1], P[0 ... m-1])
                        para i <-- 0 até n – m faça
                                j <-- 0
                                enquanto j < m e P[j] = T[i + j] faça
                                        j <-- j + 1
                                se j = m 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 deslocar-se 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 mostrou-se linear, Θ(n+m) = Θ(n).

[editar] Aplicando a Força Bruta em Problemas Avançados

[editar] Problema do Par Mais Próximo

O problema do par mais próximo consiste em achar os dois pontos mais próximos em um conjunto de n pontos. Por simplicidade, vamos trabalhar com o plano cartesiano (x, y). Assumimos que estes estão representados em coordenadas do eixo x e y e a distância seja calculada pela distância Euclidiana. A força bruta irá percorrer o conjunto, e selecionar o par com menor distância. É lógico que ignoramos pontos iguais. Algoritmo:

           ParProximoBF(P)
                        dmin <-- ∞
                        para i <-- 1 até n – 1 faça
                                para j <-- i+1 até n faça
                                        d <-- raiz((xi = xj)² + (yi –yj)²)
                                        se d < dmin
                                                dmin <-- d
                                                ind1 <-- i
                                                ind2 <-- j
                        retorne ind1,ind2

Assim, temos a operação básica sendo o cálculo da distância Euclidiana. Porém o uso de cálculo da raiz (por mais que pareça trivial) é muito pesado (e sempre aproximado). Portanto, devemos evitá-lo! Um truque que evita a raiz é utilizar a soma dos quadrados somente. Isso mesmo, é só tirar a raiz. O comportamento da solução não será afetado. E, na prática, será melhor executado. Com essa característica, temos que o algoritmo cresce:

Outros exemplos de problemas avançados são: Perímetro Convexo, Caixeiro Viajante e Problema da Mochila.

Este artigo é um esboço sobre Programação. Você pode ajudar a Wikipédia expandindo-o.