Please enable JavaScript.
Coggle requires JavaScript to display documents.
IF672 (2020.1) - Levitin Aluno: Marcos André - Coggle Diagram
IF672 (2020.1) - Levitin Aluno: Marcos André
(8) Programação Dinâmica (283–296)
Técnica de resolver problemas com subproblemas sobrepostos
Resolver subproblemas menores uma vez
Gravar os resultados em uma tabela
Aplicações
Números de Fibonacci
Guardar apenas os dois últimos valores
Space-for-time trade-off
Pode ser refinado e evitar usar espaço extra
Abordagens
Bottom-up
Resolve todos os subproblemas menores
Top-Down
Evita resolver problemas desnecessários
Passo crucial
Derivar uma recorrência de uma solução para solucionar subproblemas menores
Princípio da otimidade
Soluções ótimas para os subproblemas
(8.1) Três Exemplos Básicos
Coin-row
Fileira com moedas
Máximo de moedas não-adjacentes
Divide em dois grupos
Incluem a última moeda
Não incluem
Eficiência
θ(n)
Change-making
Dar troco com o menor número de moedas
Resolução parecida com Coin-Row
Eficiência
Tempo
O(nm)
m = quantidade de denominadores
n = quantidade de moedas
Espaço
θ(n)
Coin-collecting
Tabuleiro n x m
Uma moeda por célula
Robô que coleciona moedas
Caminho em que ele coletará o máximo de moedas
Eficiência
θ(nm)
(8.2) Knapsack Problem e Funções de memória
Resolver o problema do knapsack com programação dinâmica
Dividir os subsets
não incluem o i-ésimo item
F(i-1, j)
incluem
vi + F(i-1, j - wi)
Eficiência
Caso geral
θ(nW)
Solução ótima
O(n)
Funções de memória
Top-Down direto
Resolve subproblemas comuns mais de uma vez
Muito ineficiente
Bottom-up Clássica
Enche uma tabela com soluções
Subproblemas menores só resolvidos uma vez
Alguns subproblemas não são necessários
Resolve uma vez só subproblemas necessários
Fusão dos dois tipos
Tabela inicializada com NULL
Pode ser menos espacialmente eficiente que um bottom-up espacialmente eficiente
(12) Coping with the Limitations of Algorithm Power (441–457)
(12.3) Algoritmos de Aproximação para problemas NP-Hard
Problemas pelo menos tão difíceis quanto os NP-Completo
Não há algoritmos em tempo polinomial
Provavelmente nem existem algoritmos
Resolver instância muito pequena do problema
Busca exaustiva
Programação Dinâmica
Instâncias um pouco maiores
Branch-and-bound
Boa performance não é sempre garantida
Outra opção
Resolver os problemas de forma aproximada rapidamente
Algoritmos de Aproximação
Baseados na heurística específica do problema
Heurística
Regra de senso comum advinda da experiência
Accuracy ratio
Quão aproximado é aquele algoritmo
Algoritmo de aproximação-c
Performance ratio
Qualidade de aproximação
Solução não precisa ser perfeita, mas aceitável
Algoritmos de Aproximação para o TSP
Algoritmos Gulosos
Algoritmo do Vizinho mais próximo
Algoritmo da heurística Multifragmentada
Instâncias Euclidianas
Desigualdade triangular
Simetria
Algoritmos baseados em MST
Algoritmo duas vezes ao redor da árvore
Eliminar os repetidos (Exceto o primeiro)
Algoritmo de Christofides
Mais sofisticado
Circuito Euleriano no multigrafo
Repete os passos do duas vezes ao redor da árvore
Heurísticas de busca local
2-opt
k-change
3-opt
Lin-Kernighan
Aplicação dos dois outros tipos
Resultados Empíricos
Progresso, mas aproximação ainda é útil
Held-Karp bound
Algoritmos de Aproximação para o Knapsack Problem
Algoritmos Gulosos
Discreto
value-to-weight ratios
Algoritmo guloso melhorado
Contínuo
Frações arbitrárias dos itens
Limite superior da versão discreta
Esquemas de aproximação
Versão discreta
Tempo polinomial
Aproximações com qualquer nível de precisão predefinido
Eficiência
O(kn^(k+1))
Fully polynomial schemes
Mais eficientes