Projeto E Analise De Algoritmos 2007 1 Projeto 2 Analise De

Análise de complexidade

BPP-1 é NP-Difícil

Enunciamos que o bin packing é um problema NP-Difícil. Em outras palavras, estamos dizendo que não se conhece um algoritmo polinomial para a versão de decisão do BPP-1:

  • dados $n$ itens, cada um com peso inteiro Wj $(j=1,...,n)$, e inteiros $m$ e $c$, decidir se existe uma solução viável para o problema de armazenar os $n$ itens nos $m$ bins com capacidade $c$ cada.

Para provar esta afirmação de que BPP-1 $\in$ NP-Difícil, basta reduzirmos um problema $P1$ conhecidamente pertencente à classe de problemas NP-Difícil ao problema BPP-1.

Para esta prova, foi escolhido o problema Partition, cuja definição de sua versão de decisão é dada a seguir:

  • Dado um multiconjunto $V$ de $n$ inteiros, decidir se existe um subconjunto $S \subseteq V$ tal que $\sum_{x \in S} x = \sum_{y \in V-S} y$.

Redução do problema Partition para o BPP-1

Dada uma instância de Partition, ou seja, dado um multiconjunto $V$ de $n$ inteiros, criamos uma instância do BPP-1 da seguinta forma:

  • $n = |V|$
  • pesos W $= V$
  • $c = \frac{\sum_{x \in V} x}{2}$
  • $m = 2$

Se o BPP-1 responde sim, significa que existe uma solução viável para armazenar os $n = |V|$ itens de pesos W $= V$ nos 2 bins de capacidade c = $\frac{\sum_{x \in V} x}{2}$ cada.

Já que a soma total dos pesos dos $n$ itens é $2c$ e que todos os itens podem ser armazenados nos 2 bins disponíveis, necessariamente a soma dos itens de cada bin é exatamente igual a c.

Desse modo, é nítido que existe um particionamento do multiconjunto $V$ tal que a soma dos itens de uma partição seja igual à soma dos itens da outra partição: basta escolher os itens armazenados em um dos bins para ser o subconjunto $S$, e os itens do outro bin para denotar $V - S$. Em outras palavras, se o BPP-1 responde sim para uma determinada instância definida como acima, necessariamente o problema Partition também responde sim.

De modo inverso, caso exista uma partição do multiconjunto $V$ em um subconjunto $S$ (cuja soma de itens é $c$) e outro subconjunto $V - S$ (cuja soma de itens também é $c$), se fizermos a redução conforme definida mais acima, o problema BPP-1 também responderá sim, já que será possível armazenar os $|V|$ itens de peso W $= V$ nos m = 2 bins de capacidade $c$ cada: basta armazenar todos os itens de $S$ em um bin e todos os itens de $V - S$ no outro bin. Em outras palavras, se o problema Partition responde sim para uma determinada instância, necessariamente o BPP-1 também responderá sim caso seja usada a redução como definida acima.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.