Heurísticas e Metaheurísticas 01

Prévia do material em texto

ENP557 –Heur. e Metaheurísticas
Aula 01 –Algoritmos Exatos e Teoria da Complexidade
OTIMIZAÇÃO
 Muitos problemas consistem na busca da melhor
atribuição de valores a um conjunto de variáveis,
sujeito a um conjunto de restrições, de forma a
alcançar um objetivo determinado
 Essas variáveis possuem características discretas ou
continuas
 Dentre os problemas que são modelados com variáveis
discretas, encontram-se os problemas de otimização
combinatória
OTIMIZAÇÃO
 Uma atribuição de valores às variáveis que respeita
todas as restrições é dita como uma solução viável
 O conjunto de todas as possíveis atribuições de valores
às variáveis do problema é chamado de espaço de
busca.
 A melhor solução do espaço de busca é chamado de
solução ótima.
ALGORITMOS VS HEURISTICAS
 Um algoritmo é uma sequencia finita de instruções não
ambíguas que podem ser executadas em um
computador para resolver algum tipo de problema
 Heurísticas são algoritmos que nem sempre retornam
respostas (soluções) exatas para o problema ao qual
elas retratam
 Entretanto, espera-se que essas respostas sejam
próximas da solução exata do problema
HEURÍSTICAS
 Utilizamos heurísticas em vários casos
 Quando o tempo gasto pelo melhor algoritmo que
existe para o problema (estado da arte) é maior que o
tempo disponível
 Quando a quantidade de memoria necessária para se
resolver o problema é superior a quantidade de
memoria disponível
 A quantidade de dados a serem processados é muito
grande
 Quando não se sabe como resolver o problema de
forma exata
CLASSES DE PROBLEMA
 A definição original de NP (e seu uso mais comum até
os dias atuais) não esta relacionado à problemas de
busca, mas sim a problemas de decisão
 Problemas que remetem perguntas que podem ser
respondidas com decisões de SIM e NÃO
 Existe alguma atribuição que satisfaz a formula
booleana?
CLASSES DE PROBLEMA
 Existem problemas de busca que não podem ser
resolvidos em tempo polinomial?
 A maioria dos pesquisadores de algoritmos julgam que
sim
 É difícil de acreditar que uma boa em tempo
exponencial pode ser evitada para todos os casos
 Ou que sempre serão encontrados métodos que
desfaçam a complexidade de problemas difíceis
CLASSES DE PROBLEMA
CLASSES DE PROBLEMA
 A teoria da complexidade concentra-se nos problemas
de decisão
 As propriedades que são válidas para os problemas de
decisão também são válidas para os problemas de
otimização respectivo ao mesmo problema
CLASSE NP
 Nondeterministic Polynomial-time
 Problemas que podem ser resolvidos em tempo
polinomial em máquinas de Turing não determinísticas
 Classe de problemas cuja viabilidade de uma solução
pode ser verificada em tempo polinomial
CLASSE P
 Deterministic Polynomial-time
 Problemas que podem ser resolvidos em tempo polinomial
em maquinas de Turing determinísticas
 P ⊂ NP
 Exemplos:
 Ordenação
 Problema do caminho mais curto
 Programação linear
CLASSE NP-COMPLETE
 Transformação polinomial
 Um problema de decisão A transforma-se
polinomialmente em um problema de decisão B se
 Dada qualquer entrada 𝐼𝐴 para o problema A, pode-se
construir uma entrada 𝐼𝐵 em tempo polinomial para o
problema B
 𝐼𝐴 é uma instancia “sim” para A se, e somente se, 𝐼𝐵 é
uma instancia “sim” para B
 Primeiro problema NP-C
 Em 1971, Stephen Cook provou que todos os problemas
em NP podem ser reduzidos ao SAT (problema da
satisfabilidade) em tempo polinomial
CLASSE NP-COMPLETE
 Um problema de decisão 𝐷 ∈ 𝑁𝑃 é dito NP-C quando
qualquer outro problema em NP pode ser
transformado em D
 Consequência: se existir algum algoritmo polinomial
para a resolução de algum problema em NP-C, então
todos os problemas da classe NP também serão
resolvidos em tempo polinomial
 Então 𝑃 = 𝑁𝑃
CLASSE NP-HARD
 Problemas de otimização relacionados aos problemas
de decisão contidos em NP-C
 Classe de problemas da qual pertentem a maioria dos
problemas de grande importância pratica
REDUÇÃO DE PROBLEMAS
 Uma redução de um problema A para um problema B
são dois algoritmos de tempo polinomial f e h que,
respectivamente
 Transformam qualquer instancia 𝐼𝐴 em uma instancia 𝐼𝐵
 Transformam qualquer instancia 𝐼𝐵 em uma instancia 𝐼𝐴
 Se não existe solução para 𝐼𝐵, por consequência não
existe solução para 𝐼𝐴
REDUÇÃO DE PROBLEMAS
TEORIA DA COMPLEXIDADE
 Estuda a complexidade inerente aos problemas
computacionais e aos algoritmos que resolvem estes
problemas
 Complexidade de algoritmos
 Quais são os requisitos de tempo e de memoria de um
determinado algoritmo em função do tamanho da
entrada?
 Complexidade de problemas
 Qual é a complexidade do algoritmo de menor
complexidade que resolve o problema?
TEORIA DA COMPLEXIDADE
 Insertion Sort
TEORIA DA COMPLEXIDADE
TEORIA DA COMPLEXIDADE
 Complexidade polinomial
 A complexidade de um algoritmo ou de um problema é
dita polinomial se ela é limitada por um polinômio
 Exemplo: 𝑂 𝑛 , 𝑂 𝑛. 𝑙𝑜𝑔𝑛 , 𝑂 𝑛𝑘 k é 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡𝑒 , entre
outros
 Complexidade exponencial
 A complexidade de um algoritmo ou de um problema é
dita exponencial, se ela cresce de acordo com uma
função exponencial
 Exemplo: 𝑂 𝑛! , 𝑂 𝑛𝑛 , 𝑂 𝑘𝑛 𝑘 é 𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡𝑒 , entre
outros
TEORIA DA COMPLEXIDADE
 Como provar a complexidade de um problema?
 A complexidade de um algoritmo que resolve o
problema nos dá um limite superior para a
complexidade do problema
 Problema de ordenação→ 𝑂 𝑛2
 Dá para fazer melhor?
TEORIA DA COMPLEXIDADE
 Problema do fecho convexo
TEORIA DA COMPLEXIDADE
 Pode-se ordenar qualquer conjunto de números usando
o seguinte algoritmo
TEORIA DA COMPLEXIDADE
 Transforme o problema de ordenação em um problema
de fecho convexo
 𝑃 = 𝑎, 𝑎2 , 𝑏, 𝑏2 , 𝑐, 𝑐2 , … , 𝑧, 𝑧2
 𝑂 𝑛
TEORIA DA COMPLEXIDADE
 Resolva o problema de fecho convexo utilizando o
algoritmo de Graham
 𝑂 𝑛. 𝑙𝑜𝑔𝑛
TEORIA DA COMPLEXIDADE
 Percorra todos os pontos do fecho até encontrar o que
contenha o menor valor no eixo das abscissas
 𝑂 𝑛
TEORIA DA COMPLEXIDADE
 A partir do ponto selecionado, percorra novamente
todos os pontos no polígono, retornando os valores
contidos na coordenada X
 𝑂 𝑛
TEORIA DA COMPLEXIDADE
 Com isso, a complexidade total do algoritmo é
 𝑂 𝑛 + 𝑂 𝑛. 𝑙𝑜𝑔𝑛 + 𝑂 𝑛 + 𝑂 𝑛 = 𝑂 𝑛. 𝑙𝑜𝑔𝑛
TEORIA DA COMPLEXIDADE
 Estes estudos são realizados, em suma, para resolver
problemas que pertencem a classe NP-H
 Mas pra que isso se posso usar métodos exatos para
resolver esses problemas?
TEORIA DA COMPLEXIDADE
 Na prática, os problemas NP-H podem ser
solucionados utilizando das seguintes técnicas
 Algoritmos exatos pseudo-polinomiais
 Programação dinâmica
 Métodos exatos de enumeração implícita
 Backtraking, branch-and-bound
 Algoritmos evolucionários
 Programação genética
 Heurísticas e Metaheurísticas
KNAPSACK PROBLEM
KNAPSACK PROBLEM
ALGORITMOS EXATOS
PROGRAMAÇÃO DINÂMICA
BRANCH-AND-BOUND
HEURÍSTICA
 Algoritmo guloso
 Ordena os itens pelo valor de custo benefício