Kapsnack Problem

  • View
    189

  • Download
    2

Embed Size (px)

Text of Kapsnack Problem

Universidade Federal de Minas Gerais Instituto de Cincias Exatas Departamento de Cincia da Computao

PROJETO E ANLISE DE ALGORITMOS Trabalho: disponvel em: http://www.dcc.ufmg.br/ ruiter/paatp2

Ruiter Braga Caldas Professor - Nivio Ziviani

Belo Horizonte 10 de maio de 2004

Sumrio1 O Problema da Mochila1.1 1.2 1.3 Provar que o Problema da Mochila NP-Completo . . . . . . . . . . Mostrar que o Problema est em NP . . . . . . . . . . . . . . . . . . Reduo Polinomial . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

2 2 2

2 Soluo usando Backtracking 3 Soluo usando Programao Dinmica 4 Soluo usando o Mtodo Guloso 5 Comparao entre os Mtodos5.1

4 6 10 11

Resposta para os Conjuntos de Dados . . . . . . . . . . . . . . . . . . 13

6 Estruturas de Dados A Cdigo Fonte B Tabelas com tempos de execuoB.1 Mtodo Guloso . . . B.1.1 Conjunto I . . B.1.2 Conjunto II . B.1.3 Conjunto III . B.1.4 Conjunto IV . B.2 Mtodo Dinmico . . B.2.1 Conjunto I . . B.2.2 Conjunto II . B.2.3 Conjunto III . B.2.4 Conjunto IV . B.3 Mtodo Backtracking B.3.1 Conjunto I . . B.3.2 Conjunto II . B.3.3 Conjunto III . B.3.4 Conjunto IV . C.1 C.2 C.3 C.4 Conjunto Conjunto Conjunto Conjunto I I I I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15 19 2727 27 28 29 30 31 31 33 34 35 36 36 37 38 39

C Tabelas com Utilidade Acumulada

3939 41 42 43

2

1 O Problema da MochilaO problema da Mochila (knapsack problem ) pode ser enunciado da seguinte forma: Dados um nmero m 0, um inteiro positivo n e, para cada i em {1, . . . , n}, um nmero vi 0 e um nmero wi 0, encontrar um subconjunto S de {1, . . . , n} que maximize v(S) sob a restrio w(S) m. Onde, v(S) denota a soma iS vi e, analogamente, w(S) denota a soma iS wi . Os nmeros vi e wi podem ser interpretados como utilidade e peso respectivamente de um objeto i. O nmero m pode ser interpretado como a capacidade de uma mochila, ou seja, o peso mximo que a mochila comporta. O objetivo do problema ento encontrar uma coleo de objetos, a mais valiosa possvel, que respeite a capacidade da mochila. Este problema vem sendo estudado deste o trabalho de D.G. Dantzig[5], devido a sua utilizao imediata na Indstria e na Gerencia Financeira, porm foi mais enunciado por razes tericas, uma vez que este freqentemente ocorre pela relaxao de vrios problemas de programao inteira. Toda a famlia de Problemas da Mochila requer que um subconjunto de tens sejam escolhidos, de tal forma que o somatrio das suas utilidades seja maximizado sem exceder a capacidade da mochila. Diferentes tipos de problemas da Mochila ocorrem dependendo da distribuio de tens e Mochilas como citado em [5]: No problema da Mochila 0/1 (0/1 Knapsack Problem ), cada tem pode ser escolhido no mximo uma vez, enquanto que no problema da Mochila Limitado (Bounded Knapsack Problem ) temos uma quantidade limitada para cada tipo de tem. O problema da Mochila com Mltipla Escolha (Multiple-choice Knapsack Problem ) ocorre quando os tens devem ser escolhidos de classes disjuntas, e se vrias Mochilas so preenchidas simultaneamente temos o problema da Mochila Mltiplo (Multiple Knapsack Problem ). A forma mais geral o problema da Mochila com multirestries (Multi-constrained Knapsack Problem ) o qual basicamente um problema de Programao Inteira Geral com Coecientes Positivos. Todos os problemas da Mochila pertencem a famlia NP-Hard [5], signicando que muito improvvel que possamos desenvolver algoritmos polinomiais para este problema. Porm, a despeito do tempo para o pior caso de todos os algoritmos terem tempo exponencial, diversos exemplos de grandes instncias podem ser resolvidos de maneira tima em frao de segundos. Estes resultados surpreendentes vem de vrias dcadas de pesquisa que tem exposto as propriedades estruturais especiais do Problema da Mochila, que tornam o problema to relativamente fcil de resolver. Neste trabalho todos os algoritmos apresentados resolvem o Problema da Mochila 0/1, que consiste em escolher n tens, tais que o somatrio das utilidades maximizado sem que o somatrio dos pesos extrapolem a capacidade da Mochila. Isto pode ser formulado como o seguinte problema de maximizar :n

M aximizarj=1 n

uj x j

Sujeitoj=1

pj xj M

xj {0, 1}, j = 1 . . . n1

onde xj uma varivel binria igual a 1 se j deve ser includo na mochila e 0 caso contrrio.

1.1 Provar que o Problema da Mochila NP-CompletoPara provar que um problema acordo com [6], que: pertence a N P -Completo necessrio provar, de

o mesmo pertence a classe N P , apresentando em algoritmo no-determinista em tempo polinomial ou mostrando que uma dada soluo pode ser vericada em tempo polinomial. Apresentar um reduo em tempo polinomial de um problema N P -completo para o mesmo.

1.2 Mostrar que o Problema est em NPPara provar que o Problema da Mochila 0/1 pertence a classe N P vamos apresentar um algoritmo no-determinista que resolva o problema em tempo polinomial.KnapsackND(cM, uM, n, P [1..n], U [1..n], X[1..n])

1 2 3 4 5 6

for i 1ton do

if ( n P [i] X[i] > cM )OR( 1 then return Insucesso else return Sucesso

X[i] escolhe(0, 1);

n 1

U [i] X[i] < uM )

O procedimento KnapsackN D uma algoritmo No-Determinista para o problema de deciso da Mochila. As linhas de 1-3 atribui o valor 0/1 para o vetor soluo X[i], 0 i n. Na linha 4 feito um teste para vericar se a atribuio do pesos vivel e no ultrapassa a capacidade da Mochila cM e se o resultado da Utilidade pelo menos uM . Uma soluo com sucesso encontrada se as restries so satisfeitas. A complexidade de tempo deste procedimento O(n). Se m o tamanho da entrada usando uma representao binria, o tempo O(m)[4].

1.3 Reduo PolinomialVamos apresentar uma reduo polinomial a partir de outro problema conhecido como NP -Completo para o problema da Mochila. Antes de faz-lo vamos dar uma verso de um problema de deciso para o Problema da Mochila 0/1. O problema de Otimizao difere do problema de Deciso somente na funo de Otimizao. Assim a verso de Deciso para o problema da Mochila a seguinte: Entrada: um conjunto de n tens, tal que todo i tem utilidade ci e peso wi , uma mochila tem capacidade W e um valor positivo C . Questo: Existe um subconjunto S {1, ..., n} de tens, tais que o peso total no mximo W : wi WiS

2

e o valor da utilidade total pelo menos C :

c(S) =iS

ci C?

Para provar que a verso de deciso do problema da Mochila N P -completo vamos fazer uma reduo polinomial a partir do problema Maximum Subset Sum Soluo: A verso do problema de deciso para Maximum Subset Sum denida como apresentada em [3]: Entrada: Um conjunto nito A, um tamanho inteiro positivo si para cada elemento i A, e um inteiro positivo B . Questo: Existe uma subconjunto A A tal que

si = B?iA

Como podemos notar, Maximum Subset Sum um caso especial do problema de Otimizao do Problema da Mochila 0/1 com ci = wi , como citado em [2]. A reduo completa como se apresenta a seguir: Dados uma instncia do problema Subset Sum, reduziremos esta para uma instncia do Problema da Mochila 0/1 da seguinte forma :

U = A, wi = ci = si , W = C = BEsta reduo feita em tempo polinomial, desde que todas as atribuies so executadas em tempo polinomial. Desta forma uma, resposta para uma instncia do problema da Mochila corresponde a uma resposta para o problema Maximum Subset Sum.

Uma resposta "sim"para uma instncia do Problema da Mochila 0/1 signica que existe um subconjunto S U tal que wi W andiS iS

ci C

Isto signica, usando a nossa transformao, que existe um subconjunto A A tal que B si B.iA

Isto ,

si = B.iA

Assim, por denio, uma resposta "sim"para problema Subset Sum.

Um resposta "No"para o Problema da Mochila 0/1, signica que tal conjunto no existe. O que , exatamente, uma resposta negativa para o problema Subset Sum.Assim mostramos que:

o problema da Mochila est em N P e, existe uma reduo polinomial a partir do problema Maximum Subset Sum para o Problema da Mochila 0/1.Com isso provamos que Problema da Mochila 0/1 N P -Completo. 3

2 Soluo usando BacktrackingBacktracking uma estratgia para sistematicamente examinar a lista de possveis solues. A idia do backtracking eliminar a vericao explcita de uma boa parte dos possveis candidatos. Para tanto, o problema deve respeitar as restries que maximizam/minimizam alguma funo de otimizao. Os seguintes passos so respeitados: 1. Denir um espao de soluo para o problema. Este espao de soluo deve incluir pelo menos uma soluo tima para o problema. 2. Organizar o espao de soluo de forma que seja facilmente pesquisado. A organizao tpica uma rvore. 3. Proceder a busca em profundidade. Backtracking uma estratgia que se aplica em problemas cuja soluo