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

De Die Cedulas (orare pentru lecţiile unei zile) - 4

R | orar şcolar
2021 sep

7. Ordinea cea mai bună: "betweenness"

Cu mountHtoDay() obţinem orarele „cel mai bune” în cazul în care profesorii sunt ordonaţi după betweenness; statisticile furnizate printr-un program "traceMount.R" (v. [1]-3) arată atunci, cam aşa:

> source("traceMount7.R")
[1] 16:46:00   # 1:500
[1] 17:17:30   # durata execuţiei: cam 30 minute
trM   # numărul de ferestre - frecvenţă şi cuartile
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 
 2  1  6  6 17 23 25 39 32 57 48 42 39 35 32 28 24 16 11  8  2  2  3  1  1 
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  30.00   38.00   40.00   40.68   44.00   54.00 
[1] 11100   # total încercări
> source("traceMount7.R")
[1] 17:37:02   # 1:1000
[1] 18:33:21   # durata execuţiei: cam o oră
trM
 28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47 
  2   1   8   3   9  17  19  41  55  66  81  92  87 103 105  98  58  54  30  30 
 48  49  50  51  52  53 
 14  12   9   1   3   2 
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  28.00   38.00   41.00   40.56   43.00   53.00 
[1] 21311   # total încercări
> source("traceMount7.R")
[1] 19:20:34   # 1:1000
[1] 20:13:52   # durata execuţiei: cam o oră
trM
 25  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45 
  1   1   1   1   4   7  11  15  25  36  53  76  80  92  94 107  87  98  63  51 
 46  47  48  49  50  51  54  56 
 30  23  17  13   7   4   2   1 
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  25.00   38.00   41.00   40.47   43.00   56.00 
[1] 20253   # total încercări

Durata execuţiei (în medie, 60/1000=0.06 minute de orar) este mult mai mică decât în cazurile precedente.
Numărul de „încercări” (prin care mountHtoDay() produce un orar în care profesorii au zero, una singură, sau maximum două ferestre, consecutive) este în medie, 20 şi este mult mai mic decât în cazurile precedente.
Media numărului de ferestre din orarele obţinute este 40-41, deci „mai bună” decât obţinusem anterior; mai mult, în 75% dintre orarele rezultate, numărul de ferestre nu depăşeşte 43-44.

În cazurile anterioare nu ajungeam la orare cu mai puţin de 30 de ferestre; acum iată că obţinem şi orare cu „numai” 25 de ferestre (sau şi mai puţin).
În [1]-1 găsisem totuşi – întâmplător – un orar cu 25 de ferestre şi studiind orarul respectiv, exprimam bănuiala că pentru o obţine prin mountHtoDay() orare cu „puţine” ferestre, ordinea profesorilor trebuie să corespundă cumva „cu aceea în care fiecare să aibă cât mai puţine clase în comun, cu cei care îl preced”; încercând să formalizăm această bănuială – asupra poziţionării fiecărui profesor în raport cu ceilalţi, condiţionată de prezenţa unor clase comune – ajungem la "betweenness".

8. Graful profesorilor şi măsura "betweenness"

Considerăm un graf Γ având drept vârfuri profesorii existenţi în ziua pentru care vrem să obţinem un orar prin mountHtoDay(), două vârfuri fiind adiacente (legate printr-o muchie a grafului) dacă profesorii respectivi au măcar o clasă comună.

Am vrea să parcurgem cât mai „uşor” acest graf, trecând deci de la un vârf la următorul pe un cel mai scurt, dintre drumurile existente în Γ între cele două vârfuri. Considerând arbitrar două vârfuri, P1 şi P2, probabilitatea ca un anumit vârf P să fie „între” cele două date (adică să se afle pe un cel mai scurt drum, dintre cele care unesc P1 cu P2) este dată de raportul dintre numărul celor mai scurte drumuri de la P1 la P2 care trec prin P şi numărul tuturor celor mai scurte drumuri de la P1 la P2; valoarea acestui raport este „notată” betweenness(P1, P, P2), iar însumând toate aceste valori când P1 şi P2 variază în mulţimea tuturor vârfurilor – obţinem betweenness(P), pentru fiecare vârf P al grafului.

Bineînţeles că nu este necesar să modelăm noi, funcţia betweenness(); putem folosi de exemplu, pachetul igraph:

# profGraph.R
library("igraph")
source("schedulesDay.R")

lessons <- csv2tidy()  # lecţiile <prof><cls> din ziua 3 (68×40)
profs <- lessons %>% distinct(.$prof) %>% pull()  # şirul numelor profesorilor
np <- length(profs)
adjm <- matrix(rep(0, np), nrow=np, ncol=np, byrow=TRUE, 
               dimnames=list(profs, profs))  # matricea de adiacenţă

cls_of <- function(P) {  # şirul claselor profesorului dat
    lessons %>% filter(prof==P) %>% 
    distinct(cls) %>% pull()
}
adj_of <- function(P) {  # profesorii adiacenţi unuia dat
    lessons %>% filter(prof != P & cls %in% cls_of(P)) %>% 
    distinct(prof) %>% pull()
}
for(P1 in profs) {
    for(P2 in adj_of(P1)) {
        adjm[P1, P2] <- 1  # adiacenţi dacă au măcar o clasă comună
    }
}

g1 <- graph_from_adjacency_matrix(adjm, mode = "undirected")
btw <- betweenness(g1, directed=FALSE)

coords <- layout_with_lgl(g1)
plot(g1, vertex.size = btw*0.2, edge.curved = .2, layout = coords) 

saveRDS(btw %>% sort(), file = "betweenness.RDS")

În plot() am dimensionat mărimea de reprezentare a vârfurilor proporţional cu valorile "betweenness"; se vede pe figură (dar impresia vizuală ne poate păcăli) că ordinea profesorilor, descrescător după coeficienţii betweenness(), ar fi: "P05", "P36", "P02", "P07", ..., "P50", ..., "P65", "P59".
Desigur, am păstrat valorile respective în vectorul numit mai sus btw, pe care în final l-am ordonat crescător şi l-am salvat în fişierul "betweenness.RDS" – în scopul de a-l folosi apoi în funcţia setProfBits() din programul "schedulesDay.R", de exemplu pentru a obţine statistici precum cele redate mai sus (v. §7):

# traceMount7.R
rm(list=ls())
source("schedulesDay.R")
lessons <- csv2tidy() 
prfOrd <- function(vp) names(readRDS("betweenness.RDS"))
task <- setProfBits(lessons, FUN = prfOrd)
print(strftime(Sys.time(), format="%H:%M:%S"), quote=FALSE)
trM <- map_dbl(1:1000, function(i) {
    TB <- task[[1]] %>% split(.$cls)
    Bits <<- task[[2]]
    orZ <- mountHtoDay(TB)
    sum(unlist(lapply(orZ[[2]], holes)))
})
print(strftime(Sys.time(), format="%H:%M:%S"), quote=FALSE)
print(table(trM));  print(summary(trM));  print(NTRY)

Când foloseam (v. §5) un „grad empiric” pentru a ordona profesorii, aveam multe situaţii de egalitate (pentru care în §6 apelam la câte o ordonare aleatorie); de data aceasta, valorile din "betweenness.RDS" sunt distincte două câte două – cel puţin, pentru cazul ilustrat în program („lecţiile din ziua a 3-a”); în alte cazuri, or fi existând excepţii (adică egalităţi de coeficienţi) dar cu siguranţă foarte puţine.

Profesorii cu doar două ore în ziua respectivă au coeficienţii "btw" cei mai mici (cu unele excepţii), deci apar în capul listei lecţiilor fiecărei clase (a revedea în [1]-1, descrierea (I)–(IV) a algoritmului folosit de mountHtoDay()); prin urmare mountHtoCls() le va aloca orele 1 şi 2 ale zilei, sau (excepţional) orele 1 şi 3 (cu o fereastră). Redăm un orar obţinut prin mountHtoDay(), plecând de la ordinea profesorilor indusă de coeficienţii "betweenness" ai vârfurilor grafului de mai sus:

prof   1   2   3   4   5   6  7     prof   1   2   3   4   5   6  7
 P59  5E  5D   -   -   -   -  -	     P33   -   -  7C  9D 12A 10A  -
 P65  7E  7D   -   -   -   -  -	     P50   -   -  5C  9E  6B   -  -
 P64  9D  9C   -   -   -   -  -	     P20  7A   -   -  5D 10C  7B  -
 P56  5C 10B   -   -   -   -  -	     P21   -   -   - 11E 12E  9E  -
 P71  9A 12A   -   -   -   -  -	     P40   - 11D  9C 11B   -  8B  -
 P67  8C  7E   -   -   -   -  -	     P18  7B  6C   -  7A  6E   -  -
 P72 10E 11E   -   -   -   -  -	     P55   -   -   - 12A  5D  8C  -
 P63 11B  9A 11A   -   -   -  -	     P16   -   -  9A  5C 10A 11A  -
 P58 10B  6E   -   -   -   -  -	     P42   -   -   -   -  9B 10B 9E
 P26  8A 10E 10D  8B   -   -  -	     P34  5A  8B   -  5B 11E   -  -
 P48  6B  8F  7B   -   -   -  -	     P31   -   -  6C 11C  5E  9B  -
 P49  8D  9B 12B   -   -   -  -	     P11   -   -  5E  7E  7D  8D  -
 P29 12C  8A  8E   -   -   -  -	     P19   -   -  8F  5A  7B  6E  -
 P66 11E  9D   -   -   -   -  -	     P41   -   -   -  8E  9E  7A  -
 P47   -   -  7E  8A   -  8E  -	     P12   -   - 11C 12D 11D  7E  -
 P51  6C  8D  9B   -   -   -  -	     P04   -   -  7A  6C  7C  6B  -
 P60 11C 12D 12E   -   -   -  -	     P28 12B 10C  6A  9C 11B   -  -
 P14  7C 10A 10B   -   -   -  -	     P32   -  5A 11E  5E 11C   -  -
 P57  5D  6B  5A   -   -   -  -	     P37   -   -   -  9A  6C 11E  -
 P10   - 11B  8D 12B 10D   -  -	     P08   -   - 12C  6D  5C 12D  -
 P45  5B 12C  6E   -   -   -  -	     P22  8E   -   -  7B  6D 10E  -
 P46 10C  7B 12D   -   -   -  -	     P13   -   -  7D 10D 10E  8F 8B
 P44  6A  5C  9E   -   -   -  -	     P39   -   -  8C  8F  8E  7C  -
 P54 12E 12B   -  6E   -   -  -	     P23   -   -   - 11D  9A 10C 7D
 P62   -   -  9D 10A 10B   -  -	     P06  9E   -   - 12E 12D 12A  -
 P52 11D  7C   -   -  5A   -  -	     P09 10A 11A   -  7C  8F 11C  -
 P17  6D   - 11B  8C 11A   -  -	     P01 11A 10D  8B  6A  8C  8A  -
 P35 12A  6D 10C 11A   -   -  -	     P25   -   -   - 12C  7E  5D 9B
 P24 12D  6A  6B   -   -   -  -	     P03   -  8C  8A  7D  7A  5E  -
 P27  7D  5B 10E   -  8B   -  -	     P07   -   - 12A 10E  9D  9C 8A
 P53  9C  7A  6D 10C   -   -  -	     P36   -   - 10A  8D  6A  9D 8C
 P38  9B  9E  5B   -   -   -  -	     P02  6E   -   -  9B  9C  6C 7C
 P30  8F  5E  5D  6B   -   -  -	     P05 10D 12E   - 10B 12C  9A  -
 P15  8B  8E   -   -  8D 10D  -	    
 P43   - 11C 11D   -  8A  7D  -

Avem aici 22 de ferestre, de câte o singură oră în 10 cazuri şi de câte două ore consecutive în 6 cazuri; majoritatea ferestrelor sunt la mijloc, în orele 3 şi 4 ale zilei (în orele 2 şi 5 avem numai câte două ferestre).

Putem recupera – prin unique(orZ[[1]]$cls) (v. [1]-1) – lista claselor în ordinea folosită de mountHtoDay() pentru obţinerea orarului respectiv şi… apare o idee aparent năstruşnică: am putea reduce (într-o anumită măsură, probabil) ferestrele din orarul rezultat „repetând” mountHtoDay() (cu ordinea de profesori şi clase prin care a rezultat orarul), dar prevăzând acum posibilitatea de revenire la o clasă anterioară (pentru a modifica orarul stabilit lecţiilor acesteia), de fiecare dată când setarea coloanei $ora a clasei curente induce crearea unei ferestre la unul dintre profesori. „Năstruşnică” sau nu, ideea este totuşi dintre cele „uşor” de probat manual

vezi Cărţile mele (de programare)

docerpro | Prev | Next