El problema subconjuntos de suma y la solvencia de los problemas NP-completos

Question

Yo estaba leyendo sobre el problema subconjunto sumas cuando vine con lo que parece ser un algoritmo de propósito general para resolverlo:

(defun subset-contains-sum (set sum)
    (let ((subsets) (new-subset) (new-sum))
        (dolist (element set)
            (dolist (subset-sum subsets)
                (setf new-subset (cons element (car subset-sum)))
                (setf new-sum (+ element (cdr subset-sum)))
                (if (= new-sum sum)
                    (return-from subset-contains-sum new-subset))
                (setf subsets (cons (cons new-subset new-sum) subsets)))
            (setf subsets (cons (cons element element) subsets)))))

"juego" es una lista no contiene duplicados y "suma" es la suma de buscar subconjuntos para. "Subgrupos" es una lista de las cons cells, donde el "coche" es una lista subconjunto y el "CDR" es la suma de ese subconjunto. Nuevos subconjuntos se crean a partir de los antiguos en O (1) tiempo con sólo cons'ing el elemento a la parte delantera.

No estoy seguro de lo que la complejidad de ejecución de la misma es, pero parece que con cada "suma" elemento Crece, el tamaño de "subgrupos" dobles, más uno, por lo que me parece que al menos sea cuadrática.

Estoy publicar esto porque mi impresión antes era que los problemas NP-completos tienden a ser intratable y que la mejor por lo general se puede esperar es una heurística, pero esto parece ser una solución de propósito general que voluntad, suponiendo que tiene los ciclos de CPU, siempre te dan la respuesta correcta. ¿Cuántos otros problemas NP-completos se pueden resolver como éste?

Answer 1

Todos los problemas NP-completos tienen soluciones. Mientras usted está dispuesto a gastar el tiempo para calcular la respuesta, es decir. El hecho de que no hay un eficiente algoritmo, no quiere decir que no es uno. Por ejemplo, usted podría iterar sobre cada posible solución, y que finalmente va a conseguir uno. Estos problemas se utilizan por todo el lugar en la computación en el mundo real. Sólo tiene que tener cuidado acerca de cómo un problema de una gran configura por sí mismo si va a necesitar tiempo exponencial (o peor!) Para resolverlo.

Answer 2

problemas NP-completos tienen solución, pero no en tiempo polinómico (por lo que sabemos). Es decir, un problema NP-completo puede tener un algoritmo O(n*2^n) que podría resolverlo, pero no va a tener, por ejemplo, un algoritmo O(n^3) para resolverlo.

Es interesante que, si se encontró un (polinomio) el algoritmo rápido para cualquier problema NP-completo, entonces todos los problemas de NP podría ser resuelto en tiempo polinómico. Esto es lo que P = NP se trata.

Si entiendo correctamente su algoritmo (y esto se basa más en sus comentarios que en el código), entonces es equivalente al algoritmo O(n*2^n) aquí . Hay subconjuntos 2^n, y dado que también es necesario para resumir cada subconjunto, el algoritmo es O(n*2^n).

Una cosa más sobre la complejidad - la O(whatever) sólo indica la eficacia de un algoritmo particular escalas. No se puede comparar dos algoritmos y decir que uno es más rápido que el otro basado en esto. notación Big-O no se preocupa por los detalles de implementación y optimizaciones - es posible escribir dos implementaciones del mismo algoritmo con uno de ellos mucho más rápido que el otro, a pesar de que podrían ser tanto O(n^2). Una mujer que hace los bebés es una operación O(n), pero lo más probable es que esto va a tomar mucho más tiempo que la mayoría de las clases O(n*log(n)) que realiza. Todo lo que podemos decir sobre la base de esto es que la clasificación será más lenta para valores muy grandes de n.

Answer 3

  

No estoy seguro de lo que el tiempo de ejecución   complejidad de la que es, pero parece que   con cada elemento de "suma" crece, la   tamaño de dobles "subconjuntos", más uno,   por lo que me parece ser, al menos,   cuadrática.

Si el dobles en tiempo de ejecución para cada aumento de N, lo que buscas en un O (2 ^ n) algoritmo. Eso es también lo que cabe esperar de visitar todos los subconjuntos de un conjunto (o todos los miembros de la powerset de un conjunto), ya que eso es exactamente 2 ^ n miembros (si se incluye conjunto vacío RHE).

El hecho de que la adición o no adición de un elemento a todos los conjuntos hasta ahora visto-se rápido no significa que el total de procesamiento es rápida.

Answer 4

Lo que está pasando aquí podría expresarse mucho más simple uso de la recursividad:

(defun subset-sum (set sum &optional subset)
  (when set
    (destructuring-bind (head . tail) set
      (or (and (= head sum) (cons head subset))
          (subset-sum tail sum          subset)
          (subset-sum tail (- sum head) (cons head subset))))))

Los dos llamadas recursivas al final muestran claramente que estamos atravesando un árbol binario de profundidad n, el tamaño del conjunto dado. El número de nodos en el árbol binario es O (2 ^ n), como se esperaba.

Answer 5

Es karpreducible a tiempo polinómico. Reducir con la reducción de Karp a un O problema de decisión (nM) utilizando un montón o binarios de búsqueda límites superiores es log (M * 2 ^ M) = logM + log (2 ^ M) = logM + Mlog2 Tiempo Ergo: O (nM)