momente şi schiţe de informatică şi matematică
anti point—and—click

Reducerea ferestrelor din orarul zilei (II)

Local Search | R | orar şcolar
2021 oct

Variaţiuni strategice

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)

docerpro | Prev | Next