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 S₁ e S₂ , tais que a soma dos números em S₁ é igual à soma dos números em S₂. 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 S₁, S₂ , tais que a diferença entre a soma dos elementos de S₁ e a soma dos elementos de S₂ é minimizada. A versão de otimização é NP-difícil, mas pode ser resolvida de forma eficiente na prática.^[3]

Dado S = {3,1,1,2,2,1}, uma solução válida para o problema da partição é formada pelos dois conjuntos S₁ = {1,1,1,2} e S₂ = {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. S₁ = {3,1,1} e S₂ = {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}.

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 = x₁, ..., x_n

Seja N o número de elementos de S. Seja K a soma de todos os elementos de S. Ou seja: K = x₁ + ... + x_n. Vamos construir um algoritmo que determina se existe um subconjunto de S cuja soma é ${\displaystyle \lfloor K/2\rfloor }$. Se existe um subconjunto, em seguida:

se K é par, o resto de S também tem soma ${\displaystyle \lfloor K/2\rfloor }$

se K é ímpar, então o resto de S tem soma ${\displaystyle \lceil K/2\rceil }$. Esta é uma boa solução possível.

Desejamos determinar se existe um subconjunto de S que tem soma (${\displaystyle \lfloor K/2\rfloor }$. Seja:

p(i, j) é Verdadeiro se um subconjunto de { x₁, ..., x_j } tem soma i e False caso contrário.

Então p(${\displaystyle \lfloor K/2\rfloor }$, n) é Verdadeira se, e somente se, existe um subconjunto de S cuja soma é ${\displaystyle \lfloor K/2\rfloor }$. O objetivo do nosso algoritmo será para calcular p(${\displaystyle \lfloor K/2\rfloor }$, 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 − x_j, 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

x₁, ..., x_j

se e somente se uma das seguintes condições for verdadeira:

Existe um subconjunto de { x₁, ..., x_j-1 } que tem soma i;

existe um subconjunto de { x₁, ..., x_j-1 } que tem soma i − x_j, uma vez que x_j + subconjunto da soma = i.

• 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