Projeto e Análise de Algoritmos  
Aula 02 Técnicas de Projeto de Algoritmos  
(Força Bruta)  
Edirlei Soares de Lima  
<edirlei@iprj.uerj.br>  
Tipos Importantes de Problemas  
Problemas de Ordenação: Reorganizar os itens de uma dada  
lista em ordem crescente.  
Problemas de Busca: Encontrar um dado valor chamado de  
chave de busca em um dado conjunto.  
Processamento de Strings: Buscar uma dada palavra em um  
texto, avaliar a similaridade entre cadeias de caracteres, etc.  
Problemas de Grafos: Travessia de grafos (como visitar todos  
os pontos de uma rede), caminho mais curto (qual a melhor  
rota entre duas cidades), ordenação topológica.  
Tipos Importantes de Problemas  
Problemas Combinatoriais: Problemas onde é necessário  
encontrar um objeto combinatorial (permutações,  
combinações ou subconjuntos) que satisfaça certas restrições  
e tenha certas propriedades (maximizar um valor, minimizar  
um custo).  
Problemas Geométricos: Envolvem objetos geométricos com  
pontos, linhas e polígonos.  
Problemas Numéricos: Envolvem objetos matemáticos de  
natureza contínua: resolução de equações e sistemas de  
equações, integrais definidas, etc.  
Estratégias de Projeto de Algoritmos  
Força Bruta (Brute Force)  
Dividir e Conquistar (Divide and Conquer)  
Diminuir e Conquistar (Decrease and Conquer)  
Transformar e Conquistar (Transform and Conquer)  
Compromisso TempoEspaço (Space and Time Tradeoffs)  
Estratégia Gulosa (Greedy)  
Programação Dinâmica (Dynamic Programming)  
Voltando Atrás (Backtracking)  
Ramificar e Limitar (Branch and Bound)  
Algoritmos Aproximados  
Força Bruta  
A técnica de força bruta (também conhecida como a  
busca exaustiva) é um método para resolver um  
problema através de uma travessia completa (ou  
parcial) no espaço de busca do problema para se  
obter uma solução.  
Durante a busca, é possível podar (optar por não  
explorar) partes do espaço de busca, se for possível  
determinar que estas partes não têm qualquer  
possibilidade de conter a solução necessária.  
Força Bruta  
Geralmente, a força bruta é uma das estratégias mais  
fáceis de aplicar.  
Apesar de ser raramente uma fonte de algoritmos  
eficientes ou brilhantes, é uma importante estratégia  
de projeto de algoritmos.  
É aplicável a uma ampla variedade de problemas.  
Exemplo 1: Busca Sequencial  
Comparar elementos sucessivos de uma dada lista com um  
dada chave de busca até:  
Encontrar um elemento similar (busca bem sucedida) ou;  
A lista ser exaurida sem encontrar um elemento similar (busca mal  
sucedida).  
int busca(int n, int *vet, int elem)  
{
int i;  
for (i=0; i<n; i++){  
if (elem == vet[i])  
return i;  
}
return -1;  
}
Algoritmo Geral de Força Bruta  
1
. Listar todas as soluções potenciais para o problema de uma  
maneira sistemática.  
Todas as soluções estão eventualmente listadas;  
Nenhuma solução é repetida;  
2
3
. Avaliar as soluções, uma a uma, talvez, desqualificando as  
não práticas e mantendo a melhor encontrada até o  
momento.  
. Quando a busca terminar, retornar a solução encontrada.  
Exemplo 2: Caixeiro Viajante  
Problema: dadas n cidades com distâncias conhecidas entre  
cada par, encontrar o trajeto mais curto que passe por todas  
as cidades exatamente uma vez antes de retornar a cidade de  
origem (Traveling Salesman Problem (TSP)).  
Trajeto:  
Custo:  
2
7
A
C
B
a → b → c → d → a  
a → b → d → c → a  
a → c → b → d → a  
a → c → d → b → a  
a → d → b → c → a  
a → d → c → b → a  
2+3+7+5 = 17  
2+4+7+8 = 21  
8+3+4+5 = 20  
8+7+4+2 = 21  
5+4+3+8 = 20  
5+7+3+2 = 17  
5
3
8
4
D
Hipóteses: (n-1)!  
Complexidade: O(n!)  
Exemplo 3: Problema da Mochila  
Dados n itens:  
Pesos: w1, w2, ..., wn  
Valores: v1, v2, …, vn  
Uma mochila de capacidade W  
Problema: encontrar o subconjunto mais valioso de  
itens que caibam dentro da mochila (Knapsack  
Problem).  
Exemplo 3: Problema da Mochila  
Exemplo:  
Exemplo 3: Problema da Mochila  
Algoritmo de Força Bruta:  
1. Identificar todos os subconjuntos  
do conjunto de n itens dados;  
2
. calcular o peso total de cada  
subconjunto para identificar  
subconjunto praticáveis;  
3
. encontrar um subconjunto com o  
valor mais elevado entre eles.  
Exemplo 3: Problema da Mochila  
Como o número de subconjuntos de um conjunto de  
n
n elementos é 2 , a busca exaustiva leva a um  
n
algoritmo O(2 ).  
Assim, tanto para o problema do caixeiro viajante  
quanto da mochila, a busca exaustiva leva a  
algoritmos que são extremamente ineficientes.  
Estes problemas são chamados de problemas NP-  
hard.  
Exemplo 4: Par de Pontos mais Próximos  
Problema: Dados n pontos no plano, determinar dois  
deles que estão à distância mínima.  
ꢁꢂꢃꢄꢅꢆꢁꢄ(ꢇ1, ꢈ1, ꢇ2, ꢈ2) = (ꢇ1−ꢇ2)2 + (ꢈ1−ꢈ2)  
Exemplo 4: Par de Pontos mais Próximos  
Problema: Dados n pontos no plano, determinar dois  
deles que estão à distância mínima.  
Entrada: coleção de n pontos (X[1 . . n] e Y[1 . . n]).  
Saída: menor distância entre dois pontos da coleção.  
1
2
3
4
5
6
7
. PAR-MAIS-PROXIMO(X, Y, n)  
O(n2)  
. d +∞  
. para i ← 1 até n faça  
. para j ← 1 até n faça  
. se Distancia(X[i], Y[i], X[j], Y [j]) < d então  
d Distancia(X[i], Y[i], X[j], Y [j])  
. retorna d  
.
Força Bruta  
Outros algoritmos baseados em força bruta que  
veremos ao longo do curso:  
Multiplicação de Inteiros Grandes;  
Busca de Padrões em String;  
Maior Subsequência Comum;  
Bubble Sort;  
Selection Sort;  
Busca em Profundidade;  
Busca em Largura;  
Comentários sobre a Força Bruta  
Força bruta é uma estratégia direta para resolver um  
problema, geralmente baseada diretamente no enunciado do  
problema e definições dos conceitos envolvidos.  
Algoritmos de busca exaustiva são executados em uma  
quantidade de tempo realística somente para instâncias  
muito pequenas.  
Em muitos casos existem alternativas muito melhores!  
Em alguns casos, busca exaustiva (ou variação) é a única  
solução conhecida.  
Comentários sobre a Força Bruta  
Vantagens:  
Ampla aplicabilidade;  
Simplicidade;  
Fornece algoritmos razoáveis para alguns problemas.  
Desvantagens:  
Raramente fornece algoritmos eficientes;  
Alguns algoritmos força bruta são inaceitavelmente vagarosos;  
Não tão construtivo/criativo quanto outras técnicas de projeto de  
algoritmos.  
Exercícios  
Lista de Exercícios 02 Força Bruta/Busca  
Exaustiva  
http://www.inf.puc-rio.br/~elima/paa/  
Leitura Complementar  
Levitin. Introduction to the Design and  
Analysis of Algorithms, 3rd Edition, 2011.  
Capítulo 3: Brute Force and Exhaustive  
Search