Baixe 05 - projeto forcabruta e outras Notas de estudo em PDF para Engenharia Telemática, somente na Docsity! Análise e Técnicas de Algoritmos Projeto de Algoritmos Força Bruta Tiago Massoni análise e projeto
(design) em
software
O
= -
prt
co
a -”
al
— E
Algumas técnicas de projeto de algoritmos força bruta backtracking branch and bounds método húngaro greedy dividir para conquistar programação dinâmica algoritmos aleatórios, etc. 5 Algumas técnicas de projeto de algoritmos força bruta backtracking branch and bounds método húngaro greedy dividir para conquistar programação dinâmica algoritmos aleatórios, etc. 5 OU TUDO MISTURADO!! Trade offs Força bruta (incremental) Aplicável a quase todos os problemas Em geral não resulta em algoritmos eficientes, mas para entradas pequenas propósitos teóricos e educacionais poucas limitações sobre a entrada 8 Exemplos 9 Exemplos Soma de elementos em uma sequência 9 Exemplos Soma de elementos em uma sequência Busca por elementos com certas propriedades em uma sequência Ordenação de elementos Calculo do fatorial 9 string matching string texto (n) e string procurada (m) m ≤ n encontrar i, índice do caractere mais a esquerda em texto da primeira substring correspondente ‘a procurada 10 string matching string texto (n) e string procurada (m) m ≤ n encontrar i, índice do caractere mais a esquerda em texto da primeira substring correspondente ‘a procurada 10 Exercício Dado duas cadeias de caracteres, A e B, determinar se A é substring de B. Exemplo: A = “casa” e B = “acasalamento” -> true A = “acasalamento” e B = “casa” -> false A = “feliz” e B = “felicidade” -> false Alguma maneira de responder ao 2º exemplo sem fazer comparações de caracteres? Busca exaustiva • Busca de uma elemento com certas propriedades dentro de um domínio – exemplo simples: em um vetor, quais dois elementos tem a soma mais próxima de um valor k 13 Busca exaustiva • problemas de otimização – encontrar elementos (parâmetros) que maximizem ou minimizem certas características desejáveis • ex: uso de um grafo para checar o trajeto mais econômico / problemas do troco, mochila 13 Caixeiro Viajante
2
o MA »
VE S 84 Db)
8 A 4
aa a
Cc) f 4)
Caixeiro Viajante
2
2.0
8 Ne se 4
x
EN
/ N
/ N
/ N
(e) | (td)
Trajeto
a>b>ec>d=>a
a>b>d>c>a
a>c>b>d-=a
a>c>d>b>a
a>d>b>e>a
a>d>ec>b->a
Custo
2+9+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+9+2 = 17
Caixeiro Viajante
0.
8. e
Trajeto Custo
a>b>c>d>a — 2+3+7+5=17
a>b>d>c>a — 2+4+7+8=21
a>eobod>a — 8+3+4+5=20
a>ec>d>b>a 8+7+4+2 = 21
a>d>b>e>a — 5+4+9+8=20
asd>esb>a 5+7+9+2 = 17
16
