Dynamic Programming
Explicação
É um método geral para otimizar processos de decisão multiestágios, é útil para resolver problemas que possuem subproblemas sobrepostos, nos quais uma solução para o problema geral depende das soluções dos subproblemas menores.
Ao invés de resolver repetidamente os subproblemas sobrepostos, a programação dinâmica sugere resolver cada subproblema uma única vez e gravar os resultados em uma tabela, de onde uma solução para o problema original pode ser obtida.
Exemplos
Coin-row problem
Objetivo
Neste problema, há uma fila de n moedas com valores positivos c1, c2,...,cn, não necessariamente distintos. O objetivo é pegar a quantidade máxima de dinheiro sujeita à restrição de que nenhuma duas moedas adjacentes na fila inicial podem ser escolhidas.
Solução
Dá para dividir o problema de achar o F(n) de uma moeda em dois subproblemas onde, um é F(n - 1) onde a última moeda não está inclusa mas sim o seu anterior, e o d Cn + F(n - 2) onde adicionamos o valor da moeda n ao F da antepenúltima moeda. A solução será o subproblema que tiver o maior valor comparado ao outro
Change-making problem
Objetivo
Solução
Neste problema, o objetivo é dar troco para uma quantia n utilizando o menor número possível de moedas de denominações d1 < d2 < ... < dm
Coin-collecting problem
Seja F(n) o número mínimo de moedas cujos valores somam n e definindo F(0) = 0, primeiro definimos um conjunto de moedas de denominações que varia de 1 até m, ao fazer isso podemos dizer que, j = {1, 2, 3, ..., m}, F(n) = 1 + min(F(n - D[j]))
Ao fazer isso é tirado do valor n uma moeda de denominação obtendo o valor k ao fazer F(k) obtemos o número necessário de moedas de denominação necessárias para chegar em k ao somar mais 1 adicionamos a última moeda necessária para chegar ao valor n, obter o mínimo desses valores apenas significa encontrar k onde o F(k) é menor que os outros
Objetivo
Neste problema, várias moedas estão distribuídas em células de um tabuleiro n × m, e um robô, localizado na célula superior esquerda do tabuleiro, precisa coletar o máximo possível de moedas e levá-las para a célula inferior direita. Não pode existir mais de uma moeda por célula e o robô só pode se mover ou para a direita ou para baixo
Solução
Considerando F(i, j) o número máximo de moedas que se pode levar para a célula na linha i e coluna j, podemos dividir o problema em dois sendo eles F(i - 1, j) e F(i, j - 1) que são o número máximo de moedas que se pode levar para às células adjacentes da esquerda e de cima respectivamente
Ao escolher o número máximo entre esses dois subproblemas descobrimos qual o número de moedas o robô pode carregar antes de chegar na célula atual, se a célula atual tiver uma moeda somamos mais 1 caso contrário o resultado é o número escolhido
The Knapsack Problem and Memory Functions
Knapsack Problem
Objetivo
O problema envolve selecionar um subconjunto de itens, de um conjunto onde cada item possui um valor e um peso não negativo, de modo a maximizar o valor total, respeitando a capacidade de uma mochila.
Solução
considerando que F(i, j) é o valor máximo para os primeiros i itens e sendo j a capacidade restante da mochila, é possível dividir o problema em dois, um em que não é adicionado o item ou seja F(i - 1, j) e o que ele é adicionado Vi + F(i - 1, j - Wi)
Caso j - Wi < 0 então a solução é F(i - 1, j), caso contrário, a solução será max(F(i - 1, j), Vi + F(i - 1, j - Wi)), ou seja, a solução consiste em decidir se é melhor adicionar o i-ésimo item ou não
Memory Functions
O problema da programação dinâmica é que, como ela consiste em resolver primeiro os subproblemas uma única vez para depois resolver o problema original, por muitas vezes ela resolve subproblemas que não são necessários para resolver o problema original
Para isso servem as Memory Functions que é uma técnica para manter a capacidade de resolver subproblemas uma única vez, mas, resolvendo apenas aqueles que são necessários para chegar a resolução do problema original
Approximation Algorithms for NP -Hard Problems
Explicação
Apesar dos métodos já citados anteriormente que podem resolver problemas NP-Hard em um tempo aceitável, isso só funciona para instâncias específicas do problema que são relativamente pequenas, para instâncias maiores do problema para que haja uma solução em tempo polinomial é usado como recurso algoritmos de aproximação
Esses algoritmos de aproximação vão usar um conjunto de heurísticas, uma regra extraída a partir da experiência e não provada matematicamente, que partirão para uma solução aproximada do problema
A solução virá com uma margem de erro que é chamada de ratio onde r(Sa) = f(S*)/f(Sa) onde S* é a solução real, que por muitas vezes não sabemos qual é
Define-se um algoritmo de aproximação c, onde c >= 1, se r(Sa) <= c
Quanto mais próximo de r(Sa) = f(Sa)/f(S*) estiver de 1, mais próxima está a solução computada da solução real