Cap. 3 Força Bruta

Prévia do material em texto

FORCA BRUTA
Capítulo III
Força Bruta
 Uma abordagem simples, geralmente baseado 
directamente na declaração do problema e 
definições dos conceitos envolvidos basta fazê-
lo, e não ser muito elaborada.
 Exemplos:
1. Cálculo de an (a>0, n um inteiro não negativo).
2. Cálculo de factorial de n
3. Multiplicação de duas matrizes
4. Procura de uma chave de um determinado valor 
numa lista.
Fo
rç
a-
B
ru
ta
Então, quando e porque Força Bruta
 Por que não a força bruta?
◦ Quando não é possível criar um algoritmo elegante
◦ Quando não tiver uma chance de ver os padrões escondidos 
necessário para obter uma solução óptima
◦ Para problemas onde existem soluções que são melhores do 
que todos os pares, a força bruta não será o ideal.
 Porquê força bruta?
◦ Extremamente fácil de criar
◦ O método pode ser aplicado a uma grande variedade de 
problemas (o que não é verdade para um monte de outras 
estratégias, como podemos ver nos próximos capítulos)
◦ Funciona bem para valores pequenos (tamanhos de entrada) e 
é fácil de implementar
◦ Despesas de um algoritmo mais avançado não pode ser 
justificada
 Apenas alguns casos difíceis de resolver
Fo
rç
a-
B
ru
ta
Algoritmo de Ordenação usando a força bruta
Ordenação por Seleção
 Escanea a lista para encontrar o seu menor elemento e trocá-lo 
com o primeiro elemento. Em seguida, a partir do segundo 
elemento, escanea os elementos à direita da mesma para 
localizar o menor entre elas e trocá-lo com os segundos 
elementos.
Geralmente, na passagem i (0 ≤ i ≤ n–2 ), encontra-se o menor 
elemento em A [i .. n-1] e troca-o com A [i]:
A[0] ≤ . . . ≤ A[i-1] | A[i], . . . , A[min], . . ., A[n-1]
na sua posição final
 Exemplo: 7 3 2 5
 Exemplo: 89 45 68 90 29 34 17
Fo
rç
a-
B
ru
ta
Análise de ordenação por selecção
Algoritmo OrdSeleccao( A[0..n–1])
//Ordena dos elementos de um dado vector
//Entrada: Um vector A[0..n–1] de elementos não ordenados
//Saida: Um vector A[0..n–1] ordenada seguindo uma certa ordem
para i <– 0 até n – 2 faça
min <- i
para j < - i+1 até n – 1 faça
se A[j] < A[min] nin <- i
troca A[i] e A[min)
Fo
rç
a-
B
ru
ta
Análise
 Eficiência de tempo:
Nota: o nº de troca só é Θ (n), ou 
exactamente n–1 
-Isso é bom ou ruim?
)(
2
)1(
1...)3()2()1(
)1(
]1)1()1[(
1)(
2
2
0
2
0
2
0
1
1
nO
nn
nnn
in
in
nC
n
i
n
i
n
i
n
ij


















Fo
rç
a-
B
ru
ta
Ordenação por Bubble sort
Exemplo:
 7 3 2 5
 89 45 68 90 29 34 17
Algoritmo Bubblesort( A[0..n–1])
//Ordena dos elementos do vector A[0..n–1]) usando bubble sort
//Entrada: Um vector A[0..n–1] de elementos não ordenados
//Saida: Um vector A[0..n–1] ordenada seguindo uma certa ordem
Para i <– 0 até n – 2 faça
min <- i
Para j < - 0 até n – 2 – i faça
se A[j+1] < A[j] 
troca A[j] e A[j+1]
Fo
rç
a-
B
ru
ta
Análise
Nota: Quantas trocas devem ocorrer 
no pior dos casos? 
Ou seja, olhe para os códigos de 
ordenação por selecção e bubble 
sort e observe onde a troca de 
comandos estão. 
 Eficiência de tempo:
)(
2
)1(
1...)3()2()1(
)1(
]10)2[(
1)(
2
2
0
2
0
2
0
2
0
nO
nn
nnn
in
in
nC
n
i
n
i
n
i
in
j









 








Fo
rç
a-
B
ru
ta
Melhoria de força bruta
 Com a força bruta, é frequentemente possível 
fazer pequenas coisas que diminuem o tempo 
de execução.
◦ Estes geralmente não altera os limites assintóticos.
 Exemplo: Pesquisa Sequencial
◦ Certifique-se de que se tem o valor procurado 
anexada ao final da lista.
 Dessa forma, o item terá que ser encontrado e não terão 
que verificar constantemente para o fim da lista.
◦ Obviamente, poderíamos primeiro classificar nossa 
lista
Fo
rç
a-
B
ru
ta
Força Bruta: Correspondência de Sequencias.
 padrão: uma sequência de m caracteres para pesquisar.
 texto: a string (longo) de n caracteres onde será pesquisado o 
padrão
 problema: encontrar um substring no texto que corresponde ao 
padrão.
Algoritmo:
Passo 1 Alinhe padrão no início do texto
Passo 2 Movendo da esquerda para a direita, comparar cada 
caractere padrão para o caractere correspondente no texto até
- todos os caracteres se encontram correspondentes 
(busca bem-sucedida), ou
- Uma incompatibilidade é detectada
Passo 3 Enquanto padrão não é encontrado e o texto ainda não 
está exausta, realinhar padrão uma posição para a direita e 
repita o passo 2
Fo
rç
a-
B
ru
ta
Exemplos de correspodencia de caracteres
usando a força bruta
1. Padrão: 001011
Texto: 10010101101001100101111010
2. Padrão: Feliz
Texto: Nunca é muito tarde para ter uma 
infância feliz.
3. Padrão: happy
Texto: happhapphapphappy
4. Padrão: aaab
Texto: aaaaaaaaaaaaaaaaaaaaaaaaaaaab
Fo
rç
a-
B
ru
ta
Pseudocódigo e Eficiência
 Eficiencia: pior Caso?
Algoritmo FBCorrespCarateres(T[0..n–1], P[0..m–1])
//Implementa a correspondência de sequencia usando a força bruta
//Entrada: Um vector T[0..n–1] de n caracteres representando o texto e
// um vector P[0..m–1] de m caracteres representando o padrão
//Saida: O index do primeiro carácter no texto que começa a 
//correspondencia de subsequencia ou -1 no caso de insucesso.
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 retorna i
retorna -1
Fo
rç
a-
B
ru
ta
Avaliação polinomial
Problema: Encontre o valor do polinômio
p(x) = anx
n + an-1x
n-1 +… + a1x
1 + a0
no ponto x = x0
Algoritmo
p←0.0
para i ←n até 0 faça
potencia←1
para j← 1 até i faça //calcula xi
potencia← potencia ∗ x
p←p + a[i] ∗ potencia
retorna p
Eficiência?
Fo
rç
a-
B
ru
ta
Avaliação polinomial: Melhoria
Podemos melhorar este algoritmo se avaliamos este polinómio de 
direita a esquerda:
p(x) = anx
n + an-1x
n-1 +… + a1x
1 + a0
no ponto x = x0
Melhor algoritmo:
p←a[0]
potencia←1
para i ←1 até n faça
potencia ← potencia ∗ x
p←p + a[i] ∗ potencia
retorna p
Eficiência?
Fo
rç
a-
B
ru
ta
Problema de distância mínima entre os pontos
 Encontrar a menor distância entre pontos num 
conjunto de n pontos (no plano cartesiano).
 Algoritmo:
Calcular a distância entre cada par de pontos 
distintos e retornar os índices dos pontos para os 
quais a distância é o menor.
 Qual é a fórmula para a distância entre dois 
pontos no plano cartesiano (XY)?
Fo
rç
a-
B
ru
ta
22 )()(),(
),(
),(
jijiji
jjj
iii
yyxxPPd
yxP
yxP



Problema de distância mínima entre pontos (cont.)
Eficiencia?
Como torna-lo mais rápido?
Algoritmo pontosproximos(P)
//Entrada: a lista P de n (n≥2) pontos P1=(x1,y2), …, Pn=(xn, yn) 
//Saida: Indices ind1 e ind2 de par de pontos mais próximos
…
dmin
para i de 1 até n–1 passo 1 faça
para j de i+1 até n passo 1 faça
if d <dmin
dmind;
ind1 i
ind2 j
retorna ind1, ind2
Fo
rç
a-
B
ru
ta
Busca Exaustiva
 A solução de força bruta para um problema que 
envolve busca de um elemento com uma 
propriedade especial, geralmente entre os objetos 
combinatórios como permutações, combinações ou 
subconjuntos de um conjunto.
◦ Método:
Gerar uma lista de todas as possíveis soluções para o 
problema de forma sistemática (ver algoritmos no cap. 
5.4) 
◦ avaliar as possíveis soluções, uma por uma, 
desqualificandoos inviáveis e, para resolver problema de 
optimização mantem a melhor encontrada
◦ quando a pesquisa termina, anunciar a solução (s) 
encontrada(s)Fo
rç
a-
B
ru
ta
Problema de Caixeiro Viajante
 O problema pede para se encontrar a viajem de custo 
mínimo partindo da cidade origem passando por n 
cidades e terminando na cidade origem. Cada cidade é 
visitada somente uma vez.
 O problema pode ser modelado pelo grafo dirigido 
ponderado, com os vértices representado cidades e 
ramos as distancias.
 Problema pode ser reduzido ao problema de busca de 
menor circuito Hamiltoriano. (O circuito de Hamilton é 
definido como o ciclo que passa pelos todos vértices de 
um grafo somente uma vez)
 Também pode-se observar que o circuito Hamiltoriano
pode ser definido como uma sequencia de n+1 vértices 
adjacentes vi0, vi1, …, vin–1, vi0 onde o primeiro vértice da 
sequencia é o mesmo que o último enquanto que o 
restante n–1 são distintos.F
o
rç
a-
B
ru
ta
Exemplo 1: Problema de Caixeiro viajante
usando força bruta
 Dadas n cidades com distâncias conhecidas entre cada par, 
encontrar a menor rota que passa por todas as cidades 
exactamente uma vez, antes de retornar à cidade de partida.
 Em alternativa: Encontre o circuito hamiltoniano mais curto 
em um grafo conexo ponderado
a b
c d
2
5
8 7
3
1
Viajem Distancia
abcda L=2+8+1+7=18
abdca L=2+3+1+5=11 
acbda L=5+8+3+7=23
acdba L=5+1+3+2=11 
adbca L=7+3+8+5=23
adcba L=7+1+8+2=18Fo
rç
a-
B
ru
ta
Exemplo 2: Problema de Mochila
 Sejam dados n items:
◦ pesos: p1 p2 … pn
◦ valores: v1 v2 … vn
◦ a capacidade da Mochila: C
 Encontre subconjunto mais valioso dos itens que se encaixam na 
mochila
Exemplo: Mochila com capacidade C=16
Fo
rç
a-
B
ru
ta Item Peso Valor
1 2 $20
2 5 $30
3 10 $50
4 5 $10
Problema de mochila usando busca exaustiva
Subconjunto Peso Total Valor Total
{1} 2 $20
{2} 5 $30
{3} 10 $50
{4} 5 $10
{1,2} 7 $50
{1,3} 12 $70
{1,4} 7 $30
{2,3} 15 $80
{2,4} 10 $40
{3,4} 15 $60
{1,2,3} 17 não cabe
{1,2,4} 12 $60
{1,3,4} 17 não cabe
{2,3,4} 20 não cabe
{1,2,3,4} 22 não cabe
Eficiencia: 2nFo
rç
a-
B
ru
ta
Exemplo 3: O Problema da Atribuição
 Existem n pessoas que precisam ser atribuídos n tarefas, uma pessoa 
por trabalho. O custo de atribuição de pessoa i a tarefa j é C [i, j].
 Encontre um trabalho que minimiza o custo total.
 Algorítmo: 
◦ Gerar todas as atribuições legítimas, calcule seus custos e selecionar o mais 
barato.
 Quantas tarefas existem?
 Colocar o problema como aquele sobre a matriz de custo:
Fo
rç
a-
B
ru
ta
Tarefa 1 Tarefa 2 Tarefa 3 Tarefa 4
Pessoa1 9 2 7 8
Pessoa2 6 4 3 7
Pessoa3 5 8 1 8
pessoa4 7 6 9 4
Problema de atribuição usando busca exaustiva
 Atribuição (col.#s) Custo Total
<1, 2, 3, 4> 9+4+1+4=18
<1, 2, 4, 3> 9+4+8+9=30
<1, 3, 2, 4> 9+3+8+4=24
<1, 3, 4, 2> 9+3+8+6=26
<1, 4, 2, 3> 9+7+8+9=33
<1, 4, 3, 2> 9+7+1+6=23
etc.Fo
rç
a-
B
ru
ta













4967
8185
7346
8729
C
Comentários finais sobre busca exaustiva
 Algoritmos de busca exaustiva é executado 
em um quantidade real de tempo apenas 
em casos muito pequenos. Em alguns casos, 
não são melhores alternativas!
◦ circuitos de Euler
◦ caminhos mais curtos
◦ árvore geradora mínima
◦ problema de atribuição
Em muitos casos, a pesquisa exaustiva ou a sua 
variação é a única forma conhecida para obter a 
solução exacta
Fo
rç
a-
B
ru
ta