Possibile problema NP-completo?

Question

Vorrei solo che qualcuno verificasse se il seguente problema è NP-completo o se esiste effettivamente una soluzione migliore/più semplice rispetto al semplice controllo combinato di forza bruta.

Abbiamo una sorta di problema di allocazione delle risorse nel nostro software e lo spiegherò con un esempio.

Diciamo che abbiamo bisogno che 4 persone siano al lavoro durante il turno di giorno.Questo numero e il fatto che si tratti di un "turno diurno" sono registrati nel nostro database.

Tuttavia, non chiediamo a chiunque di occupare questi posti, ci sono alcuni requisiti che devono essere soddisfatti per soddisfare il conto.

Di questi 4, diciamo che 2 devono essere infermiere e 1 deve essere medico.

Uno dei medici deve anche lavorare come parte di una squadra particolare.

Quindi abbiamo questo insieme di informazioni:

Turno diurno:4
1 dottore
1 medico, deve lavorare nella squadra A
1 infermiera

Quanto sopra non è il problema.Il problema sorge quando iniziamo a scegliere le persone per lavorare nel turno di giorno e cerchiamo di capire se le persone che abbiamo scelto finora possono effettivamente soddisfare i criteri.

Ad esempio, supponiamo di scegliere James, John, Ursula e Mary per lavorare, dove James e Ursula sono medici, John e Mary sono infermieri.

Anche Ursula lavora nella squadra A.

Ora, a seconda dell'ordine in cui cerchiamo di adattare il conto, potremmo finire per dedurre che abbiamo le persone giuste oppure no, a meno che non iniziamo a provare combinazioni diverse.

Ad esempio, se scorri l'elenco e scegli prima Ursula, potremmo abbinarla al criterio "1 medico".Poi arriviamo a James e notiamo che poiché non lavora nella squadra A, gli altri criteri su "1 medico, deve lavorare nella squadra A" non possono essere soddisfatti con lui.Dato che le altre due persone sono infermiere, neanche loro soddisfano questi criteri.

Quindi torniamo sui nostri passi e proviamo prima James, e anche lui può soddisfare i primi criteri, e poi Ursula può soddisfare i criteri di cui ha bisogno quella squadra.

Quindi il problema ci appare perché dobbiamo provare diverse combinazioni finché non le abbiamo provate tutte, nel qual caso abbiamo alcuni criteri che non sono ancora stati soddisfatti, anche se il numero totale di teste funzionanti è lo stesso del totale numero di teste necessarie oppure abbiamo trovato una combinazione che funziona.

E' questa l'unica soluzione? Qualcuno riesce a trovarne una migliore?

---

Modificare:Qualche chiarimento.

I commenti a questa domanda menzionano che con così poche persone dovremmo usare la forza bruta, e sono d'accordo, questo è probabilmente quello che potremmo fare, e potremmo anche farlo, nella stessa corsia in cui alcune ottimizzazioni guardano alla dimensione di i dati e seleziona algoritmi di ordinamento diversi con un minor sovraccarico iniziale se la dimensione dei dati è piccola.

Il problema, però, è che questo fa parte di un sistema di pianificazione dei turni, in cui potresti coinvolgere un certo numero di persone, sia come "Abbiamo bisogno di X persone nel turno di giorno" sia come "Abbiamo questo gruppo di Y persone che lo farà", così come il potenziale per un ampio "Abbiamo questo elenco di criteri Z per quelle X persone che dovranno in qualche modo corrispondere a queste Y persone", e poi si aggiunge il fatto che avremo un certo numero di giorni per fare lo stesso calcolo, in tempo reale, mentre il leader aggiusta il roster, e poi è emersa la necessità di una soluzione rapida.

Fondamentalmente, il leader vedrà sullo schermo un'informazione sommaria in tempo reale che dice quante persone mancano ancora, sia nell'intero turno di giorno, sia quante persone soddisfano i vari criteri, e quante persone effettivamente ned in aggiunta a quelli che abbiamo.Questo display dovrà essere aggiornato in semi-live mentre il leader modifica il roster con "E se James prendesse il turno di giorno invece di Ursula, e Ursula prendesse il turno di notte".

Ma grazie mille alle persone che hanno risposto finora, il problema della soddisfazione dei vincoli sembra la strada da percorrere, ma qui esamineremo sicuramente tutti i collegamenti e i nomi degli algoritmi.

Questo è il motivo per cui adoro StackOverflow :)

Answer 1

Quello che hai c'è una vincolo problema soddisfazione ; la loro relazione a NP è interessante, perché sono in genere NP ma spesso non NP-completo, vale a dire che sono trattabili a soluzioni in tempo polinomiale.

Come Ebo notato nei commenti, la tua situazione suona come esso può essere formulato come un esatto problema della copertura , che è possibile applicare Algoritmo X di Knuth a. Se si prende questo tack, fatecelo sapere come funziona per voi.

Answer 2

Lo fa apparire come hai un vincolo problema soddisfazione .

Nel tuo caso avrei particolarmente guardo tecniche di propagazione di vincoli prime - si può essere in grado di ridurre il problema a una dimensione gestibile in quel modo.

Che cosa succede se nessuno soddisfa i criteri?

Answer 3

Quello che si sta descrivendo è il 'compagno di camera problema' è leggermente descritto in questa tesi .

Orso con me, io sono alla ricerca di collegamenti migliori.

Modifica

Ecco un altro tesi .

Answer 4

Per quanto mi riguarda avrei molto probabilmente cercando di trovare riduzione a grafo bipartito corrispondenza problema. Anche per dimostrare che problema è NP di solito è molto più complicato che stare non è possibile trovare una soluzione polinomiale.

Answer 5

Non sono sicuro che il vostro problema è NP, che non ha odore in quel modo, ma cosa avrei fatto se fossi voi sarebbe quella di ordinare i requisiti per le posizioni tali che si tenta di riempire il primo più specifica dal minor numero di persone sarà disponibile riempire queste posizioni, così si è meno probabilità di avere fare marcia indietro un sacco. Non v'è alcun motivo per cui non si dovrebbe combinare questo con l'algoritmo X, un algoritmo di pura Knuth-ness.

Answer 6

Lascio la teoria ad altri, dato che il mio buon senso matematico non è così grande, ma si possono trovare uno strumento come Cassowary / Cassowary.net o NSolver utile per rappresentare il vostro problema in modo dichiarativo come un problema di soddisfacimento di vincoli e quindi risolvere il vincoli.

In tali strumenti, il metodo simplex combinato con propagazione di vincoli viene spesso impiegato per ridurre lo spazio deterministico soluzione e quindi trovare una soluzione ottimale in una funzione di costo. Per gli spazi più grandi di soluzione (che non sembrano applicare nella dimensione del problema si specifica), vengono utilizzati algoritmi di tanto in tanto genetici.

Se non ricordo male, NSolver include anche nel codice di esempio una semplificazione di un problema reale Nurse-rostering che il dottor Chun ha lavorato ad Hong Kong. E c'è un documento sul lavoro che ha fatto.

Answer 7

Sembra a me come si dispone di un paio di problemi separabili che sarebbe molto più facile da risolvere:

- selezionare un medico della squadra A - selezionare un altro medico di qualsiasi squadra - selezionare due infermiere

In modo da avere tre problemi indipendenti.

Una precisazione, però, fare bisogna avere due medici (uno dal team specificato) e due infermiere, o un medico del team specificato, due infermieri e un altro che possono essere sia medico o l'infermiere?

Answer 8

Alcune domande:

1. E 'l'obiettivo di soddisfare i vincoli esattamente , oppure solo di circa (ma per quanto possibile)?
2. Può una persona essere un membro di diverse squadre?
3. Quali sono tutti i possibili vincoli? (Per esempio, potremmo avere bisogno di un medico, che è membro di diverse squadre?)

Se si vuole soddisfare i vincoli esattamente , quindi vorrei ordinare i vincoli sempre meno di rigore, vale a dire, quelli che sono i più difficili da raggiungere (ad esempio, medico e la squadra A nel tuo esempio sopra ) devono essere controllati prima

Se si vuole soddisfare i vincoli di circa , quindi è una storia diversa ... si dovrà indicare un qualche tipo di ponderazione / dell'importanza-funzione che determina ciò che piuttosto avremmo, quando abbiamo non può corrispondere esattamente, e hanno diverse possibilità tra cui scegliere.

Answer 9

Se hai diversi o molti vincoli, dai un'occhiata a Pianificatore di sbavature (open source, Java).

Forza bruta, ramificato e legato e tecniche simili richiedono troppo tempo.Algoritmi deterministici come riempire prima i turni più grandi sono molto subottimali.Le metaeuristiche sono un ottimo modo per affrontare questo problema.

Dai uno sguardo specifico all'esempio di elenco degli infermieri nel mondo reale di Drools Planner.È facile aggiungere molti vincoli, come "le giovani infermiere non vogliono lavorare il sabato sera" o "alcune infermiere non vogliono lavorare per molti giorni di seguito".