Relazionare i problemi NP-Complete ai problemi del mondo reale

Question

Ho una buona conoscenza dei problemi NP Complete; non è questo il problema Quello che non ho è un buon senso di dove si presentano nella programmazione "reale". Alcuni (come lo zaino e il venditore ambulante) sono ovvi, ma altri non sembrano ovviamente collegati a problemi "reali".

Ho avuto diverse volte l'esperienza di dover lottare con un problema difficile solo per rendermi conto che si tratta di un noto problema NP Complete che è stato oggetto di ricerche approfondite. Se avessi riconosciuto più rapidamente la connessione, avrei potuto risparmiare un po 'di tempo nella ricerca di soluzioni esistenti per il mio problema specifico.

Esistono risorse (online o di stampa) che collegano in modo specifico NP Complete alle istanze del mondo reale?

Modifica: Modifica: Ad esempio, stavo lavorando a un programma che ha cercato di dividere gli studenti in gruppi in base all'età, al grado e alla scuola di origine, che è essenzialmente un problema di partizionamento del grafico. Mi ci è voluto un po 'per realizzare la connessione.

Answer 1

Ho trovato che Computers and Intractability è il riferimento definitivo su questo argomento.

Answer 2

Di solito la connessione che si sta parlando deve essere estratto con un cosiddetto riduzione, ad esempio, si riducono 3-SAT al problema si sta lavorando e quindi si può concludere che il problema ha la stessa complessità di esso.

Questo passaggio non è banale, poiché è necessario dimostrare che si può trasformare ogni istanza problema l di un noto NP-Hard problema L in un'istanza c del problema C utilizzando un algoritmo deterministico polinomiale.

Quindi, se non da imparare correlazioni basical di comuni problemi NP-rigidi utilizzando la memoria, non c'è modo per essere sicuri che se un problema è simile ad un altro NP-Hard senza prima cercare di indovinare e poi dimostrarlo , devi essere intelligente.

Answer 3

Ecco un link wiki: http://wapedia.mobi/en/List_of_NP-complete_problems Avviso dice

Questo elenco non è in alcun modo completo (ci sono più di 3000 note problemi NP-completi)

probabilmente sarebbe essere un grande compito se qualcuno potesse compilare tale lista.

Un teorico dovrebbe cercare di capire/provare un problema NP-Completo/Difficile. Ma un programmatore non ha tempo per farlo. Ha bisogno di una lista.

Sono corretto?

Penso che si dovrebbe google. E, leggi tutti i link. Aggiungi a qualsiasi nuovo problema trovato nel link alla tua lista.

Speranza che aiuta

PS: Non dimenticate di inviare la lista quando hai finito: P

Answer 4

Per sviluppare meglio l'intuizione del libro "Manuale L'algoritmo Design, Second Edition" di Skiena (estratti su Google books) è semplicemente fantastico.

1. List nella parte posteriore con problemi (compresi i problemi duri), che includono un'illustrazione ed una discussione (spesso) con una mondo reale esempio.
2. Copre sia il teorico e il lato pratico delle cose, spesso parlando di codice effettivo.

Leggi excepts online qui (vedi alcuni esempi in capitoli 14): http://books.google.dk/books?id=7XUSn0IKQEgC&printsec=frontcover#v=onepage&q&f=false

capitolo 16 (non in linea) discute alcuni problemi difficili, tra cui partizione grafico.