Empacotamento de conjuntos
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) |
Exemplos
[editar | editar código-fonte]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.
Heurísticas
[editar | editar código-fonte]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).
Complexidade
[editar | editar código-fonte]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 e 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.
Notas
[editar | editar código-fonte]- ↑ Vazirani (2001)
- ↑ 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.
- ↑ 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
- ↑ 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
Referências
[editar | editar código-fonte]- Maximum Set Packing, Viggo Kann.
- "set packing". Dictionary of Algorithms and Data Structures, editor Paul E. Black, National Institute of Standards and Technology. Note that the definition here is somewhat different.
- Steven S. Skiena. "Set Packing". The Algorithm Design Manual. Last modified June 2, 1997.
- Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger. "Maximum Set Packing". A compendium of NP optimization problems. Last modified March 20, 2000.
- Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. [S.l.]: W.H. Freeman. ISBN 0-7167-1045-5 A3.1: SP3, pg.221.
- Vazirani, Vijay V. (2001). Approximation Algorithms. [S.l.]: Springer-Verlag. ISBN 3-540-65367-8
Ligações externas
[editar | editar código-fonte]- [1]: A Pascal program for solving the problem. From Discrete Optimization Algorithms with Pascal Programs by MacIej M. Syslo, ISBN 0-13-215509-5.
- Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination
- Solving packaging problem in PHP