PDA

Visualizza la versione completa : [delphi] permutazioni matrice


123delphi321
26-12-2012, 17:50
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

franzauker2.0
26-12-2012, 20:44
E' una domandina un pochino generica, specificare meglio.

123delphi321
26-12-2012, 21:27
Originariamente inviato da franzauker2.0
E' una domandina un pochino generica, specificare meglio.

ok,
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

franzauker2.0
27-12-2012, 10:55
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 ( :zizi: ahh... mi sento giovane, mi sovvengono i problemi della susi...) per il lato-euristico.

In sostanza cosa ti turba? Il tempo di elaborazione ?

123delphi321
27-12-2012, 11:18
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 ( :zizi: 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,

scusa, che significa 'Bh la classica domandina di RO.' ?

mi turba il tempo 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

franzauker2.0
27-12-2012, 11:30
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 :zizi:

Anzi no... ripensandoci... li buttavo via direttamente sulla via del ritorno davanti al mitico barettino :mem:

Loading