Programação dinâmica

Definição

Knapsack

Algoritmos de aproximação para problemas NP-hard

Exemplos

A programação dinâmica é usada para resolver problemas com subproblemas sobrepostos, onde a solução de um problema maior depende das soluções de problemas menores relacionados. Em vez de resolver os subproblemas repetidamente, a programação dinâmica sugere resolvê-los uma vez e registrar os resultados em uma tabela para evitar recálculos. Isso pode ser ilustrado pelo exemplo dos números de Fibonacci, onde em vez de usar a recorrência diretamente, podemos preencher um array com os valores progressivos dos números de Fibonacci.

Problema de Troco (Change-making problem): O objetivo é dar o troco para um valor n usando o menor número possível de moedas de diferentes denominações. Isso é resolvido de forma eficiente usando a fórmula recursiva: F(n) = min{F(n - dj)} + 1, com F(0) = 0.

Problema de Coleta de Moedas (Coin-collecting problem): Neste problema, um robô precisa coletar moedas em uma grade e levá-las para o canto oposto da grade. O número máximo de moedas coletadas é calculado recursivamente: F(i, j) = max{F(i - 1, j), F(i, j - 1)} + 1.

Problema das Moedas em Linha (Coin-row problem): Dada uma fila de moedas, o objetivo é escolher moedas de modo a maximizar a soma, com a restrição de não pegar moedas adjacentes. Isso é resolvido usando uma fórmula recursiva: F(n) = max{cn + F(n - 2), F(n - 1)}, onde F(n) é a maior soma possível e as condições iniciais são F(0) = 0 e F(1) = c1.

O problema knapsack envolve escolher um subconjunto valioso de itens, cada um com peso e valor conhecidos, para colocar em um pacote com capacidade limitada. O objetivo é maximizar o valor dos itens no pacote.

Para resolver esse problema usando programação dinâmica, desenvolvemos uma relação de recorrência. Consideramos uma instância do problema com os primeiros i itens, pesos w1,...,wi, valores v1,...,vi e uma capacidade do pacote j. Definimos F(i, j) como o valor da melhor solução para essa instância.
Observamos que podemos dividir os subconjuntos de itens em dois grupos: aqueles que não incluem o item i e aqueles que o incluem. O valor da melhor solução entre todos os subconjuntos é o máximo desses dois casos.

Memory Functions (Funções de memória)

A função de memória, é uma abordagem na programação dinâmica que visa combinar os benefícios das abordagens top-down e bottom-up para resolver problemas que têm subproblemas sobrepostos em sua solução, minimizando assim, o retrabalho ao armazenar e reutilizar soluções para subproblemas já resolvidos

Uma estratégia para lidar com problemas complexos, como Knapsack, é encontrar soluções aproximadas por meio de algoritmos rápidos. Isso é especialmente útil quando uma solução próxima, mas não necessariamente a melhor, é aceitável.

Problema do caixeiro-viajante(TSP): esse é um problema de otimização combinatória, que é resolvido por meio de algoritmos de aproximação. O TSP é um problema NP-completo, o que significa que encontrar a solução exata é extremamente difícil e consome muito tempo. Portanto, a abordagem é encontrar soluções aproximadas que sejam aceitáveis em termos de qualidade.

Exemplos de algoritmos de aproximação

Ao analisar o desempenho desses algoritmos em instâncias do TSP, em muitos casos, as soluções aproximadas são de alta qualidade e podem ser obtidas em tempo razoável, mesmo para instâncias grandes. No entanto, para instâncias assimétricas do TSP, encontrar soluções ótimas permanece desafiador.

Algoritmos mais avançados, como o algoritmo de Christofides, que é uma aproximação 1,5 para instâncias euclidianas do TSP. Ele usa árvores geradoras mínimas e emparelhamentos para construir uma solução aproximada.

Algoritmos de busca local, como o algoritmo 2-opt, que exploram vizinhanças em torno de soluções atuais para melhorá-las iterativamente. Esses algoritmos podem ser especialmente eficazes em instâncias euclidianas.

Há algoritmos de aproximação simples, como o algoritmo do "vizinho mais próximo", que funciona escolhendo sempre a cidade não visitada mais próxima em cada etapa.