Problema da partição
Na ciência da computação, o problema da partição (ou particionamento de números[1]) é a tarefa de decidir se um determinado multiconjunto S de números inteiros positivos pode ser particionado em dois subconjuntos de S1 e S2 , tais que a soma dos números em S1 é igual à soma dos números em S2. Embora o problema da partição seja NP-completo, existe uma solução com programação dinâmica com tempo pseudo-polinomial e há uma heurística que resolve o problema, em muitos casos, de forma otimizada, ou aproximadamente. Por esta razão, ele tem sido chamado de "o problema NP-difícil mais fácil".[2]
Há uma versão otimizada do problema da partição, que é particionar o multiconjunto S em dois subconjuntos S1, S2 , tais que a diferença entre a soma dos elementos de S1 e a soma dos elementos de S2 é minimizada. A versão de otimização é NP-difícil, mas pode ser resolvida de forma eficiente na prática.[3]
Exemplos
Dado S = {3,1,1,2,2,1}, uma solução válida para o problema da partição é formada pelos dois conjuntos S1 = {1,1,1,2} e S2 = {2,3}. Ambos os conjuntos a soma é de 5, e eles são partições de S. Note que esta solução não é única. S1 = {3,1,1} e S2 = {2,2,1} é outra solução.
Nem todos os multiconjuntos de números inteiros positivos tem uma partição em duas metades, com igual soma. Um exemplo de um conjunto S = {2,5}.
Algoritmo de tempo pseudo-polinomial
O problema pode ser resolvido usando programação dinâmica quando o tamanho do conjunto e o tamanho da soma dos números inteiros no conjunto não é muito grande para tornar os requisitos de armazenamento inviável.
Suponha que a entrada para o algoritmo seja uma lista com a seguinte forma:
- S = x1, ..., xn
Seja N o número de elementos de S. Seja K a soma de todos os elementos de S. Ou seja: K = x1 + ... + xn. Vamos construir um algoritmo que determina se existe um subconjunto de S cuja soma é . Se existe um subconjunto, em seguida:
- se K é par, o resto de S também tem soma
- se K é ímpar, então o resto de S tem soma . Esta é uma boa solução possível.
Relação de recorrência
Desejamos determinar se existe um subconjunto de S que tem soma (. Seja:
- p(i, j) é Verdadeiro se um subconjunto de { x1, ..., xj } tem soma i e False caso contrário.
Então p(, n) é Verdadeira se, e somente se, existe um subconjunto de S cuja soma é . O objetivo do nosso algoritmo será para calcular p(, n). Para isso, temos a seguinte relação de recorrência:
- p(i, j) é Verdadeiro se qualquer p(i, j − 1) é Verdadeira ou se p(i − xj, j − 1) é Verdadeiro
- p(i, j) é Falso caso contrário
A razão para isso é a seguinte: existe algum subconjunto de S que tem soma i utilizando números
- x1, ..., xj
se e somente se uma das seguintes condições for verdadeira:
- Existe um subconjunto de { x1, ..., xj-1 } que tem soma i;
- existe um subconjunto de { x1, ..., xj-1 } que tem soma i − xj, uma vez que xj + subconjunto da soma = i.
Notas
- ↑ Korf 1998
- ↑ Hayes 2002
- ↑ Korf, Richard E. (2009). Multi-Way Number Partitioning (PDF). IJCAI
<ref>
com nome "knapsack" definido em <references>
não é utilizado no texto da página.Referências
- Hayes, Brian (Maio–Junho de 2002), «The Easiest NP Hard Problem», American Scientist
- Karmarkar, Narenda; Karp, Richard M (1982), «The Differencing Method of Set Partitioning», University of California at Berkeley: Computer Science Division (EECS), Technical Report UCB/CSD 82/113
- Gent, Ian; Walsh, Toby (agosto 1996), Wolfgang Wahlster, ed., Phase Transitions and Annealed Theories: Number Partitioning as a Case Study, John Wiley and Sons, pp. 170–174
- Gent, Ian; Walsh, Toby (1998), «Analysis of Heuristics for Number Partitioning», Computational Intelligence, 14 (3): 430–451, doi:10.1111/0824-7935.00069
- Mertens, Stephan (novembro 1998), «Phase Transition in the Number Partitioning Problem», Physical Review Letters, 81 (20), Bibcode:1998PhRvL..81.4281M, arXiv:cond-mat/9807077
, doi:10.1103/PhysRevLett.81.4281, consultado em 3 de outubro de 2009
- Mertens, Stephan (2001), «A physicist's approach to number partitioning», Theoretical Computer Science, 265 (1-2): 79–108, doi:10.1016/S0304-3975(01)00153-0
- Mertens, Stephan (2006), «The Easiest Hard Problem: Number Partitioning», in: Allon Percus; Gabriel Istrate; Cristopher Moore, Computational complexity and statistical physics, ISBN 9780195177374, Oxford University Press US, p. 125, Bibcode:2003cond.mat.10317M, arXiv:cond-mat/0310317
- Borgs, Christian; Chayes, Jennifer; Pittel, Boris (2001), «Phase transition and finite-size scaling for the integer partitioning problem», Random Structures and Algorithms, 19 (3-4): 247–288, doi:10.1002/rsa.10004, consultado em 4 de outubro de 2009
- Korf, Richard E. (1998), «A complete anytime algorithm for number partitioning», Artificial Intelligence, ISSN 0004-3702, 106 (2): 181–203, doi:10.1016/S0004-3702(98)00086-1, consultado em 4 de outubro de 2009
- Mertens, Stephan (1999), A complete anytime algorithm for balanced number partitioning, Bibcode:1999cs........3011M, arXiv:cs/9903011