Problema da mochila

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde Agosto de 2013).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.
Problema da mochila: Como maximizar o valor com um peso máximo?

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 é a 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.

História[editar | editar código-fonte]

Também conhecido como "knapsack problem", o Problema da Mochila está relacionado com um grande número de outros modelos de programação. Sua importância está associada exatamente a esse fato.

Foi possivelmente reportado pela primeira vez na literatura por Dantzig (1957) e constitui um marco das técnicas de programação inteira, otimização combinatória e programação dinâmica.

Metaforicamente podemos entendê-lo como o desafio de encher uma mochila sem ultrapassar um determinado limite de peso, otimizando o valor do produto carregado.

O problema da mochila possui alguns variantes que são:

  • O Problema simples da mochila: Onde o ladrão possui uma mochila e vários objetos cada tipo com o seu valor.
  • O Problema múltiplo da mochila: Onde o ladrão possui mais de uma mochila ou uma mochila com vários bolsos e vários objetos de cada tipo com o seu valor.

O problema simples da mochila foi resolvido por Ronald Rivest, Adi Shamir e Len Adleman em 1982 e o problema dinâmico da mochila foi resolvido por Ernmie Brickell em 1984.

Definição[editar | editar código-fonte]

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


\sum_{i=1}^{n}v_{i}x_{i}  \mbox{ , sujeito a } \sum_{i=1}^{n}w_{i}x_{i} \leq \emph{W}.

Problema da Mochila com Repetições (Ilimitado)[editar | editar código-fonte]

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


\textstyle\sum_{i=1}^{n}v_{i}x_{i}  \mbox{ , sujeito a } \sum_{i=1}^{n}w_{i}x_{i} \leq \emph{W} \mbox{ onde } x_{i} \in \mathbb{N}.

Problema da Mochila sem Repetições (Limitado)[editar | editar código-fonte]

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.

0/1[editar | editar código-fonte]

Este caso e aplicado na situação onde só e possível pegar uma unica unidade de cada item. Portanto temos a restrição de que x_{i} \in \{0,1\}. A equação a ser maximizada pode ser escrita como:


\sum_{i=1}^{n}v_{i}x_{i}  \mbox{ , sujeito a } \sum_{i=1}^{n}w_{i}x_{i} \leq \emph{W} \mbox{ onde } x_{i} \in \{0,1\}.

Limitado[editar | editar código-fonte]

Este caso e aplicado na situação onde só e possível pegar uma unica unidade de cada item. Portanto temos a restrição de que x_{i} \in \{1,2, ..., c_{i}\}. A equação a ser maximizada pode ser escrita como:


\sum_{i=1}^{n}v_{i}x_{i}  \mbox{ , sujeito a } \sum_{i=1}^{n}w_{i}x_{i} \leq \emph{W} \mbox{ onde } x_{i} \in \ \{0, 1,..., c_{i} \}.

Motivação[editar | editar código-fonte]

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.

Aplicações Práticas[editar | editar código-fonte]

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.

Resoluções[editar | editar código-fonte]

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 concluido. 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:

Solução usando Programação Dinâmica[editar | editar código-fonte]

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 é chamado, armazena o resultado para que cada vez que a função for chamada novamente volte o resultado e não uma requisição para ser resolvida.

No Método Guloso, uma solução ótima é definida por uma sequencia de decisões ótimas locais. Quando esse método não funciona, uma possível saída seria gerar todas as possíveis sequencias de decisões e escolher a melhor sequencia, como no Backtracking. Porém essa solução é ineficiente, por ser de ordem exponencial. Na programação dinâmica é possível avaliar todas as soluções, garantido assim que a resposta final estará correta, e armazenar resultados anteriores impedindo dessa forma contas repetidas, o que deixa esse algoritmo mais eficiente.

Ilimitado[editar | editar código-fonte]

Para a versão que permite repetições, é preciso pensar nos subproblemas que existem. Pode-se pensar que e possível olhar para mochilas com capacidade menores de forma que w \leq W . Com esta restrição, pode-se escrever:

K(w) = maior valor alcançado com uma mochila de capacidade w.

É possível ver isto em forma de subproblemas menores? Se a solução para K(w) inclui o item i, então removendo este item da mochila teremos uma solução ótima para K(w-w_{i}). Em outras palavras, K(w) é simplesmente K(w-w_{i}) + v_{i}, para algum i. Como não sabemos quem é o i, temos de tentar todas as possibilidades.


K(w) =\max_{i: w_{i}\leq w} \{ K(w-w_{i}) + v_{i}\},

Para resolver, podemos apresentar o seguinte pseudo-código:

   K(0) = 0
   \mbox{para } w=1 \mbox{ até } W\mbox{ : }
       K(w) = \max\{K(w-w_{i})+v_{i}: w_{i} \leq w\}
   retornar K(W)

Este algoritmo preenche uma tabela uni-dimensional de tamanho W+1, da esquerda para a direita. Como cada chamada leva um tempo fixo de O(n), e temos que fazer W chamadas, o tempo total de execução sera de O(nW).

Limitado 0/1[editar | editar código-fonte]

Para o caso limitado, saber ver subproblemas como no caso ilimitado é completamente inútil. Por exemplo, saber que o valor de K(w-w_{n}) e alto nao ajuda em nada, pelo fato de que não sabemos se o item n já foi ou não utilizado. Precisamos antes refinar o conceito de subproblemas para carregar informação acerca dos itens que já foram utilizados. Para isto, basta adicionar um segundo parêmetro, 0 \leq j \leq n :

K(w,j) = maior valor alcançado com uma mochila de capacidade w e itens 1,..., j.

A resposta que procuramos é K(W,n). Como e possível expressar um subproblema K(w,j) em termos de subproblemas menores? Simples. Ou o item j e necessário para alcançar o valor ótimo, ou não é:


K(w,j) = \max \{ K(w-w_{j}, j-1) + v_{j}, K(w, j-1)  \} .

O algoritmo consiste em preencher uma tabela bi-dimensional, com W+1 linhas e n+1 colunas. Apesar da tabela agora ser muito maior que no caso ilimitado, o tempo de execução será o mesmo, pois cada chamada leva um tempo fixo de O(n) e W chamadas são feitas, então o tempo total será de O(nW).

   Inicializar K(0,j) = 0 \forall j = \{1,.., n\} e K(w,0) = 0 \forall w = \{1,.., W\}
   para j = 1 até n:
       para w = 1 até W:
           se w_{j} > w: K(w,j) = K(w,j-1)
           senão: K(w,j) = \max\{ K(w,j-1), K(w-w_{j},j-1) + v_{j}\}
   retornar K(W,n)

Solução usando Backtracking[editar | editar código-fonte]

Backtracking é um algoritmo refinado da busca por força bruta (ou enumeração exaustiva), no qual boa parte das soluções podem ser eliminadas sem serem explicitamente examinadas. É uma estratégia que se aplica em problemas cuja solução pode ser definida a partir de uma seqüência de n decisões, que podem ser modeladas por uma árvore que representa todas as possíveis seqüências de decisão. De fato, se existir mais de uma disponível para cada uma das n decisões, a busca exaustiva da árvore é exponencial. A eficiência desta estratégia depende da possibilidade de limitar a busca, ou seja, podar a árvore, eliminando os ramos que não levam a solução desejada.

Para tanto é necessário definir um espaço de solução para o problema. Este espaço de solução deve incluir pelo menos uma solução ótima para o problema. Depois é preciso organizar o espaço de solução de forma que seja facilmente pesquisado. A organização típica é uma árvore. Só então se pode realizar a busca em profundidade.

Para o problema da mochila o algoritimo de forca bruta compara todas as possibilidades de preenchimento da mochila que não ultrapassem o peso máximo estipulado. Durante este teste, o algoritimo guarda em uma variável a maior utilidade conseguida e ao final de todas as comparações, o resultado do algoritimo está armazenado nesta variável.

Solução usando o Método Guloso[editar | editar código-fonte]

O Método Guloso é um dos algoritmos mais simples que pode ser aplicado a uma grande variedade de problemas, que na maioria possuem n entradas e é necessário obter um subconjunto que satisfaça alguma restrição, como no Problema da Mochila. Qualquer subconjunto que satisfaça esta restrição é chamado de solução viável. Então o que queremos é uma solução viável que maximize ou minimize uma dada função objetivo. Essa função viável que satisfaz a função objetivo é chamada de Solução Ótima.

No Método Guloso construimos um algoritmo que trabalha em estágios, considerando uma entrada por vez. Em cada estágio é tomada uma decisão considerando se uma entrada particular é uma solução ótima. Isto é feito considerando as entradas em uma ordem determinada por um processo de seleção, que é baseado em alguma medida de otimização que pode ou não ser a função objetivo. Na maioria das vezes, porém, essas medidas de otimização resultarão em algoritmos que gerarão soluções sub-ótimas.

Solução usando Algoritmo de Aproximação de Greedy[editar | editar código-fonte]

Foi proposto por George Dantzig, em 1957, um algoritmo de aproximação de greedy para resolver o problema da mochila. A versão dele dispõe os itens em ordem decrescente de valor por unidade de peso. Em seguida, começa a inseri-los na mochila com tantas cópias quanto possível do primeiro tipo de item, até que não haja mais espaço na mochila. Caso o problema seja delimitado, ou seja, a oferta para cada tipo de item tenha um limite, o algoritmo pode ficar muito custoso.

Um algoritimo que utiliza o método de aproximação tem por objetivo encontrar uma solução aproximada para o problema com tempo na ordem de n e n^2. Além disso, temos uma taxa de aproximação representada por:

MAX(C* /C,C/C*)

Onde C* é o custo obtido. Esta taxa de aproximação deve ser menor ou igual a 2.

Para resolução do problema da mochila, utiliza-se o método de aproximação baseado em algoritmo gulosos. Este algoritimo ordena a entrada com relação à taxa obtida da divisão do valor pelo peso, essa ordenação é feita do maior para o menor. O método de ordenação utilizado é o Quicksort o qual possui um tempo de ordenação de nlog(n).

Depois de realizada a ordenação, a solução do problema é obtida simplesmente pegando os primeiros elementos da ordenação até que a capacidade da mochila seja atingida, se existir um elemento que ao ser colocado na mochila ultrapasse a sua capacidade, este elemento é desprezado e passa-se para o próximo.

Ligações externas[editar | editar código-fonte]

Ver também[editar | editar código-fonte]