ALGORITMO DE PROGRAMAÇÃO DINÂMICA

Técnicas de Divisão e Conquista e de Programação Dinâmica para a resolução de Problemas de Otimização
Francisco Vando Carneiro Moreira
Gerardo Valdisio Rodrigues Viana
Faculdade Lourenço Filho
Universidade Estadual do Ceará
Resumo
Encontrar o valor máximo ou mínimo de uma função é um problema bastante utilizado em diversas áreas.
Em geral, este valor é chamado de "ótimo" pois corresponde ao melhor dentre todos os possíveis num espaço de soluções viáveis. Neste contexto define-se a otimização, que pode ser restrita, quando a solução atender determinadas condições impostas pelo problema, ou irrestrita, quando qualquer solução dentro do domínio da função é investigada. Classificam-se como problemas mais difíceis aqueles em que o espaço de soluções não é contínuo, caracterizando a chamada Otimização Discreta, ou Combinatória, definida assim: “dado um conjunto A de elementos, deseja-se encontrar um subconjunto S ⊆ A tal que a função objetivo, aplicada aos elementos de S, possui o valor "ótimo" que pode ser de máximo (maior de todos) ou de mínimo (menor de todos)”. Como o número de opções para a escolha de S cresce de forma exponencial com o tamanho do conjunto A, métodos exatos para obter a "solução ótima" precisam percorrer todo o espaço, o que se torna impraticável. Para isto existem os métodos aproximados que correspondem às heurísticas, meta-heurísticas e algoritmos aproximativos. Dentre estes, destacam-se as técnicas de Divisão e Conquista e de Programação Dinâmica. Neste trabalho, mostramos o funcionamento destes dois algoritmos aplicados a alguns problemas conhecidos de otimização combinatória. Palavras-chave: Divisão e Conquista, Programação Dinâmica, Algoritmos, Problema da Mochila.

1. INTRODUÇÃO
Dados, uma “mochila” com capacidade C e um conjunto A com n itens, onde cada item i ∈ A contém um peso Pi > 0 e uma utilidade, ou valor, Vi > 0, deseja-se determinar um subconjunto S ⊆ A tal que a soma dos pesos dos elementos de S não