De Die Cedulas (orare pentru lecţiile unei zile) - 4
[1] De Die Cedulas (orare pentru lecţiile unei zile) - 1, - 2, - 3
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)