Saltar para o conteúdo

Empacotamento de conjuntos

Origem: Wikipédia, a enciclopédia livre.

Empacotamento de conjuntos é um clássico NP-completo problema em complexidade computacional teoria e análise combinatória, e foi um dos Karp 21 problemas NP-completos.

Suponha que temos um conjunto finito S e uma lista de subconjuntos de S. Então, problema de empacotamento de conjuntos pergunta se algum conjunto com k subconjuntos da lista são dois a dois disjuntos (em outras palavras, não há dois compartilham um elemento).

Mais formalmente, dado um universo   e uma família  de subconjuntos de , um empacotamento é uma subfamília  de conjuntos de tal forma que todos os conjuntos em são disjuntos dois a dois, e o tamanho do pacote é . No problema de decisão de empacotamento de conjuntos, a entrada é um par  e um inteiro ; a questão é se há um pacote de conjuntos de tamanho ou mais. No problema de otimização de empacotamento de conjuntos, a entrada é o par , e a tarefa é encontrar um pacote de conjuntos que utilize a maioria dos conjuntos.

O problema está, claramente, em NP, uma vez que, dado k subconjuntos, podemos facilmente verificar que eles são pares disjuntos em tempo polinomial.

A versão otimizada do problema, o máximo empacotamento de conjuntos, pede-lhe o número máximo de pares disjuntos conjuntos na lista. É um problema de maximização, que pode ser formulado, naturalmente, como um programa linear inteiro, pertence à classe de problemas de empacotamento, e o seu dual programa linear é o problema da cobertura de conjuntos.[1]

Formulação do programa linear inteiro 

[editar | editar código-fonte]

O conjunto máximo de embalagem problema pode ser formulado como o seguinte programa linear inteiro.

maximizar (maximizar o número total de subconjuntos)
sujeito a para todo (conjuntos selecionados tem que ser par disjunto)
para todo . (cada conjunto é o pacote de conjuntos ou não)

Como um exemplo simples, suponha que a sua cozinha contém uma coleção de diferentes ingredientes de alimentos (), e você tem um livro de receitas com uma coleção de receitas ( ). Cada receita exige um subconjunto dos ingredientes. Você pretende preparar a maior coleção de receitas do livro. Na verdade, você está procurando por um empacotamento () no () - uma coleção de receitas cujos conjuntos de ingredientes são pares disjuntos.

Como outro exemplo, suponha que você esteja em uma convenção de embaixadores estrangeiros, cada um dos quais fala inglês e várias outras línguas. Você deseja fazer um anúncio a um grupo deles, mas por você não confiar neles, você não quer que eles sejam capazes de conversar entre si sem que você seja capaz de compreendê-los. Para garantir isso, você vai escolher um grupo de tal forma que não há dois embaixadores que falem a mesma língua, que não o inglês. Por outro lado, você também quer dar o seu anúncio como embaixadores possível. Neste caso, os elementos do conjunto são outros idiomas que não o inglês, e os subconjuntos são os conjuntos de línguas faladas por um determinado embaixador. Se dois conjuntos são disjuntos, os dois embaixadores compartilham outros idiomas que não o inglês. Um conjunto máximo de empacotamento irá escolher o maior número possível de embaixadores, sob a pretendida restrição. Embora este problema é de difícil resolução e, em geral, neste exemplo, uma boa heurística é escolher primeiro embaixadores que só falam línguas incomuns, de modo que muitas pessoas são desqualificados.

Versão ponderada

[editar | editar código-fonte]

Há uma versão ponderada do problema do empacotamento de conjunto em que cada subconjunto é atribuído um peso real e é esse peso que deseja maximizar:

No nosso simples exemplo acima, podemos peso das receitas de acordo com o número de amigos que amam a resultante pratos, para que o nosso jantar vai agradar o maior número de amigos.

O problema de empacotamento de conjuntos que pode ser difícil para alguns k, mas não é difícil encontrar um k para o qual é fácil em uma determinada entrada. Por exemplo, podemos utilizar um algoritmo guloso onde olhamos para o conjunto que cruza o menor número de outros conjuntos, adicioná-lo para a nossa solução, e remover os conjuntos intersectados. Estamos continuamente fazendo isso até que não tenham conjuntos restantes, e temos um pacote de conjuntos do tamanho de alguns, apesar de não ser o máximo empacotamento de conjuntos. Embora nenhum algoritmo possa sempre produzir resultados perto do máximo (veja a próxima seção).

O problema de empacotamento de conjuntos não é apenas um problema NP-completo, mas a sua versão otimizada (problema do máximo empacotamento de conjuntos) tem sido comprovada de tão difícil aproximação quanto como o problema do máximo clique; em particular, ele não pode ser aproximado dentro de qualquer fator constante.[2] O melhor algoritmo conhecido aproxima dentro de um factor de .[3] A versão ponderada também pode ser aproximada assim.[4]

No entanto, o problema tem uma variante que é mais tratável: se nós não assumimos nenhuma subconjunto excede k≥3 elementos, a resposta pode ser aproximada dentro de um fator de k/2 + ε para qualquer ε > 0; em particular, o problema com 3 conjuntos de elementos pode ser estimado em cerca de 50%. Em outra variante mais tratável, se nenhum elemento ocorre em mais de k de subconjuntos, a resposta pode ser aproximada dentro de um fator de k. Isso também é verdadeiro para o versão ponderada.

Problemas equivalentes

[editar | editar código-fonte]

Existe uma redução de tempo polinomial de um-para-um entre o problema do conjunto independente e o problema de empacotamento de conjuntos:

  • Dado o problema de empacotamento de conjuntos sobre uma coleção , crie um grafo onde para cada conjunto existe um vértice , e existe uma aresta entre  sse . Agora, cada conjunto independente de vértices no grafo gerado corresponde à um pacote de conjuntos em .
  • Dado um problema de conjuntos de vértices independentes em um grafo , crie uma coleção de conjuntos onde para cada vértice  existe um conjunto  contendo todos os vértices adjacentes à . Agora, cada pacote de conjuntos na coleção gerada corresponde à um conjunto de vértices independentes em .

Este é também um bidirecional redução APMS, e mostra que os dois problemas são igualmente difíceis para se aproximar.

Casos especiais

[editar | editar código-fonte]

Correspondência e 3-dimensional de correspondência são casos especiais de de empacotamento. Uma correspondente de tamanho máximo pode ser encontrada em tempo polinomial, mas encontrar um maior 3-dimensional de correspondência ou de um maior conjunto independente é NP-difícil.

Outros problemas relacionados

[editar | editar código-fonte]

Definir o empacotamento é uma entre uma família de problemas relacionados à cobertura ou particionamento de elementos de um conjunto. Um problema intimamente relacionado é o problema de cobertura de conjuntos. Aqui, também dado um conjunto S e uma lista de conjuntos, mas o objetivo é determinar se podemos escolher k conjuntos que, juntos, contêm todos os elementos de S. Estes conjuntos podem sobrepor-se. A versão otimizada encontra, o número mínimo de tais conjuntos. O conjunto máximo de empacotament não precisa cobrir todos os possíveis elementos.

O problema NP-completo da cobertura exata, por outro lado, exige que cada elemento a ser contidos em exatamente um dos subconjuntos. Encontrar uma cobertura exata em tudo, independentemente do tamanho, é um problema NP-completo. No entanto, se criar um conjunto singleton para cada elemento de S e adicioná-las à lista, o problema resultante é tão fácil como o empacotamento de conjuntos.

Karp originalmente mostrou que empacotamento de conjuntos é NP-completo através de uma redução da camarilha problema.

Veja também: Packing in a hypergraph.

  1. Vazirani (2001)
  2. Hazan, Elad; Safra, Shmuel; Schwartz, Oded (2006), «On the complexity of approximating k-set packing», Computational Complexity, 15 (1): 20–39, MR 2226068, doi:10.1007/s00037-006-0205-6 .
  3. Halldórsson, Magnus M.; Kratochvíl, Jan; Telle, Jan Arne (1998). Independent sets with domination constraints. 25th International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science. 1443. Springer-Verlag. pp. 176–185 
  4. Halldórsson, Magnus M. (1999). Approximations of weighted independent set and hereditary subset problems. 5th Annual International Conference on Computing and Combinatorics. Lecture Notes in Computer Science. 1627. Springer-Verlag. pp. 261–270 

Ligações externas

[editar | editar código-fonte]