64
Algoritmos - Teoria e Prática - 3ª Ed. 2012

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas Cormen IBSN: 9788535236996

Elaborado por professores e especialistas

Passo 1 de 8keyboard_arrow_downkeyboard_arrow_up

Temos um conjunto de n objetos onde os tamanhos estão entre 0 e 1. Desejamos empacotar todos os objetos no número mínimo de caixas de tamanho unitário. Vamos provar que esse problema é NP-difícil.

Passo 2 de 8keyboard_arrow_downkeyboard_arrow_up

Primeiro vamos mostrar que é NP-difícil determinar se, dado um conjunto de números, existe um subconjunto deles cuja soma é igual à soma do complemento daquele conjunto (problema da partição). Vamos mostrar que este é NP-difícil usando-o para resolver o problema de soma de subconjunto.

Passo 3 de 8keyboard_arrow_downkeyboard_arrow_up

Suponha que quiséssemos encontrar um subconjunto de cuja soma seja t. Vamos então rodar a partição no conjunto , cuja soma é . Assim qualquer partição deve ter ambos os lados iguais a .

Passo 4 de 8keyboard_arrow_downkeyboard_arrow_up

Se existir um subconjunto do conjunto original cuja soma seja t, nós podemos pô-lo em um lado junto com o elemento que adicionamos e por todos os outros elementos originais do outro lado, o que nos dá uma partição.

Passo 5 de 8keyboard_arrow_downkeyboard_arrow_up

Supondo que tenhamos uma partição, então todos os elementos que estão do mesmo lado do elemento adicionado formam um subconjunto cuja soma é t. Isso mostra que o problema de partição é NP-difícil.

Passo 6 de 8keyboard_arrow_downkeyboard_arrow_up

Chamamos de uma instancia do problema de partição, então vamos construir uma instância do problema de empacotamento que pode ser empacotado em duas caixas se, e somente se, existir um subconjunto de cuja soma seja igual àquela do seu complemento.

Passo 7 de 8keyboard_arrow_downkeyboard_arrow_up

Para fazer isso, somente chamaremos nossos valores de . Então o peso total é exatamente 2, portanto claramente duas caixas são necessárias, Além disso ele só pode caber em duas caixas se houver uma partição do conjunto original.

Passo 8 de 8keyboard_arrow_downkeyboard_arrow_up

Demonstramos, então, por redução, que o problema de empacotamento em caixas é NP-difícil.

Navegar por capítulo