Fundamentos de Programação II
Estratégias algorítmicas de
resolução de problemas
Prof. Msc. Everton Fernando Baro
2014/01
Agenda
●
Estratégias algorítmicas
–
Recursividade
–
Divisão e conquista
●
Balanceamento
–
Tentativa e erro
–
Algoritmos gulosos e aproximados
–
Programação dinâmica
Algoritmos gulosos
“A melhor solução é a que resolve o problema
mais imediato”
●
●
●
Também chamados algoritmos gananciosos
Escolhem a opção que parece ser a melhor no
momento (escolha ótima) e esperam que desta
forma consiga-se chegar a uma solução ótima
global
Utilizada para resolução de problemas de
otimização, que lidam com sequências de
passos que exigem decisão/escolha
Algoritmos gulosos
●
●
Tomam decisões com base apenas na
informação disponível, sem se preocupar com
os efeitos futuros
Algoritmos gulosos nunca reconsideram as
decisões tomadas, independentemente das
consequências
Algoritmos gulosos
●
Características gerais
–
Existe um problema a ser resolvido e um conjunto
de candidatos à solução
–
Durante a execução do algoritmo são criados dois
conjuntos
●
●
–
Avaliados + rejeitados
Avaliados + escolhidos
Uma rotina verifica se um conjunto de candidatos
produz uma solução
Algoritmos gulosos
●
Características gerais
–
Uma segunda rotina verifica se é ou não possível
adicionar candidatos a este conjunto para obter
pelo menos uma solução ótima
–
Uma rotina de seleção identifica qual dos
candidatos restantes é o melhor
–
Uma rotina objetivo retorna o valor da solução
encontrada
Problema do Troco
●
●
●
Suponha que tenhamos disponíveis moedas
com valores de 1.00, 0.50, 0.25, 0.10, 0.05 e
0.01
O problema é criar um algoritmo para obter um
determinado valor com o menor número de
moedas possível
O problema do troco é um algoritmo guloso
quando, após escolhida uma moeda para fazer
parte do conjunto solução, ela nunca mais é
retirada do conjunto
Problema do Troco
Problema do Troco
Problema do Troco
Dúvidas
Agenda
●
Estratégias algorítmicas
–
Recursividade
–
Divisão e conquista
●
Balanceamento
–
Tentativa e erro
–
Algoritmos gulosos
–
Algoritmos aproximados
–
Programação dinâmica
Algoritmos aproximados
●
●
●
Algoritmos com soluções polinomiais são
considerados fáceis
Algoritmos com soluções exponenciais são
considerados difíceis
Os algoritmos vistos até o momento tem
solução polinomial
–
●
O tempo computacional para apresentar a solução
cresce geometricamente em função do tamanho do
problema
Algoritmos difíceis são comuns na natureza
Algoritmos aproximados
●
●
Problemas de solução exponencial são
computacionalmente relacionados e formam
uma classe conhecida como NP
(nondeterministic polynomial)
A teoria do NP-Completo diz que um problema
NP tem solução polinomial se, e somente se,
todos os outros problemas NP puderem ser
resolvidos em tempo polinomial
Algoritmos aproximados
●
O problema do Caixeiro Viajante
–
Um caixeiro viajante deseja visitar n cidades de tal
forma que sua viagem inicie e termine em uma
mesma cidade, e cada cidade seja visitada uma
única vez
–
Supõe-se que sempre existe uma estrada entre
duas cidades quaisquer, o problema é encontrar a
menor rota que o caixeiro viajante pode utilizar em
sua viagem
Algoritmos aproximados
●
Para o exemplo abaixo, o percurso
<C1, C3, C4, C2, C1>
é solução para o problema, com distância 24
C1
4
9
8
C3
3
5
C2
8
C4
Algoritmos aproximados
●
●
Um algoritmo simples deveria verificar todas as
rotas possíveis e escolher a menor
Existem (n - 1)! rotas possíveis
–
●
●
●
permutação dos caminhos entre uma cidade e
outra
Para n cidades, n – 1 caminhos chegam até ela
Para cada caminho, são feitas n operações de
soma para calcular a distância
No total, n! operações de soma são realizadas
Algoritmos aproximados
●
No exemplo, n = 4 cidades
–
Para esse percurso, o algoritmo demoraria em
torno de 4! = 24 unidades de tempo
C1
4
9
8
C3
3
5
C2
8
C4
Algoritmos aproximados
●
Para 50 cidades, o algoritmo demoraria em
torno de 50! =~ 1064 unidades de tempo
–
●
!!!!!!!!!!
O que fazer?
–
Algoritmos aproximados geram soluções
aproximadas dentro de um limite para a razão entre
a solução ótima e a solução aproximada
Algoritmos aproximados
●
Enfoques para desenvolver algoritmos
aproximados
–
Algoritmos exponenciais usando Tentativa e Erro
●
●
●
Utiliza técnicas de poda para eliminar caminhos que não
levarão à solução ótima
Encontrar um algoritmo eficiente que não leva à
solução ótima, mas garantidamente próxima da
ótima
Encontrar algoritmos que, na média, é eficiente,
funcionando bem para as entradas que ocorrem
usualmente na prática
Dúvidas