Il problema sottoinsiemi somma e la solvibilità dei problemi NP-completi

Question

Stavo leggendo sul problema sottoinsieme somme quando mi si avvicinò con quello che sembra essere un algoritmo generale per risolverlo:

(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)))))

"set" è un elenco che non contiene duplicati e "somma" è la somma di sottoinsiemi cercare. "Sottoinsiemi" è un elenco di celle cons, dove la "macchina" è una lista sottoinsieme e la "cdr" è la somma di quel sottoinsieme. Nuovi sottoinsiemi sono creati da quelli vecchi in O (1) tempo semplicemente cons'ing l'elemento verso la parte anteriore.

Non sono sicuro di quello che la complessità di esecuzione di esso è, ma sembra che con ogni elemento "somma" cresce, la dimensione di "sottoinsiemi" raddoppia, più uno, per cui mi sembra almeno essere quadratica.

Sto inviando questo perché la mia impressione prima era che i problemi NP-completi tendono ad essere intrattabile e che il meglio che si può normalmente sperare è un'euristica, ma questo sembra essere una soluzione general-purpose che sarà, a patto di avere i cicli di CPU, sempre dare la risposta corretta. Quanti altri problemi NP-completi possono essere risolti come questo?

Answer 1

Tutti i problemi NP-completi hanno soluzioni. Finché siete disposti a spendere il tempo per calcolare la risposta, che è. Solo perché non c'è un efficace algoritmo, non significa che non v'è uno. Ad esempio, si può solo scorrere su ogni possibile soluzione, e sarete finalmente ottenere uno. Questi problemi sono utilizzati in tutto il luogo in informatica del mondo reale. Hai solo bisogno di stare attenti a come un grosso problema di impostare da sé se si sta andando ad avere bisogno di tempo esponenziale (o peggio!) Per risolverlo.

Answer 2

problemi NP-completi sono risolvibili, non solo in tempo polinomiale (per quanto ne sappiamo). Che è, un problema NP-completo può avere un algoritmo O(n*2^n) che potrebbe risolvere, ma non avrà, per esempio, un algoritmo O(n^3) per risolverlo.

È interessante notare che, se un rapido (polinomiale) algoritmo è stato trovato per qualsiasi problema NP-completo, allora ogni problema in NP potrebbe essere risolto in tempo polinomiale. Questo è ciò che P = NP è di circa.

Se ho capito l'algoritmo in modo corretto (e questo si basa più sui vostri commenti che sul codice), allora è equivalente all'algoritmo O(n*2^n) qui . Ci sono sottoinsiemi 2^n, e dal momento che è anche necessario riassumere ogni sottoinsieme, l'algoritmo è O(n*2^n).

Una cosa di più sulla complessità - l'O(whatever) indica solo quanto bene un particolare algoritmo di scale. Non si può paragonare due algoritmi e dire che uno è più veloce rispetto agli altri sulla base di questo. Notazione O-grande non si cura di dettagli di implementazione e ottimizzazione - è possibile scrivere due implementazioni dello stesso algoritmo con un essere molto più veloce rispetto agli altri, anche se potrebbero entrambi essere O(n^2). Una donna che fa i bambini è un'operazione O(n), ma le probabilità sono che questo sta andando a prendere molto più a lungo rispetto alla maggior parte tipi O(n*log(n)) eseguite. Tutto quello che posso dire sulla base di questo è che l'ordinamento sarà più lento per molto grandi valori sul n.

Answer 3

  

Non sono sicuro di ciò che il tempo di esecuzione   la complessità di esso è, ma sembra che   ciascun elemento "somma" cresce, la   dimensione del doppi "sottoinsiemi", più uno,   così mi sembra almeno essere   quadratica.

Se il runtime raddoppia per ogni aumento di N, si sta guardando un O (2 ^ N) algoritmo. Questo è anche quello che mi aspetto da visitare tutti i sottoinsiemi di un insieme (o tutti i membri del Powerset di un set), in quanto questo è esattamente 2 ^ N membri (se si include rhe insieme vuoto).

Il fatto che l'aggiunta o meno aggiunta di un elemento a tutti i set-finora visto è veloce non significa che il trattamento totale è veloce.

Answer 4

Che cosa sta succedendo qui potrebbe essere espressa molto più semplicemente utilizzando la ricorsione:

(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))))))

I due chiamate ricorsive alla fine mostrano chiaramente stiamo attraversano un albero binario di profondità n, la dimensione del set indicato. Il numero di nodi dell'albero binario è O (2 ^ n), come previsto.

Answer 5

E 'karpreducible a tempo polinomiale. Ridurre con riduzione di Karp a un problema decisionale O (nm) utilizzando un cumulo o binari di ricerca limiti superiori è log (M * 2 ^ M) = LOGM + log (2 ^ M) = LOGM + Mlog2 Ergo Tempo: O (nm)