fabioz96
22-08-2017, 01:19
Salve, sto scrivendo un programma che calcola in modo esaustivo tutte le possibili combinazioni di un orario scolastico usando il BackTracking.
Ho 10 classi scolastiche (mi riferisco alle classi degl studenti e non a quelle di java):
public enum Classe{ IA, IIA, IIIA, IB, IIB, IIIB, IC, IIC, IIIC, IID };
e ho anche 24 Docenti.
Un Docente è un oggetto con: Nome, Materi, Giorno Libero e una Mappa che contiene le coppie <Classe, Ore in questa classe>.
Il mio orario viene rappresentato in questo modo: 28755
Dove G.L. e F.S. rappresentano le ore in cui non possono essere assegnati i docenti.
Uso un BackTracking Iterativo per riempiere l'orario rappresentato da una matrice di costanti Classe (IA, IIA ecc).
Ogni colonna rappresenta la 1, 2, 3, 4 e 5 ora di una giornata. Nelle righe ci sono i docenti.
Il programma riempie una colonna alla volta quando il docente della riga ha ore nella classe attuale e quando il giorno corrispondente a quella colonna, non è il giorno libero.
Quando raggiunge l'ultima ora di sabato, ripete lo stesso procedimento per la classe successiva.
Questo programma prova tutte le combinazioni.
Il problema in questione ha complessità esponenziale, ma esistono altri programmi che risolvono questo problema in tempi ragionevoli. Il mio problema sembra molto simile al calcolo combinatorio dove la dimensione dell'input è abbastanza alto. Se esiste un algoritmo che risolve problemi combinatori in tempi ragionevoli, potrei adattarlo.
Sapete indicarmi una soluzioni più efficiente? Come posso ridurre il tempo di calcolo?
Questo è il codice della parte del BackTracking:
public void trovaCombinazioniOrario(){
int liv = 0;
boolean rivedi = false;
ArrayList<Classe> arrayClasse = new ArrayList<>( Arrays.asList( Classe.values() ) );
int nClasseAttuale = 0;
if( arrayClasse.isEmpty() ){ System.err.println("Non c'è nessuna classe da assegnare!"); System.exit(-1); }
Classe classe = arrayClasse.get(nClasseAttuale); //Prendo la prima classe
if ( !primaScelta( classe, liv) ){ //Innanzitutto faccio una prima scelta
System.err.println("Non c'è nemmeno la prima scelta per la classe "+classe);
return;
}//if
//TODO
while (liv >= -1){
// System.out.println("La classe attuale è "+classe+ " al livello "+liv);
System.out.println(this);
if( solCompleta(liv) ){ //Se il livello è l'ultimo,
/**Ho sistemato una classe e vedo la successiva*/
if( arrayClasse.size()-1 > nClasseAttuale ){ //C'è una prossima classe
nClasseAttuale++;
classe = arrayClasse.get( nClasseAttuale ); //prendo la prossima
liv = -1; //assegno la prossima classe a partire dal liv -1 (dopo fa l'incremento)
rivedi = false; //devo andare avanti e non rivedere
} else { //Non c'è una prossima classe, era l'ultima
filtraEStampa(); //filtra l'orario e lo stampa
rivedi = true; //provo altre combinazioni
liv++;
}//if lit
}else{
liv++; //Oppure incremento il livello
if( !primaScelta( classe, liv) ) //e faccio la prima scelta del livello successivo
rivedi= true; //se non va bene devo rivedere
}//else
while( rivedi && liv >= 0){ //finché non va bene
liv--; //torno indietro di livello
if( liv == -1 ){
/**Non ho soluzioni andando avanti e provo a modificare una classe precedente*/
if( nClasseAttuale > 0 ){ //C'è una classe precendente e devo riprovare
nClasseAttuale--;
classe = arrayClasse.get(nClasseAttuale);
liv = GIORNI_SETTIMANA * ORE_GIORNO -1; //riprovo a partire dall'ultimo livello della classe precedente
} else{ //Non c'è una classe precedente
System.out.println("Ho terminato le combinazioni");
return; //Non c'è nessuna scelta possibile
}//if lit
}//if -1
if( successivaScelta(classe, liv) ) //faccio la scelta successiva
rivedi= false; //se va bene, non devo più rivedere
}//while
}//while
}//assegnaClasse
Ho 10 classi scolastiche (mi riferisco alle classi degl studenti e non a quelle di java):
public enum Classe{ IA, IIA, IIIA, IB, IIB, IIIB, IC, IIC, IIIC, IID };
e ho anche 24 Docenti.
Un Docente è un oggetto con: Nome, Materi, Giorno Libero e una Mappa che contiene le coppie <Classe, Ore in questa classe>.
Il mio orario viene rappresentato in questo modo: 28755
Dove G.L. e F.S. rappresentano le ore in cui non possono essere assegnati i docenti.
Uso un BackTracking Iterativo per riempiere l'orario rappresentato da una matrice di costanti Classe (IA, IIA ecc).
Ogni colonna rappresenta la 1, 2, 3, 4 e 5 ora di una giornata. Nelle righe ci sono i docenti.
Il programma riempie una colonna alla volta quando il docente della riga ha ore nella classe attuale e quando il giorno corrispondente a quella colonna, non è il giorno libero.
Quando raggiunge l'ultima ora di sabato, ripete lo stesso procedimento per la classe successiva.
Questo programma prova tutte le combinazioni.
Il problema in questione ha complessità esponenziale, ma esistono altri programmi che risolvono questo problema in tempi ragionevoli. Il mio problema sembra molto simile al calcolo combinatorio dove la dimensione dell'input è abbastanza alto. Se esiste un algoritmo che risolve problemi combinatori in tempi ragionevoli, potrei adattarlo.
Sapete indicarmi una soluzioni più efficiente? Come posso ridurre il tempo di calcolo?
Questo è il codice della parte del BackTracking:
public void trovaCombinazioniOrario(){
int liv = 0;
boolean rivedi = false;
ArrayList<Classe> arrayClasse = new ArrayList<>( Arrays.asList( Classe.values() ) );
int nClasseAttuale = 0;
if( arrayClasse.isEmpty() ){ System.err.println("Non c'è nessuna classe da assegnare!"); System.exit(-1); }
Classe classe = arrayClasse.get(nClasseAttuale); //Prendo la prima classe
if ( !primaScelta( classe, liv) ){ //Innanzitutto faccio una prima scelta
System.err.println("Non c'è nemmeno la prima scelta per la classe "+classe);
return;
}//if
//TODO
while (liv >= -1){
// System.out.println("La classe attuale è "+classe+ " al livello "+liv);
System.out.println(this);
if( solCompleta(liv) ){ //Se il livello è l'ultimo,
/**Ho sistemato una classe e vedo la successiva*/
if( arrayClasse.size()-1 > nClasseAttuale ){ //C'è una prossima classe
nClasseAttuale++;
classe = arrayClasse.get( nClasseAttuale ); //prendo la prossima
liv = -1; //assegno la prossima classe a partire dal liv -1 (dopo fa l'incremento)
rivedi = false; //devo andare avanti e non rivedere
} else { //Non c'è una prossima classe, era l'ultima
filtraEStampa(); //filtra l'orario e lo stampa
rivedi = true; //provo altre combinazioni
liv++;
}//if lit
}else{
liv++; //Oppure incremento il livello
if( !primaScelta( classe, liv) ) //e faccio la prima scelta del livello successivo
rivedi= true; //se non va bene devo rivedere
}//else
while( rivedi && liv >= 0){ //finché non va bene
liv--; //torno indietro di livello
if( liv == -1 ){
/**Non ho soluzioni andando avanti e provo a modificare una classe precedente*/
if( nClasseAttuale > 0 ){ //C'è una classe precendente e devo riprovare
nClasseAttuale--;
classe = arrayClasse.get(nClasseAttuale);
liv = GIORNI_SETTIMANA * ORE_GIORNO -1; //riprovo a partire dall'ultimo livello della classe precedente
} else{ //Non c'è una classe precedente
System.out.println("Ho terminato le combinazioni");
return; //Non c'è nessuna scelta possibile
}//if lit
}//if -1
if( successivaScelta(classe, liv) ) //faccio la scelta successiva
rivedi= false; //se va bene, non devo più rivedere
}//while
}//while
}//assegnaClasse