Sono tutti problemi di programmazione NP-Hard?

Question

So che ci sono alcuni problemi di programmazione là fuori che sono NP-hard/NP-completo ...tuttavia, nessuno di loro ha dichiarato in modo tale da mostrare questa situazione è anche NP.

Se si dispone di un set di attività vincolata ad un startAfter, startBy, e durata tutti cercando di utilizzare un singola risorsa ...si può risolvere un palinsesto o di identificare che non può essere risolto senza una ricerca esaustiva?

Se la risposta è "mi dispiace, pal, ma questo è NP-completo" che cosa sarebbe la migliore euristica(s?) da usare e ci sono modi per ridurre il tempo necessario per a) risolvere una pianificazione e b) individuare un irrisolvibile pianificazione.

Ho implementato (prolog) un programma di base di risoluzione dei conflitti obiettivo attraverso la ricorsione che implementa una "più piccola della finestra" euristico.Questo in realtà si trova soluzioni piuttosto rapidamente, ma è estremamente lento a trovare valido orari.C'è un modo per superare questo?

Yay per il composto di domande!

Answer 1

La parte più dura della maggior parte dei problemi di programmazione in la vita reale è entrare in possesso di una affidabilità e set completo di vincoli.Se prendiamo l'esempio di creazione di una università di orario:

• Professore A non alzarsi la mattina, fa un sacco di commissioni, ma nessuno potrà dire che il calendario di office su questo tipo di vincolo
• Dipartimento 1 esigenze di orario per l'inizio del termine, tuttavia, Dipartimento 2 che utilizza lo stesso camere è disposto a decidere sui corsi che verrà eseguito fino a quando tutti gli studenti sono arrivati
• Ecc

Allora avete bisogno di una pianificazione di sistema in grado di far fronte con i cambiamenti, in modo che quando un vincolo è cambiato all'ultimo minuto non è necessario modificare l'orario completo.

Tutto quanto sopra è normalmente ignorato nei documenti di ricerca su sistemi di programmazione.Come per NP completezza di un dato problema di programmazione, in la vita reale non si cura anche se non è NP completo è improbabile anche essere in grado di definire che cosa è la “soluzione migliore” è, quindi, abbastanza buono è abbastanza buono.

Vedere http://www.asap.cs.nott.ac.uk/watt/resources/university.html per un elenco dei documenti che possono aiutare a iniziare;ci sono ancora molti Dottori di ricerca nel software di programmazione.

Answer 2

Ci sono spesso buone algoritmi di approssimazione per NP-hard/completa ottimizzazione di problemi come la pianificazione.Si potrebbe scremare il corso note di Ahmed Abu Safia su Algoritmi di approssimazione per la pianificazione o varie articoli.

In un certo senso, tutta la crittografia a chiave pubblica è fatto con "meno rigido" in problemi come il factoring, in parte perché NP-hard problemi di offrire troppi casi più semplici.E ' lo stesso di NP-completezza che li rende "moralmente difficile", che dà loro anche troppe facili problemi, che spesso cadono nello stesso errore associato ottimale.

C'è una profonda teoria di la durezza di approssimazione che discute i limiti di algoritmi di approssimazione, però.

Answer 3

È possibile utilizzare la programmazione dinamica per risolvere alcune di queste cose.Gli algoritmi generici vengono alla mente.Pianificazione teoria è una profonda e bella, ma quei due mi è trovare la volontà di risolvere la maggior parte dei problemi che ho dovuto affrontare.Forse sono stato fortunato.

Answer 4

Cosa vuoi dire con startBy?

Con startAfter e se c'è solo una risorsa, poi una veloce soluzione potrebbe essere utilizzare ordinamento topologico.L'esempio di algoritmo viene eseguito in un tempo lineare, ma non include il caso di errore se il grafo non contiene cicli.

Answer 5

Ecco uno che non lo è.

Pianificazione di una serie di lavori i= 1,2...n una singola macchina, che ogni prendere tempo t(i) in modo che il tempo medio di attesa è ridotto al minimo.

Soluzione:Ordinare in ordine crescente di t(i).O(n log n)

Buona lista qui

Answer 6

Si consideri il problema di programmazione che è in classe P:

Ingresso:elenco di attività che includono l'ora di inizio e ora di fine.

Ordina per ora di fine.

Selezionare i primi N elementi di questo elenco ordinato per trovare la massima quantità di attività che è possibile pianificare in un dato periodo di tempo.

È possibile aggiungere avvertenze come:tutte le attività devono terminare alle 5 del pomeriggio, beh, in questo caso, come si lavora attraverso la lista, una volta raggiunta un'attività che termina dopo questo tempo.