Algoritmo di programmazione orario studente

Question

Ho bisogno di trovare un algoritmo per trovare il momento migliore per incontrarci, diciamo un gruppo di studio. Il sistema contiene informazioni su un gruppo di studenti e i loro programmi di classe. Il sistema dovrebbe dare un tempo per il meetup, in cui non vi è alcun conflitto con gli orari delle classi di nessuno. quale sarebbe il modo migliore per attaccare questo problema. Stavo cercando qualsiasi algoritmo di pianificazione, ma non ho trovato nessuno adatto.

grazie in anticipo

Answer 1

Come mi ricordo le migliori soluzioni per questo problema sono soluzioni generate da algoritmi genetici

vedere questo link http://www.codeproject.com/KB/recipes/GaClassSchedule.aspx

Answer 2

Domanda interessante.

Questo è quello che vorrei fare:

1. In primo luogo, allineare tutti timescheduals, per tutti gli studenti (ad esempio a partire dal lunedì, ogni giorno diviso per 24 ore). È possibile utilizzare un valore booleano o un intero per ciascun periodo e memorizzarli in un array.
2. Quindi eseguire un'operazione di aggiunta su tutti i programmi insieme.

Che poi si presenta così, per esempio:

Student A: 11100000111111100000 
Student B: 00000011111000010001 
Student C: 00000000111111110001 
_______________________________+ 
      11100022333222220002 
       ^^^   ^^^ 

Allora avresti bisogno di trovare tutte le lacune nella matrice (aree con zeri) utilizzando un semplice ciclo che tiene traccia della corrente lunghezza zero. Memorizza l'indice di inizio e di fine e lo traduce (al contrario del passaggio 1) in un'area temporale.

Answer 3

questo è un problema di corrispondenza e può essere risolvere con maximum flow algorithm

ogni gruppo di studenti e di studio è un nodo su un grafico direzionale e ingresso per ogni studente ha un'unità di flusso in ingresso ed è collegato a tutti i gruppi di studio nodo. ciascun gruppo di nodi di studio ha capacità di produzione illimitata, quando il flusso nella rete è massima avete la vostra corretta combinazione

vedi anche Introduction to Algorithms (reti di flusso capitolo)

Answer 4

ci sono 24*60 = 1440 minuti al giorno. Così si potrebbe facilmente la forza bruta che, dal momento che non c'è bisogno di ottenere più di una precisione di basi minuto. Comunque descriverò un semplice DP.

È possibile creare un array booleano che memorizza se quel minuto ha una classe in esso da uno degli studenti del gruppo. Hai anche un secondo array. Questa matrice memorizza il numero di spazi aperti in questo blocco ea sinistra. Che cosa si può fare è di traslazione l'array booleano da destra a sinistra e se il blocco ha una classe in esso si fare il numero 0, altrimenti si rendono 1 più il numero nel minuto precedente.

Tuttavia, sento che la mia spiegazione manca, ecco pseudo codice:

blocked = <boolean array>; 
numtoleft = <array containing the counts>; 
if blocked[0]: 
    numtoleft[0] = 0; 
else: 
    numtoleft[0] = 1; 

for i = 1 to 1440-1: 
    if blocked[i]: 
     numtoleft[i] = 0; 
    else: 
     numtoleft[i] = numtoleft[i-1]; 

allora si può facilmente trovare la più grande slot aperto, trovando il numero massimo nella matrice 'numtoleft' e si può aggiungere restrizioni ai tempi che si sta guardando.

EDIT:

Ecco l'algoritmo in Python:

def largestslot(blocked, startminute, endminute): 
    numtoleft = [0]*1440 
    numtoleft[startminute] = 0 if blocked[startminute] else 1 
    for i in xrange(startminute+1, endminute+1): 
     numtoleft[i] = 0 if blocked[i] else 1 
    ansmax = max(numtoleft[startminute:endminute+1) 
    ansi = numtoleft.index(ansmax) 
    return (ansi-ansmax, ansi) 

Answer 5

Vorrei iniziare con un approccio molto semplice a questo:

• sorta tutte in programma blocchi di tempo di tutti i membri della raggruppare in una lista, ordinata per l'ora di inizio di un blocco
• passare l'elenco e unire elementi adiacenti, se si sovrappongono (endTime di n è maggiore di un'ora di inizio di n + 1)

Ora l'elenco contiene blocchi temporali in cui tutti i membri del gruppo hanno altre attività. Quindi è necessario controllare l'elenco per le fasce orarie libere e controllare, se lo slot è abbastanza grande per la riunione desiderata.

Answer 6

Ogni studente ha una gamma di ore disponibili. E tutti devono incontrarsi (il che significa che c'è almeno un'ora in cui sono tutti gratuiti). Devi semplicemente iniziare con il primo studente e intersecare il suo intervallo di ore disponibili con il prossimo studente e farlo (continuando a restringere l'intervallo originale) per ogni studente e dovresti lasciare un intervallo adatto a ogni studente.

Answer 7

Avrei impostato una durata per la riunione e un intervallo di tempo valido durante la riunione, ovvero 45 minuti di durata a partire dalle 8:00 ma non dopo le 21:30. Quindi dovrebbe essere sufficiente intersecare il tempo libero del membro del gruppo e trovare un blocco adatto. Ti consigliamo di includere tolleranze per la sovrapposizione, ad esempio se il 75% del gruppo può incontrarsi, allora è fattibile.

Si potrebbe anche voler includere i buffer per le ore di inizio/fine per consentire il viaggio, ecc. E includere quei buffer nei criteri di ricerca. L'unica cosa che odio della maggior parte degli incontri è che non prendono in considerazione i tempi di viaggio e di configurazione e prenotano invece una riunione una sopra l'altra.