Técnicas De Programação III

[ANÁLISE DO PROBLEMA DA MOCHILA]

Uma análise completa sobre o problema da mochila, desde sua criação até as sua aplicações práticas e suas soluções.

 

SUMÁRIO

1 Introdução 1

2 Problema da mochila 1

3 Definição 2

3.1 Problema da Mochila com Repetições (Ilimitado) 2

3.2 Problema da Mochila sem Repetições (Limitado) 2

4 Motivação 3

5 Aplicações Práticas 3

6 Resoluções 3

6.1 Solução usando Programação Dinâmica 4

6.1.1 Ilimitado 4

6.1.2 Limitado 5

6.2 Solução usando Backtracking 6

6.3 Solução usando o Método Guloso 6

6.4 Solução usando Algoritmo de Aproximação de Greedy 7

7 Conclusão 8

8 Bibliografia 8

1 INTRODUÇÃO

Uma pergunta muito frequente nas salas de aula hoje em dia é: “Aonde vou aplicar isso na minha vida?”.

O objetivo deste trabalho é de explicar um algoritmo lógico e mostrar a suas aplicações, além demonstrar toda a sua genialidade.

2 PROBLEMA DA MOCHILA

O problema da mochila (em inglês, Knapsack problem) é um problema de optimização combinatória. O nome dá-se devido ao modelo de uma situação em que é necessário preencher uma mochila com objetos de diferentes pesos e valores. O objetivo é que se preencha a mochila com o maior valor possível, não ultrapassando o peso máximo.

O problema da mochila é um dos 21 problemas NP-completos de Richard Karp, exposto em 1972. A formulação do problema é extremamente simples, porém sua solução é mais complexa. Este problema é à base do primeiro algoritmo de chave pública (chaves assimétricas).

Normalmente este problema é resolvido com programação dinâmica, obtendo então a resolução exata do problema, mas também sendo possível usar PSE (procedimento de separação e evolução). Existem também outras técnicas, como usar algoritmo guloso, meta-heurística (algoritmos genéticos) para soluções aproximadas.

3 DEFINIÇÃO

Suponha que tenha uma mochila com capacidade total de e itens distintos. Seja a quantidade de itens que está sendo carregado, cada um com um respectivo peso e valor . Maximizar o valor da mochila nada mais é que maximizar a seguinte equação:

3.1 Problema da Mochila com Repetições (Ilimitado)

Neste caso não existe nenhuma restrição quanta quantidade máxima que se pode carregar do respectivo item. Logo, o problema pode ser visto como a maximização da seguinte equação:

3.2 Problema da Mochila sem Repetições (Limitado)

Nesta situação podemos ver dois problemas envolvidos, sendo eles o problema da mochila limitado 0/1 e o problema da mochila limitado. O segundo caso pode ser visto como uma generalização do primeiro.

Este caso e aplicado na situação onde só e possível pegar uma única unidade de cada item. Portanto temos a restrição de que . A equação a ser maximizada pode ser escrita como:

|Já no segundo caso e aplicado na situação onde só e possível pegar uma única unidade de cada item. Portanto temos a restrição de que . A equação a ser maximizada pode ser escrita como:

4 MOTIVAÇÃO

Imagine que você possui um contentor de certo tamanho e vários produtos com seus valores para serem colocados dentro dele. Porém os produtos devem ser colocados de um jeito que o contentor tenha o maior valor.

Suponha que você tenha em sua máquina uma pasta cheia de arquivos e deseja gravá-los em CD, só que você já sabe de antemão que não vai caber tudo num CD só. Podem ser dois, três... dez CD's. Como proceder para encaixar o máximo de arquivos em cada CD desperdiçando o mínimo espaço em cada disco?

Desses exemplos podemos entender que a motivação do problema da mochila é colocar dentro de um compartimento uma quantidade de objetos com determinadas importâncias para que esse compartimento tenha a maior importância possível.

5 APLICAÇÕES PRÁTICAS

O modelo em si pode ser aplicado, além nos exemplos citados acima, em casos como: Investimento de capital corte e empacotamento, carregamento de veículos, orçamento.

Foi também utilizado para a construção do algoritmo de Criptografia de chave pública, onde no contexto do problema da mochila a chave pública seria o peso total que a mochila pode carregar e a partir daí, por essa palavra a encriptação é gerada.

6 RESOLUÇÕES

Por ser um problema combinatório é possível resolve-lo por enumeração exaustiva, ou seja, tentar todas as soluções possíveis e comparando-as para identificar a melhor solução. Porém isso se torna completamente inviável uma vez que, mesmo em pequenas dimensões como um problema com apenas 20 itens, haveria um número enorme de respostas. Em um problema com mais de 80 itens, o algoritmo levaria bilhões de anos para ser concluído. Assim, o método de resolução por enumeração exaustiva é de utilidade muito reduzida, senão mesmo nula, para problemas de grande dimensão.

Descreveremos aqui três soluções para este algoritmo:

6.1 Solução usando Programação Dinâmica

Programação Dinâmica, ou Função Recursiva, foi a primeira técnica mais inteligente que foi usada para resolver esse problema, na década de 50. É um método aprimorado de usar recursividade que ao invés de chamar uma função várias vezes ele, na primeira vez que é chamada, armazena o resultado para que cada vez que a função for chamada novamente volte o resultado e não uma requisição