Algoritmo per il calcolo delle restrizioni date dal calendario

Question

Sto considerando un problema ipotetico e sto cercando una guida su come affrontare il problema, da un punto di vista algoritmico.

Il problema:

consideri un'università. Si hanno i seguenti oggetti:

• Docente. Ogni membro del personale insegna uno o più documenti.
• Studenti. Ogni studente prende uno o più documenti.
• Camere. Le stanze contengono un certo numero di studenti e contengono determinati tipi di attrezzature.
• Carte. Richiedere un determinato tipo di attrezzatura e una certa quantità di tempo ogni settimana.

informazioni fornite circa le iscrizioni (IE- quanti studenti sono iscritti in ogni carta, e ciò che il personale sono assegnati per insegnare ogni carta), come posso calcolare un calendario che obbedisce alle seguenti restrizioni:

1. Il personale può insegnare solo una cosa alla volta.
2. Gli studenti possono solo partecipare a un foglio alla volta.
3. Le camere possono contenere solo un determinato numero di studenti.
4. Le carte che richiedono un determinato tipo di apparecchiatura possono essere trattenute solo in una stanza che fornisce quel tipo di apparecchiatura.
5. Ore di funzionamento dal lunedì al venerdì, 8-12 e 1-5.

Discussione:

In realtà io non sono troppo interessati con la situazione descritta sopra - è la classe generale di problema che mi incuriosisce. A prima vista Mi sembra una buona misura per un algoritmo genetico, ma la funzione di fitness per un tale algoritmo sarebbe incredibilmente complessa.

Qual è un buon approccio per cercare di risolvere questo tipo di problema che soddisfa i vincoli?

Immagino che probabilmente non c'è alcun modo per risolvere questo perfettamente, dal momento che gli studenti possono anche prendere una combinazione di documenti che porta a situazioni impossibili, in particolare come cresce il numero di studenti & documenti.

Answer 1

Stando agli algoritmi genetici, non credo che la funzione di fitness per questo sarebbe molto complessa, al contrario.

Fondamentalmente basta controllare la soluzione candidata (qualunque sia la codifica) per ciascuno dei vincoli (ne hai solo 5) e assegnargli un peso in modo che quando un vincolo non sia soddisfatto il peso viene aggiunto a un punteggio totale che potrebbe rappresentare fitness

In uno scenario di questo tipo, è sufficiente ridurre al minimo la funzione di fitness (poiché la migliore forma fisica possibile è 0, ovvero tutti i vincoli sono soddisfatti) e lasciare che GA riduca i numeri.

La codifica vorrà un po 'di capire, ma una volta fatto dovrebbe essere semplice, a meno che non mi manca qualcosa, ovviamente :)

Answer 2

Una versione molto limitata di questo problema è NP-Complete.

Considerare il caso in cui esattamente uno studente può prendere un foglio.

Ora per un determinato intervallo di tempo (ad esempio, il foglio viene insegnato tutto il giorno), è possibile costruire un grafico a 3 partizioni, con stanze, documenti e studenti, con un margine tra un foglio e uno studente se lo studente lo desidera prendilo. Aggiungi anche i bordi tra una carta e le stanze possibili.

Ora vediamo che 3 Dimensional matching problem è un'istanza del tuo problema: devi scegliere una combinazione non sovrapponibile (studente, carta, stanza) per quel particolare periodo di tempo.

Probabilmente stai meglio con alcune euristiche per il problema generale. Scusa, non posso aiutarti lì.

Spero che questo aiuti.