Saltar al contenido

Algoritmo de suma de subconjuntos

Solución:

Subset Sum es el primer problema NP-completo que aprendí en Macalester. Esta pregunta se ve más de 36000 veces, pero no veo una respuesta suficiente que explique el algoritmo en detalle con lógica. Así que pensé en intentarlo.

Suposición:

En aras de la simplicidad, primero asumí que el conjunto de entrada X contiene solo enteros positivos y k es positivo. Sin embargo, podemos ajustar el algoritmo para manejar enteros negativos y el caso si k es negativo.

Lógica:

La clave de este algoritmo o realmente cualquier problema de DP es desglosar el problema y comenzar simplemente desde un caso base. luego podemos construir sobre el caso base usando algunos conocimientos que conocemos:

  1. sabemos que si el set X está vacío, entonces no hay forma de que podamos sumar ningún valor de k.
  2. Si un conjunto X contiene k entonces tiene una suma de subconjunto para k.
  3. sabemos que si un subconjunto del conjunto x1 quien es un subconjunto de X suma a k1 luego X tendrá un subconjunto que suma a k1 a saber x1.
  4. tenemos un set X = {x1, x1, x3, ......., xn, xn+1}. Sabemos que tiene una suma de subconjunto para k1 si x1 = {x1, x1, x3, ......., xn} tiene una suma de subconjunto a k - k1.

Ejemplo para ilustrar 1,2,3,4:

  1. es fácil. si tiene un conjunto vacío {}. no puede tener un subconjunto, por lo que no puede tener ninguna suma de subconjunto.

  2. Un conjunto X = {4} tiene un subconjunto suma a 4 porque 4 en sí mismo es parte del conjunto

  3. di que tienes un set x1 = {1,3,5} quien es un subconjunto del conjunto X = {1,3,5,2,8}. si x1 tiene una suma de subconjunto a k1 = 8 entonces eso significa X también tiene un subconjunto suma a 8 porque x1 es un subconjunto de X

  4. di que tienes un set X = {1,3,5,2,19} y queremos saber si tiene una suma de subconjunto a 20. La tiene y una forma de saber si es x1 = {1,3,5,2} puede sumar a (20 – 19) = 1. Dado que x1 tiene un subconjunto suma a 1, cuando agregamos 19 al conjunto x1 podemos tomar ese nuevo número 1 + 19 = 20 para crear nuestra suma deseada 20.

Construye dinámicamente una matriz
¡Frio! ahora utilicemos las cuatro lógicas anteriores y comencemos a construir desde el caso base. Vamos a construir una matriz m. Definimos:

  • matriz m tiene i+1 filas y k + 1 columnas.

  • Cada celda de la matriz tiene valor true o false.

  • metro[i][s] devuelve verdadero o falso para indicar la respuesta a esta pregunta: “usando el primer i elementos en la matriz podemos encontrar una suma de subconjunto para s? ” m[i][s]devoluciones true por si y false por no

(tenga en cuenta la respuesta de Wikipedia o la mayoría de las personas construyen una función m (i, s) pero pensé que la matriz es una forma fácil de entender la programación dinámica. Funciona bien cuando solo tenemos números positivos en el conjunto o matriz. Sin embargo, la matriz La ruta de función es mejor porque no tiene que lidiar con el índice fuera de rango, el índice de coincidencia de la matriz y la suma de la matriz …)

Construyamos la matriz usando un ejemplo: 

X = {1,3,5,2,8}
k = 9

Vamos a construir la matriz fila por fila. En última instancia, queremos conocer la celda m[n][k] Contiene true o false.

Primera fila:

La lógica 1 nos dijo que la primera fila de la matriz debería ser false. 

   0 1 2 3 4 5 6 7 8 9
   _ _ _ _ _ _ _ _ _ _
0| F F F F F F F F F F
1|
2|
3|
4|
5|

Segunda fila y superior:

Luego, para la segunda fila o superior, podemos usar la lógica 2, 3, 4 para ayudarnos a poblar la matriz.

  • la lógica 2 nos dice que m[i][s] = (X[i-1] == s) rememebr m[i] se refiere al i-ésimo elemento de X, que es X[i-1]
  • la lógica 3 nos dice que m[i][s] = (m[i-1][s]) esto es mirar la celda directamente arriba.
  • La lógica 4 nos dice que m[i][s] = (m[i-1][s - X[i-1]]) esto es mirar la fila arriba y a la izquierda de X[i-1] células.

Si alguno de estos es true luego m[i][s] es true de lo contrario false. para que podamos reescribir 2,3,4 en m[i][s] = (m[i-1][s] || a[i-1] == s || m[i-1][s - a[i-1]])

Utilice estas lógicas anteriores para poblar la matriz m. En nuestro ejemplo, se ve así.

   0 1 2 3 4 5 6 7 8 9
   _ _ _ _ _ _ _ _ _ _
0| F F F F F F F F F F
1| F T F F F F F F F F
2| F T F T T F F F F F 
3| F T F T T T T F T T
4| F T T T T T T T T T 
5| F T T T T T T T T T

Ahora usa la matriz para responder tu pregunta:

mirar m[5][9] que es la pregunta original. utilizando los primeros 5 elementos (que son todos los elementos) ¿podemos encontrar una suma de subconjunto a 9 (k)? y la respuesta está indicada por esa celda que es true

Aquí está el código:

import java.util.*;

public class SubSetSum {

    public static boolean subSetSum(int[] a, int k){

        if(a == null){
            return false;
        }

        //n items in the list
        int n = a.length; 
        //create matrix m
        boolean[][] m = new boolean[n + 1][k + 1]; //n + 1 to include 0, k + 1 to include 0 

        //set first row of matrix to false. This also prevent array index out of bounds: -1
        for(int s = 0; s <= k; s++){
            m[0][s] = false;
        }

        //populate matrix m
        for(int i = 1; i <= n; i++){
            for(int s = 0; s <= k; s++){    
                if(s - a[i-1] >= 0){ //when it goes left we don't want it to go out of bounds. (logic 4)
                    m[i][s] = (m[i-1][s] || a[i-1] == s || m[i-1][s - a[i-1]]); 
                } else {
                    m[i][s] = (m[i-1][s] || a[i-1] == s);
                }       

            }
        }

        //print matrix
        print(m);

        return m[n][k];

    }

    private static void print(boolean[][] m){
        for(int i = 0; i < m.length; i++){
            for(int j = 0; j < m[i].length; j++){
                if(m[i][j]){
                    System.out.print("T");
                } else {
                    System.out.print("F");
                }           
            }
            System.out.print("n");
        }
    }

    public static void main(String[] args){
        int[] array = {1,3,5,2,8};
        int k = 9;

        System.out.println(subSetSum(array,k));

    }
}

Para construir la matriz m toma O ((n + 1) (k + 1)) que es O (nk). parece que debería ser polinomial, ¡pero no lo es! En realidad, es un pseudo polinomio. Leer sobre esto aquí

Nuevamente, esto solo funciona si la entrada solo contiene números positivos. Sin embargo, puede modificarlo fácilmente para que funcione con números negativos. La matriz todavía tendría n + 1 filas pero B - A + 1 columnas. Dónde B es el límite superior y A es el límite inferior (+1 para incluir cero) .La matriz aún sería Tendría que compensar s con el límite inferior.

Es bastante difícil explicar el problema de DP sobre el texto de principio a fin. Pero espero que esto ayude a aquellos que intentan comprender este problema.

Tenga en cuenta que en los ejemplos anteriores, las filas de la tabla DP están ordenadas. Ese no tiene por qué ser el caso.

Aquí hay una tabla de DP para el caso de la pregunta, es decir, dado un conjunto de {5, 3, 11, 8, 2}. Por brevedad, he omitido los valores falsos.

┌─────────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐
│ (index) │  0   │  2   │  3   │  5   │  7   │  8   │  10  │  11  │  13  │  14  │  15  │  16  │
├─────────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│    0    │ true │      │      │      │      │      │      │      │      │      │      │      │
│    5    │ true │      │      │ true │      │      │      │      │      │      │      │      │
│    3    │ true │      │ true │ true │      │ true │      │      │      │      │      │      │
│    11   │ true │      │ true │ true │      │ true │      │ true │      │ true │      │ true │
│    8    │ true │      │ true │ true │      │ true │      │ true │ true │ true │      │ true │
│    2    │ true │ true │ true │ true │ true │ true │ true │ true │ true │ true │ true │ true │
└─────────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┘

A continuación se muestra una implementación en JavaScript que generará el conjunto de destino {5, 11}:

var subSetSum = function(input, sum) {

    let y = input.length;
    let x = sum;

    if(input.length === 0) return 0;

    let d = [];

    //fill the rows
    for (let i = 0; i <= y; i++) {
      d[i] = [];
      d[i][0] = true;
    }
    
    for (let j = 1; j <= y; j++) { //j row
      for (let i = 1; i <= x; i++) { //i column
      let num = input[j-1];
        if(num === i) {
          d[j][i] = true;
        } else if(d[j-1][i]) {
          d[j][i] = true;
        } else if (d[j-1][i-num]) {
          d[j][i] = true;
        }
      }
    }
    
    //console.table(d); //uncomment to see the table
    if(!d[y][x]) return null;

    let searchedSet = [];
    for(let j=input.length, i=sum; j>0 && i != 0; j--) {
      if(input[j-1] !== i) {
        while(d[j-1][i]) { // go up
          j--;
        }
      }
      searchedSet.push(input[j-1]);
      i = i-input[j-1];
    }

    return searchedSet;
};

console.log('searched set:'+ JSON.stringify(subSetSum([5, 3, 11, 8, 2], 16)));

Como parece que todos sus números son positivos, puede resolver esto usando programación dinámica:

Comenzará una matriz booleana possible de tamaño K + 1 con el primer valor verdadero, el resto falso. El i-ésimo valor representará si es posible lograr un subconjunto de i. Para cada número n en su conjunto, recorra el possible matriz y si el i-ésimo valor es verdadero, entonces establezca el i + n-ésimo valor en verdadero también.

Al final, si el k-ésimo valor en possible es verdadero, entonces puede formar un subconjunto de k. Problema resuelto en tiempo O (NK).

La página de Wikipedia sobre el problema de la suma de subconjuntos tiene una explicación detallada de este algoritmo aplicado a conjuntos de números enteros que no se garantiza que sean positivos.

Sugeriría leer el algoritmo de Wiki. El algoritmo existe allí, ver Solución de programación dinámica de tiempo pseudopolinomial Para el O(P*n) solución, La solución no es polinomio en tiempo, es polinomio en (p, n) pero no es polinomio en n + log P (tamaño de entrada) y porque P puede ser muy grande como 2 ^ n, la solución P * n = (2 ^ n) * n no es una solución de tiempo polinomial en general, pero cuando p está limitado por alguna función polinomial de n es un algoritmo de tiempo polinomial.

Este problema es NPC, pero hay un Pseudo polynomial timealgoritmo para ello, y pertenece a weakly NP-Complete problemas, también hay Strongly NP-Complete problemas, lo que significa que no puede encontrar ningún pseudo polynomial time algoritmo para ellos a menos que P = NP, y este problema no está en este rango de problemas, por lo que de alguna manera es fácil.

Dije esto de la manera más simple posible, pero no es una definición exacta de un problema Muy NP-Completo o Débilmente NP-Completo.

Para obtener más detalles, consulte el capítulo 4 de Garey y Johnson.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)

Tags : / / /

Utiliza Nuestro Buscador

Preguntas Relacionadas:

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *