Ciao a tutti,
dovrei permutare una matrice 157*13 ottenendo come risultato un array di 157 elementi che soddisfano alcune condizioni.
ho provato con la tecnica di backtrak ma il tempo per il risultato è lungo..
qualcuno di Voi mi puo' suggerire una valida (veloce) tecnica/algoritmo per ottenere il risultato?
grazie
E' una domandina un pochino generica, specificare meglio.
ok,Originariamente inviato da franzauker2.0
E' una domandina un pochino generica, specificare meglio.
dovrei elaborare un orario di lezione di una scuola..solo 5 classi.
per ogni classe ho le ore settimanali che deve fare.
es.:
classe 1: lun. 6 ore, mart. 6, mer 6, gio 5, ven 5, sab 4 = 32 ore settimanali
classe 2: lun. 6 ore, mart. 6, mer 6, gio 5, ven 5, sab 4 = 32 ore settimanali
classe 3: lun. 6 ore, mart. 6, mer 5, gio 5, ven 5, sab 4 = 31 ore settimanali
classe 4: lun. 6 ore, mart. 6, mer 5, gio 5, ven 5, sab 4 = 31 ore settimanali
classe 5: lun. 6 ore, mart. 6, mer 5, gio 5, ven 5, sab 4 = 31 ore settimanali
classe 1: 6 ore italiano+ 6 ore matem.........etcetc
quindi avrei pensato di elaborare l'orario e quindi ho creato una matrice:
la prima dimensione della matrice è il numero di ore da coprire e cioe 157 (32+32+31+31+31)
per ogni di queste 157 posizioni c'e' un array con dentro le possibili materie:
array(0)=1,2,3,4,5,6,7,8,9,10
array(1)=3,4,5,6,7,8,9,10
array(3)=1,2,3,6,7,8,9
array(4)=1,2,3,4,5,6,7,8,9,10
.....
.....
array(157)=1,2,3,6,7,8,9,10
adesso devo elaborare le possibili soluzioni.
devo 'COMBINARE' tutti questi array in modo da ottenere la soluzione che comprendera 1 elemento per ogni subarray quindi dovro avere un array come risultato di 157 elementi.
cerco di essere ancora più preciso:
gli elementi di ogni array sono stringhe di questo tipo:
multiArray[0,0]=G01O01M001I001C001T01
multiArray[0,1]=G01O01M002I001C001T01
multiArray[0,2]=G01O01M003I002C001T01
multiArray[0,3]=G01O01M004I003C001T01
multiArray[0,4]=G01O01M005I004C001T01
multiArray[0,5]=G01O01M006I005C001T01
multiArray[0,6]=G01O01M007I006C001T01
multiArray[0,7]=G01O01M010I007C001T01
multiArray[0,8]=G01O01M011I007C001T01
multiArray[0,9]=G01O01M013I008C001T01
spiego la struttura della stringa: G01O01M001I001C001T01
G01 = giorno 1
O01 = ora 1
M001 = materia 1
I001 = insegnante 1
C001 = classe 1
T01 = totale ore della materia nella settimana
ovviamente verranno scartate delle combinazioni..es.: un insegnante puo essere in una sola classe ad una certa ora di un certo giorno.
questi controlli io gia li faccio ma sembra ci voglia un tempo indefinito per elaborare tutte le combinazioni
come posso procedere?
grazie
ps. se vuoi posso postare tutta la matrice da combinare.
grazie ancora
Bhè è la classica domandina di RO.
Ci sono vari approcci possibili, con modellazioni diverse e addirittura algoritmi risolutivi esatti o euristici.
Puoi fare coi grafi (e quindi tipicamente userai il mitico Ford-Fulkerson) o perfino con un algoritmo genetico con premi-punizioni (ahh... mi sento giovane, mi sovvengono i problemi della susi...) per il lato-euristico.
In sostanza cosa ti turba? Il tempo di elaborazione ?
ciao franzauker,Originariamente inviato da franzauker2.0
Bhè è la classica domandina di RO.
Ci sono vari approcci possibili, con modellazioni diverse e addirittura algoritmi risolutivi esatti o euristici.
Puoi fare coi grafi (e quindi tipicamente userai il mitico Ford-Fulkerson) o perfino con un algoritmo genetico con premi-punizioni (
In sostanza cosa ti turba? Il tempo di elaborazione ?
scusa, che significa 'Bhè è la classica domandina di RO.' ?
mi turba il temèpo di elaborazione in quanto lo vedo lunghissimo...
ho studiato ed applicata la tecnica di BackTrak ma ci deve essere di meglio.
tu parli di grafi, Ford-Fulkerson, genetico...
hai, percaso, qualche esempio chiaro su cui poggiare la mia l'elaborazione?
grazie
Perchè è un problema noto e stranoto, assai difficile, detto CTTP o time tabling, che è un argomento classico (o almeno lo era ai miei tempi) per l'esame di Ricerca Operativa vecchio ordinamento (oggi non so, sono minicorsi dove forse insegnano la tabellina del 7).
Non esiste un metodo "magico" per risolvere questo problema, ed in letteratura ci saranno (a memoria) una cinquantina di metodi diversi, alcuni molto simili ai riti voodoo ed utilizzati, come facilmente comprensibile, per gli orari... delle università (dove i corsi son tanti, le aule pure e il problema diventa davvero difficile).
A seconda di come vedi il problema puoi modellarlo come un problema di programmazione lineare intera (PLI), rilassata opportunamente, come un problema combinatorio puro e duro, come un problema di flusso massimo (grafi), come un "qualcosa" (genetico).
In sostanza si cerca di trasformare il problema (difficile) in un "qualcosa" (modellazione) per il quale esiste già un algoritmo più o meno efficiente ed efficace per risolverlo.
In sostanza il vero problema, come te ne sarai accorto, è che dati certi vincoli (tipicamente detti hard e soft, ovvero violabili oppure no) non è per nulla banale giungere a una soluzione (anzi, in certi casi neppure esiste) esatta.
Indi per cui, per andar nello specifico, SE riesci a calcolare quello che ti serve, sia pur lentamente, bon, lascia stare, va già bene così e vivi felice.
Se invece vuoi qualcosa di più efficiente... fai prima a cercare qualche sorgente universitario in C, portarlo e compilarlo MAGARI IN JAVA
Se invece vuoi passare diciamo i prossimi 8 mesi a studiare come si risolvono problemi del genere... da qualche parte dovrei avere ancora gli appunti, se non gli ho dato fuoco
Anzi no... ripensandoci... li buttavo via direttamente sulla via del ritorno davanti al mitico barettino
Permessi di invio
Rispondi quotando