Problema da soma dos subconjuntos

Em ciência da computação, o problema da soma de subconjuntos é um importante problema da teoria da complexidade computacional e criptografia. O problema é este: dado um conjunto de inteiros, existe um subconjunto não-vazio cuja soma é 0? Por exemplo, dado o conjunto { −7, −3, −2, 5, 8}, a resposta é sim porque o subconjunto { -3, -2, 5} resulta numa soma que dá zero. O problema é NP-completo.

Um problema equivalente é este: dado um conjunto de inteiros e um inteiro s, existe algum subconjunto que some s? Problema da soma dos subconjuntos também pode ser pensado como um caso especial do problema da mochila. Um caso interessante de soma subconjunto é o problema de partição, em que s é a metade da soma de todos os elementos do conjunto.

Complexidade

A complexidade (dificuldade de resolver) da soma de subconjuntos poderá ser vista de dois parâmetros, N, o número de variáveis de decisão, e P, a precisão do problema (indicado como o número de bits necessários para indicar/resolver o problema). (Nota: aqui as letras N e P significa algo diferente do que eles querem dizer na classe de problemas NP).

A complexidade do melhor algoritmo conhecido é exponencial no menor dos dois parâmetros N e P. Assim, o problema é mais difícil se N e P são da mesma ordem. E torna-se fácil se nem N ou P são pequenas.

Se N (número de variáveis) é pequeno, então a busca exaustiva pela solução é possível. Se P (the number of place values) é um número pequeno fixo, então existem algoritmos de programação dinâmica que podem resolver.

O que acaba acontecendo é que o problema se torna aparentemente não-exponencial quando se é prático para considerar o espaço da solução. Existem duas maneiras de medir o espaço de solução do Problema da soma dos subconjuntos. Uma delas é contar o número de maneiras que as variáveis podem ser combinadas. Existem 2^N possíveis maneiras de combinar as variáveis. Contudo, com N = 10, existem somente 1024 possíveis combinações para checar. Estes podem ser contadas facilmente com uma branching search. A outra maneira é considerar a combinação de todos os valores numéricos possíveis. Estes poderão ser contados facilmente com um algoritmo de programação dinâmica. Quando N = P e ambos são grandes, então não há nenhum aspecto do espaço de soluções que podem ser contados facilmente.

Algoritmos eficientes para casos de N e P pequenos são dados abaixo.

Algoritmo de Tempo Exponencial

Existem muitas maneiras de resolver o problema da soma de subconjunto em tempo exponencial em N. O algoritmo mais ingênuo percorreria todos os subconjuntos de N números e, para cada um, checaria se o subconjunto soma um certo valor. O tempo de execução é da ordem de O(2^NN), existem 2^N subconjuntos e, para checar cada subconjunto, precisamos somar no máximo N elementos.

O melhor tempo exponencial conhecido é da ordem O(2^N/2). O algoritmo divide arbitrariamente os N elementos em dois conjuntos com N/2 cada. Para cada elemento dos dois conjuntos, ele armazena uma lista com a soma de todos 2^N/2 possíveis conjuntos de elementos. É sorteada duas lista. Usando um algoritmo de ordenação para este passo, a ordem passa a ser de O(2^N/2N). Contudo, dado uma lista ordenada das somas para k elementos, a lista poderá ser expandida para duas listas ordenadas com a introdução de um (k + 1)st elemento, e essas duas listas ordenadas podem ser fundidas em tempo O(2^k). Assim, para cada lista poderá gerar uma forma ordenada em tempo O(2^N/2). Dada duas listas ordenadas, o algoritmo poderá checar se um elemento do primeiro array e um elemento do segundo array somam s em tempo O(2^N/2). Para isto, o algoritmo passará pelo primeiro array em ordem decrescente (iniciando pelo maior elemento) e no segundo array em ordem crescente (iniciando pelo menor elemento). Sempre que a soma do elemento atual do primeiro array e o elemento atual do segundo array é mais que s, o algoritmo move para o próximo elemento do primeiro array. Se a soma for menor que s, o algoritmo move para o próximo elemento do segundo array. Se ambos elementos somam s, ele pára. Horowitz and Sahni publicaram inicialmente este algoritmo em um relatório técnico em 1972.

Solução pseudo-polinomial de programação dinâmica

O problema pode ser resolvido usando programação dinâmica. Suponha a sequência seja:x₁, …, x_n

e nós queremos determinar se existe um subconjunto não-vazio cuja soma é s. Seja N a soma dos valores negativos e P a soma dos valores positivos. Defina uma função booleana Q(i,s) (valores possíveis são verdadeiro e falso) de "Existe um subconjunto não-vazio de x₁, …, x_i cuja soma é s".

Assim, a solução para o problema será o valor de Q(n,0).

Claramente, Q(i,s) = falso se s <N ou s > P será falso se 1 ≤ i ≤ n ou N ≤ s ≤ P. então esses valores não são necessários para armazenamento ou computação.

Crie um array para armazenar os valores Q(i,s) para 1 = i = n e N = s = P.

O array poderá agora ser preenchido usando recursão. Inicialmente, para N ≤ s ≤ P,, atribua :Q(1,s) := (x₁ == s).

Então, para i = 2, ..., n, atribua

Q(i,s) := Q(i - 1,s) ou (x_i == s) ou Q(i - 1,s - x_i) para N ≤ s ≤ P.

Para cada atribuição, os valores de Q no lado direito já são conhecidas, ou porque eram armazenados na tabela para o valor anterior de i ou porque Q(i - 1,s - x_i) = falso se s - x_i <N ou s - x_i > P.

Portanto, o número total de operações aritméticas é O(n(P - N)).. Por exemplo, se todos os valores são O(n^k) para algum k, quando o tempo requerido é O(n^k+2).

Este algoritmo é facilmente modificado para retornar um subconjunto com a soma 0 se existe um.

Esta solução não pode ser contada em tempo polinomial na teoria da complexidade porque P - N é não polinomial no tamanho do problema, que é o número de bits usados ??para representá-lo. Este algoritmo é polinomial nos valores de N e P, que são exponencial em seu número de bits. Para o caso de que cada xi é positivo e limitado pela mesma constante, Pisinger encontrado um algoritmo de tempo linear.

Algoritmo de tempo polinomial aproximado

Numa versão apropriada de um subconjunto da soma poderá ser: dado um conjunto de N números

x₁, x₂, …, x_N e o número s, como saída

sim, se existe um subconjunto cuja soma seja s;
não, se não existe um subconjunto cuja soma seja um número entre (1 - c)s e s para algum c > 0;
qualquer resposta, se existe um subconjunto cuja soma é um número entre (1 - c)s e s porém sem subconjunto que some s.

Se todos os números são não-negativos, a soma aproximada é solúvel em tempo polinomial in N e 1/c.

A solução para a soma dos subconjuntos provêm da solução para o problema da soma dos subconjuntos original no caso, onde os números são pequenos (novamente, para números não-negativos). Se alguma soma dos números pode ser especificado com mais de P bits, então podemos resolver o problema aproximadamente com c = 2 - P, isto é equivalente à resolver exatamente. Então, o algoritmo de tempo polinomial para aproximar a soma torna-se-à ao algoritmo com tempo de execução em N e 2P(ou seja, exponencial em P).

O algoritmo para aproximação é o seguinte:

inicialize a lista S para armazenar o valor 0.

para cada i de 1 para N faça

   considere T cuja uma lista consistindo em  x_i + y, para todos y em S
   considere U seja a união ref T e S
   ordene U
   faça S vazia
   faça y seja o menor elemento de U
   some y para S
   para cada elemento z de U em ordem faça
      //rearranje a lista eliminando números próximos
      //e rejeite elementos maiores que s
     se y + cs/N < z = s, atribua y = z e adicione z à S
 se S contém um número entre (1 - c)s e s, retorne sim, senão não

O algoritmo é de tempo polinomial porque as listas S, T e U sempre permanecem de tamanho polinomial em N e 1/c e, quanto maior é o tempo polinomial, todas as operações poderão ser feitas em tempo polinomial. O tamanho das listas é mantido polinomial pela etapa de recorte, em que nós só incluímos um número z em S se ele é maior que a anterior por cs/N e não maior do que s. Esta etapa garante que cada elemento de S é menor do que o próximo por elementos, pelo menos, cs/N e não contêm maior que s. Qualquer lista com que a propriedade consiste em não mais do que elementos N / c.

O algoritmo é correto, pois cada etapa introduz um erro aditivo de no máximo passos cs/N e N em conjunto introduzir o erro de, no máximo, cs.