Abordagem Exata versus Aproximada

Prévia do material em texto

Análise de Algoritmos
ABORDAGEM EXATA vs APROXIMADAABORDAGEM EXATA vs APROXIMADA
Bacharelado em Ciência da Computação
Flávia Coelho
flaviacoelho@ufersa.edu.br
Atualizado em Setembro de 2016
 
Sumário
● Classes de Problemas Computacionais
● Métodos Exatos
● Métodos Aproximados
 
Classes de Problemas 
Computacionais
● Decisão 
● Localização
● Otimização
 
Problemas de Decisão
● Problemas em que a solução é SIM ou 
NÃO
● Exemplo
● Teste de PRIMALIDADE
– Dado um inteiro positivo n, determine se n é 
primo
 
Problemas de Localização
● Determinam uma certa estrutura que 
satisfaça um conjunto de propriedades 
específicas
● Exemplo
● Fatoração, em que 
instâncias são inteiros 
positivos e as soluções são 
um conjunto de seus fatores 
primos
 
Problemas de Otimização
● São problemas de localização em que as 
propriedades satisfazem critérios de 
otimização
● CAIXEIRO VIAJANTE
– Um caixeiro viajante tem de visitar n cidades 
diferentes, iniciando e encerrando sua viagem na 
primeira cidade. Não importa a ordem em que as 
cidades são visitadas e de cada uma delas pode-
se ir diretamente a qualquer outra. A solução 
consiste em descobrir a rota de custo mínimo 
para a viagem!
 
Complexidade dos Problemas
● É relevante distinguir entre problemas que 
podem ser ”resolvidos” dos que não podem 
● Problemas considerados tratáveis   são →
considerados fáceis e são resolvidos por 
algoritmos de tempo polinomial 
● Problemas considerados intratáveis   são →
considerados difíceis e são resolvidos somente 
por algoritmos de tempo exponencial (ou pior)
 
Métodos Exatos
● Visam encontrar a melhor solução para o 
problema
● Para problemas de localização/otimização
● O foco é a solução ótima global
● Precisamos considerar a influência da 
complexidade exponencial (ou pior!) 
 
Métodos Aproximados
● Para problemas difíceis, é comum não 
exigir que o algoritmo tenha sempre de 
obter a melhor solução
● Procuramos algoritmos eficientes que 
tentam encontrar uma solução que seja a 
mais próxima possível da melhor solução
● Alternativas
● Algoritmo aproximado
● Heurística
 
Algoritmo Aproximado
● Gera soluções aproximadas dentro de um 
limite para a razão entre a solução ótima 
e a produzida pelo algoritmo aproximado
● Comportamento do algoritmo aproximado 
é considerado em termos da qualidade 
dos resultados
 
Heurística
● Métodos ou algoritmos exploratórios 
● Soluções buscadas por aproximações 
sucessivas, avaliando­se os progressos 
alcançados até que o problema seja 
resolvido
● Embora a exploração seja feita de forma 
algorítmica, o progresso é obtido pela 
avaliação puramente empírica do resultado
 
Heurística
● Não assegura a solução ótima, mas somente 
uma solução válida, aproximada
● Frequentemente, não é possível justificar em 
termos estritamente lógicos, a validade do 
resultado
● Pode produzir um bom resultado ou até obter 
a solução ótima, ou não produzir solução 
alguma, ou uma solução distante da ótima
 
Heurística
● Heurística procura 'boas' soluções 
(próximas da otimalidade) a um custo 
computacional razoável
● Mas, não há garantia da otimalidade
● Desvantagem
● Dificuldade de fugir de ótimos locais, na 
busca do ótimo global
● O que deu origem à metaheurística
 
Metaheurística
● Métodos destinados a encontrar uma boa 
solução, eventualmente a ótima, consistindo 
na aplicação, em cada passo, de uma 
heurística subordinada, a qual tem que ser 
modelada para cada problema específico
● Principal característica
● Capacidade de escapar de ótimos locais, permitindo a 
busca em regiões mais promissoras
● O desafio é produzir, em tempo mínimo, soluções tão 
próximas quanto possíveis da solução ótima
 
Exemplo
● Um grupo de pesquisadores, em atividade 
numa floresta tropical, ficou perdido. Como a 
carga da bateria do único celular da 
expedição, estava acabando, somente 
conseguiram avisar à base, da situação atual 
e que estavam presos no vale mais profundo 
da região
● De posse dessas informações, foi criado um 
grupo de resgate
 
Exemplo
● Levando em consideração que não existia 
estudo topográfico sobre a região, que era 
extensa, o grupo de resgate viu­se 
dividido entre três opiniões distintas
 
Exemplo – Primeira Sugestão
● Que um avião tentasse percorrer a região na 
íntegra, identificando todos os vales ali contidos 
para que ao término fossem comparados, e o 
maior deles seria o local exato para o resgate
● Certamente encontraria o local exato   →
MÉTODO EXATO
● Mas, não seria aceita, porque o tempo gasto na 
procura comprometeria a integridade física dos 
pesquisadores
 
Exemplo – Segunda Sugestão
● De que a cada dia fosse escolhida 
aleatoriamente uma direção, e nela fossem 
também identificados os vales existentes e ao 
término de alguns dias, seria escolhido o vale 
mais profundo até então, e se tentaria o 
resgate
● Provavelmente, também não obteria êxito nas 
buscas, pois estas seriam realizadas sem 
qualquer informação prévia da região a ser 
pesquisada   → HEURÍSTICA 'CEGA'
 
Exemplo – Terceira Sugestão
● Meio termo entre as duas anteriores
● Baseado nas informações colhidas do grupo de 
pesquisadores nos dias anteriores, a ideia seria 
utilizá­las para que se determinasse um conjunto de 
regiões menores e somente ali fosse intensificada a 
procura pelo vale mais profundo
● A idéia conjuga aspectos que permitem se esquivar 
dos erros ocorridos nas idéias anteriores, pois leva 
em consideração todas as informações previamente 
conhecidas do espaço de busca a ser explorado   →
METAHEURÍSTICA
 
Técnicas de Projeto de Algoritmos
P r o g r a m a ç ã o D i n a m i c a
B r a n c h - a n d - B o u n d
B r a n c h - a n d - C u t
B r a n c h - a n d - P r i c e
O u t r o s
M e t o d o s E x a t o s
G u l o s a ( G r e e d y )
M e l h o r i a
C o n s t r u ç ã o
P a r t i c i o n a m e n t o
D e c o m p o s i ç ã o
F o r m . M a t e m a t i c a
R e l a x a ç ã o
H e u r i s t i c a s
A l g o r i t m o s G e n e t i c o s
S i m u l a t e d A n n e a l i n g
B u s c a T a b u
G R A S P
M e t a - H e u r i s t i c a s
T i m e s A s s i n c r o n o s
L o g i c a F u z z y
R e d e s N e u r a i s
E s p e c i a i s
M e t o d o s A p r o x i m a d o s
M e t o d o s d e R e s o l u ç ã o
 
Leitura Recomendada
N. Ziviani. Projeto de Algoritmos com 
Implementações em Java e C++. 
Thompson Learning, 2007, pp. 74, 390­
403
Melo, V. A. Metaheurísticas para o Problema 
do Caixeiro Viajante com Coleta de 
Prêmios. Dissertação de Mestrado, 
Instituto de Computação, Universidade 
Federal Fluminense, 2001
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21