Please enable JavaScript.
Coggle requires JavaScript to display documents.
M16 (Levitin) - Coggle Diagram
M16 (Levitin)
Cap. 8
Uma importante técnica para resolução de problemas não polinomiais é
Programação Dinâmica
Consiste em acelerar a resolução de um subproblema a partir de resoluções previamente salvas de outros subproblemas
É aplicada em problemas que respeitam o
princípio da otimalidade
, isto é, que a melhor solução para um problema é composta pelas melhores soluções de seus subproblemas
Existem 3 abordagens principais:
Bottom-up
: abordagem clássica em que os subproblemas são solucionados em ordem crescente de complexidade. Desvantagem: todos os subproblemas anteriores a um problema são resolvidos, mesmo que suas soluções sejam desnecessárias para o problema em questão
Top-Down
: a medida que a solução de um subproblema é requisitada, este entra em uma "pilha" recursiva até que seja solicitada a solução de um problema trivial, a partir do qual é sucessivamente encontradas as soluções dos subproblemas colocados na "pilha". Desvantagem: um mesmo subproblema pode ser resolvido mais de uma vez
Uso de
funções de memória
: Combina as outras duas abordagens em um mesmo algoritmo, avaliando os subproblemas de maneira
top-down
enquanto faz uso da tabela do método
bottom-up
para armazenar os subproblemas já resolvidos. Desvantagens: não gera uma melhoria significativa o suficiente para mudar a classe de eficiência que permanece a mesma do
bottom-up
, podendo ainda ser menos espacialmente eficiente que um
bottom-up
aperfeiçoado
Cap. 12
.3
Outra técnica bastante bastante recorrente para lidar com problemas de classe
NP-difícil
é o uso de
Algoritmos de Aproximação
São algoritmos que encontram soluções boas para um dado problema, embora não sejam necessariamente as melhores
Em sua maioria, fazem uso de abordagens
heurísticas
, isto é, de decisões tomadas com base na experiência/intuição humana ao lidar com determinados problemas. Ou seja, realizam-se escolhas determinadas pela expectativa de sucesso esperada pelo senso-comum
Uma informação útil para avaliar o grau de satisfatoriedade de um algoritmo de aproximação é a
razão de precisão
entre a solução encontrada e a melhor solução possível (razão não necessariamente nessa ordem)
Em um
algoritmo de aproximação - c
, existe uma constante
c
maior ou igual a 1 que limita superiormente a razão de precisão do algoritmo
Em situações em que não se sabe o valor da melhor solução, a razão de precisão pode ser calculada a partir de um limite inferior chamado
limite Held-Karp
que desconsidera determinadas restrições a fim de encontrar um resultado ótimo que extrapola um pouco o verdadeiro melhor resultado
Para alguns problemas pode haver
esquemas de aproximação
em tempo polinomial que encontram limites superiores da forma 1+1/k, sendo k um inteiro qualquer de 0 a
n
(tamanho da entrada). Quanto maior o k escolhido melhor a aproximação, porém maior é o tempo gasto na execução do algoritmo. Nesse caso, a eficiência temporal em função de
n
é polinomial
Em
esquemas totalmente polinomiais
, a eficiência temporal do algoritmos em função de
k
também é polinomial