Următoarea subliniere ne face să schimbăm strategia deterministă desfăşurată copios în [1]: există (cel puţin) o clasă a cărei mutare dintr-o anumită coloană într-o alta, conduce la un orar cu mai puţine ferestre. De exemplu:
count_gaps <- function(Orar) cnt_all_gaps(get_bin_patt(Orar)) print(count_gaps(MXT)) # iniţial, 25 ferestre rcs <- move_cls(MXT, 1, 2, "5E") # mută-KEMPE(1,2) clasa "5E" rcs <- recast(rcs) # "repară" ferestrele, după mutarea efectuată print(count_gaps(rcs)) ## în final, 17 ferestre
Pe orarul rezultat se va găsi deasemenea o clasă, a cărei mutare diminuează numărul de ferestre, ş.a.m.d. Dar e greu de crezut că am putea stabili un criteriu general, prin care să identificăm „deodată” acea mutare-Kempe de clasă care să diminueze (eventual, cel mai mult) numărul de ferestre; „strategia” din [1] ţine în fond, de o căutare exhaustivă a acestor mutări (dar parcă nu chiar pe toate căile, independent una de alta: fixam câte o coloană şi mutam fiecare clasă din acea coloană).
Putem încerca doar să nimerim cumva, câte o asemenea mutare…
Următoarea funcţie alege la întâmplare una dintre clase, precum şi două coloane distincte dintre cele care conţin clasa respectivă, mută clasa de-a lungul acestor coloane şi „repară” (pe baza gamei de reparaţii instituite în [1]) orarul rezultat astfel (şi e clar că alegerile făcute sunt independente între ele):
Cls <- MXT[, 1]; Cls <- Cls[Cls != '-']; names(Cls) <- NULL # vectorul claselor cb7 <- combn(ncol(MXT), 2) # toate combinările de câte două coloane gen_rand_tmt <- function(morr) { repeat { ql <- sample(Cls, 1) # o clasă oarecare repeat { h12 <- cb7[, sample(ncol(cb7), 1)] # două coloane oarecare if(ql %in% morr[, h12[1]] & ql %in% morr[, h12[2]]) break # ambele coloane conţin clasa } mor <- move_cls(morr, h12[1], h12[2], ql) # mută-KEMPE clasa if(!is.null(mor)) break } recast(mor) # returnează noul orar, după ce îi "repară" ferestrele }
Adoptăm orarul returnat dacă are mai puţine ferestre decât precedentul; altfel (probabil, cel mai adesea) reapelăm gen_rand_tmt(), repetând până când numărul de ferestre se stabilizează la o anumită valoare (şi dacă numărul de repetări este suficient de mare, putem spera ca această valoare să fie acceptabil de mică):
search_better <- function(Niter = 1000) { # modelează "Local search" (standard) S <- MXT # orarul iniţial ng <- count_gaps(S) repeat { for(i in 1:Niter) { Si <- gen_rand_tmt(S) # derivează aleatoriu un "nou" orar ngi <- count_gaps(Si) if(ngi <= ng) { # acceptă, dacă nu-s mai multe ferestre S <- Si ng <- ngi } } if(ng == ngi) # Returnează ultima soluţie care n-a mai putut fi break # îmbunătăţită prin ciclul curent 1:Niter } S }
Pentru orarul iniţial redat în [1] (cu 25 de ferestre), chiar şi pentru Niter mic (= 100), putem obţine (dacă avem noroc) un orar cu 10 ferestre în doar un minut (nu 15, ca în [1]), sau repetând, un orar cu 9 sau poate 8 ferestre.
Am experimentat pentru diverse valori Niter:
prnTime <- function() print(strftime(Sys.time(), format="%H:%M:%S"), quote=FALSE) sink("sann.txt", append=TRUE) prnTime() for(s in 1:20) { S <- search_better() # Niter=1000; Niter=5000; Niter=10000 print(count_gaps(S)) print.table(S) } prnTime() sink()
Pentru nIter=1000, a rezultat următoarea repartiţie după numărul de ferestre a orarelor obţinute (într-o execuţie a secvenţei de mai sus):
8 9 10 11 12 13 # ferestre
1 4 7 6 1 1
iar durata medie a producerii noului orar a fost cam de 5 minute.
Mărind numărul de iteraţii la 5000, respectiv 10000 – timpul mediu de obţinere a orarului a crescut cam la 18 şi respectiv, 36 de minute, cu aceste repartiţii după numărul ferestrelor (în câte o execuţie, a secvenţei de mai sus):
Niter 6 7 8 9 10 # ferestre
5000 1 9 5 4 1
10000 6 7 5 1 1
Mărind suficient de mult numărul de iteraţii, cresc şansele de a „nimeri” (dar într-un timp mai mare) orare cu mai puţine ferestre.
Desigur, am verificat faptul că orarele obţinute diferă între ele; ferestrele dintr-un orar cu 6 ferestre sunt altfel repartizate decât cele dintr-un alt orar cu 6 ferestre şi în general, orarele individuale ale profesorilor diferă pe cele două orare.
Dintre orarele care ne-au rezultat, redăm unul cu 6 ferestre (repartizate câte una, la 6 profesori cu câte 4 sau 5 ore, patru ferestre în a 3-a şi două în 4-a oră a zilei), care şi prin poziţionarea orelor, diferă sensibil faţă de orarul cu 10 ferestre din [1] (unde profesorii de deasupra lui P10 începeau programul, cu numai două excepţii, de la prima oră a zilei):
1 2 3 4 5 6 7 1 2 3 4 5 6 7
P59 5D 5E - - - - - P43 - - - 8A 11D 11C 7D
P65 - - - - 7E 7D - P33 - - 12A 9D 10A 7C -
P64 - - - - 9C 9D - P50 - - - 9E 5C 6B -
P56 10B 5C - - - - - P20 7B 5D 10C 7A - - -
P71 - - - - 12A 9A - P21 - - - - 12E 11E 9E
P67 7E 8C - - - - - P40 - - - 11D 11B 9C 8B
P72 - - - - 11E 10E - P18 - - 7B 6C 6E 7A -
P63 11B 11A 9A - - - - P55 - - - 12A 8C 5D -
P58 6E 10B - - - - - P16 10A 9A 5C 11A - - -
P26 - - - 10E 8B 10D 8A P42 - - - 9B 10B 9E -
P48 - - - 8F 6B 7B - P34 - - 5B 11E 5A 8B -
P49 9B 8D 12B - - - - P31 - - 6C 5E 11C 9B -
P29 8A 8E 12C - - - - P11 5E 7E 7D 8D - - -
P66 11E 9D - - - - - P19 - - 8F 5A 7B 6E -
P47 - - - 7E 8A 8E - P41 9E 7A 8E - - - -
P51 - - - - 6C 8D 9B P12 11C 11D 7E 12D - - -
P60 12D 12E 11C - - - - P04 - - - 6B 7A 6C 7C
P14 7C 10A 10B - - - - P28 10C 12B 9C 11B 6A - -
P57 6B 5A 5D - - - - P32 5A 11E 5E 11C - - -
P10 8D 11B - 12B 10D - - P37 9A 6C 11E - - - -
P45 12C 5B 6E - - - - P08 6D 12C - 5C 12D - -
P46 - - - 7B 10C 12D - P22 10E 7B 6D 8E - - -
P44 5C 9E 6A - - - - P13 10D 8F 10E 8B 7D - -
P54 12B 6E 12E - - - - P39 - - - 7C 8E 8F 8C
P62 - - - 10B 9D 10A - P23 - - 11D 7D 9A 10C -
P52 11D 7C 5A - - - - P06 12A 12D - 12E 9E - -
P17 11A 6D 11B 8C - - - P09 8F 11C 10A - 7C 11A -
P35 - - 11A 10C 6D 12A - P01 8B 8A 10D 6A 11A 8C -
P24 6A 6B 12D - - - - P25 - - 9B 12C 5D 7E -
P27 7D 10E 8B 5B - - - P03 7A 7D 8C - 5E 8A -
P53 9C 10C 7A 6D - - - P07 9D 12A 8A 9C 10E - -
P38 5B 9B 9E - - - - P36 8C 6A 9D 10A 8D - -
P30 - - 6B 5D 8F 5E - P02 6C 9C 7C 6E 9B - -
P15 8E 8B 8D 10D - - - P05 12E 10D - 9A 12C 10B -
Eventual, putem opera şi „în trepte”:
prnTime() # 16:35:09 S <- search_better(600) # MXT este orarul iniţial, cu 25 ferestre print(count_gaps(S)); prnTime() # 12 ferestre; 16:37:23 (2 minute) MXT <- S # pentru a pleca de la noul orar, cu 12 ferestre S <- search_better(3000) # acum, cu număr mare de iteraţii print(count_gaps(S)); prnTime() # 8 ferestre; 16:42:34 (5 minute)
Timpul în care am obţine prin search_better() (cu un număr mare de iteraţii) un orar acceptabil ca număr de ferestre, depinde de dimensiunile orarului (numărul de clase şi de profesori); obţinerea unui orar cu suficient de puţine ferestre depinde apoi de gama de „reparaţii” pe care am prevăzut-o şi întrucâtva, de faptul că unele clase (având mai puţine ore decât celelalte) sunt restricţionate la primele 4 sau 5 coloane.
vezi Cărţile mele (de programare)