Showing content from http://cran.rstudio.com/web/packages/rlang/../refitgaps/vignettes/clarifications-and-practice.Rmd below:
--- title: "clarifications-and-practice" output: rmarkdown::html_vignette vignette: > %\VignetteIndexEntry{clarifications-and-practice} %\VignetteEngine{knitr::rmarkdown} %\VignetteEncoding{UTF-8} --- ```{r, include = FALSE} knitr::opts_chunk$set( collapse = TRUE, comment = "#>" ) ``` ```{r setup} library(refitgaps) ``` ## Introducere Ãn imaginea de mai jos am extras dintr-un fiÈier PDF gÄsit pe website-ul unei anumite Ècoli, orarele pe o aceeaÈi zi (ultima, observând cÄ este urmatÄ de subsolul de paginÄ) pentru trei clase: ```{r out.width = '99%', echo=FALSE} knitr::include_graphics("images/Vi.png") ``` SÄ observÄm cÄ Ã®n ora a treia a zilei respective, fiecare dintre cele trei clase are de fÄcut câte o lecÈie de "GERMANA", cu... aceiaÈi *trei* profesori (cu numele separate prin '/', în celulele redate); avem aici un exemplu tipic de **tuplaj**: elevii reuniÈi din clasele iniÈiale sunt despÄrÈiÈi *ad-hoc*, dupÄ anumite criterii, constituind trei noi clase (pentru care se pÄstreazÄ numele de clasÄ iniÈiale) Èi în ora respectivÄ, la fiecare dintre cele trei clase formate astfel, intrÄ câte unul dintre cei trei profesori. Mai jos vom introduce anumite convenÈii de notaÈie, prin care tuplajul evidenÈiat mai sus s-ar reprezenta numind profesorii Èi apoi clasele pe care sunt tuplaÈi: `(Gr1 Gr2 Gr3) / (9A 9B 9C)` --- urmând sÄ Èinem seama pe parcurs, de cerinÈa ca aceste trei lecÈii sÄ cadÄ Ã®ntr-o *aceeaÈi orÄ* a zilei. Regula de bazÄ pentru *corectitudinea* unui orar este urmÄtoarea: în oricare orÄ din programul zilei, fiecare clasÄ (respectiv, profesor) face o singurÄ lecÈie, cu un singur profesor (respectiv, clasÄ). Ce ar însemna atunci, dacÄ ar fi fost specificaÈi nu trei, ci patru profesori, într-o aceeaÈi orÄ la cele trei clase: `(Gr1 Gr2 Gr3 Fr2) / (9A 9B 9C)`? DupÄ regula de corectitudine menÈionatÄ, trebuie sÄ ne gândim cÄ doi dintre aceÈti patru profesori (sÄ zicem ultimii doi) constituie un **cuplaj** pe una dintre clase: aceasta, sÄ zicem `9C` (formatÄ mai înainte, din elevi proveniÈi de la cele trei clase iniÈiale) este despÄrÈitÄ Ã®n douÄ "grupe" de elevi, iar `Gr3` Èi `Fr2` fac lecÈie în ora respectivÄ cu câte una dintre aceste "jumÄtÄÈi" ale clasei `9C` (notaÈia tuplajului devine `(Gr1 Gr2 Gr3Fr2) / (9A 9B 9C)`). Ãn *planul de încadrare* pregÄtit la începutul anului Ècolar de cÄtre conducerea Ècolii, se precizeazÄ pentru fiecare profesor al Ècolii, numele Èi prenumele, gradul didactic, disciplinele pe care este încadrat, clasele repartizate Èi numÄrul corespunzÄtor de ore, ETC. Normativele existente asupra numÄrului maximal de ore pe profesor, pe clasÄ Èi pe obiect fac posibilÄ Ã®ncropirea unui *orar* sÄptÄmânal, pentru desfÄÈurarea tuturor lecÈiilor `prof/obj/cls` prevÄzute în planul de încadrare (Èi de fapt, sunt posibile *foarte multe* orare, mai bune sau mai rele, pentru un acelaÈi set de lecÈii). De obicei, mai în toate Ècolile, orarul Ècolar este produs prin aplicaÈia comercialÄ [ascTimetables](https://www.asctimetables.com/) (sau varianta româneascÄ *aSc Orare*, semnatÄ Ã®n subsolurile de paginÄ cuprinse în imaginea de mai sus); pe de altÄ parte, ca teorie, "problema orarului Ècolar" (*School Timetable Problem*) are o vechime consistentÄ de peste 50 de ani, fiind tratatÄ mai peste tot ca "problemÄ combinatorialÄ de optimizare" (*v.* de exemplu: Pillay, N. (2014).*A Survey of School Timetabling Research*.Annals of OperationsResearch, 218(1), 261-293). Dar putem vedea *STP* Èi aÈa: se dÄ un *set de date*, conÈinând toate lecÈiile `prof/cls` desprinse din planul de încadrare al Ècolii; acest set iniÈial trebuie completat cu o coloanÄ `zi` pe care sÄ se înscrie *ziua* din sÄptÄmânÄ Ã®n care este repartizatÄ fiecare lecÈie, astfel încât repartiÈia pe zile rezultatÄ sÄ fie *echilibratÄ* pe zile, pe profesori Èi pe clase. Apoi, fiecare dintre subseturile de lecÈii repartizate în câte o aceeaÈi zi, trebuie completat cu o coloanÄ `ora` având ca valori acea orÄ `1:7` a zilei, în care trebuie alocatÄ fiecare dintre lecÈiile respective - astfel încât oricare douÄ lecÈii sÄ *nu* se suprapunÄ Ã®ntr-o aceeaÈi orÄ a zilei (ceea ce a constituit subiectul pachetului `https://cran.r-project.org/package=hours2lessons`). Ar rezulta astfel câte un *orar*, pentru fiecare zi în parte; problema care se mai pune constÄ Ã®n ajustarea orarului zilei, astfel încât numÄrul total de *ferestre* sÄ devinÄ cât se poate de mic (Èi aceasta constituie tema pachetului de faÈÄ).\ Un orar sÄptÄmânal ar fi Èi "bun", dacÄ: este echilibrat (în fiecare zi, avem cam acelaÈi numÄr de lecÈii; lecÈiile fiecÄrui profesor, ca Èi cele ale fiecÄrei clase, ca Èi cele pe un acelaÈi obiect la fiecare clasÄ, sunt repartizate *uniform*, pe zile); numÄrul total de ferestre este unul rezonabil, cât se poate de mic. Pentru a constitui setul iniÈial de date, *nu* avem nevoie de numele Èi prenumele profesorilor, nici de denumirile adoptate pentru disciplinele Ècolare; cel mai convenabil este sÄ *abreviem* disciplinele pe câte douÄ litere Èi sÄ desemnÄm profesorii concatenând numele abreviat al disciplinei principale pe care este încadrat fiecare, cu un numÄr de ordine între cei de pe o aceeaÈi disciplinÄ. De exemplu, `Bi1`, `Bi2` Èi `Bi3` ar reprezenta cei trei profesori de "Biologie", iar `Gr3Fr2` ar fi un profesor "fictiv" pentru lecÈiile "pe grupe" ale unei clase (în ora respectivÄ, `Fr2` face "FrancezÄ" cu o grupÄ, iar `Gr3` face "GermanÄ" cu cealaltÄ grupÄ). De observat cÄ pentru lecÈiile dintr-o aceeaÈi zi, nu este necesar sÄ pÄstrÄm câmpul `zi`; deasemenea, nu mai este necesar sÄ pÄstrÄm câmpul `obj`: disciplina principalÄ se deduce din codul profesorului (iar pentru eventualele discipline secundare, putem prevedea din start un dicÈionar separat). Deci orarul constituit pentru lecÈiile unei zile fixate, constÄ din trei câmpuri: `prof/cls/ora`. Desigur, trebuie respectatÄ condiÈia de ne-suprapunere a lecÈiilor (de exemplu, oricare lecÈie a cuplajului `Gr3Fr2` trebuie sÄ nu se suprapunÄ Ã®ntr-o aceeaÈi orÄ nici cu vreuna dintre lecÈiile lui `Gr3` Èi nici cu vreuna dintre cele ale lui `Fr2`, dacÄ aceÈtia au Èi "ore proprii" pe lângÄ cele din cuplaj); se impune firesc, sÄ constituim în prealabil un "dicÈionar" care sÄ reflecte dependenÈele între lecÈiile celor angajaÈi în cuplaje; dacÄ este cazul, trebuie specificate în prealabil Èi tuplajele existente. Ferestrele se pot vedea cel mai uÈor transformând orarul din "formatul lung" `prof/cls/ora` în "matrice-orar" pe profesori (*v.* `hours2lessons::long2matrix()`); de exemplu: ```{verbatim} prof 1 2 3 4 5 6 7 Gg1 9E 10B 5A - - 9D - # douÄ ferestre, în orele 4 Èi 5 Gg2 - 7B 6A 8B 9F - - # nu are ferestre Li1 10B - 12A - - - - # are 4 ore (o fereastrÄ "ascunsÄ") Li1Li3 - - - 11A - - - Li2 - - - 9D - 5B - # are 4 ore, cu douÄ ferestre (în orele 3, 5) Li2Li1 - 10A - - - - - Li2Li3 9A - - - - - - Li3 - 11B - - 11A - - # are o fereastrÄ (în ora 3) ``` Ãn orarul de pe care am extras liniile de mai sus, `Gg*` nu apar în vreun cuplaj; în schimb, calculul ferestrelor pentru cei trei profesori `Li*` este mai dificil, fiindcÄ ei intrÄ Ã®n cuplaje Èi au Èi ore proprii. Pe linia lui `Li1` apare o fereastrÄ, dar este o fereastrÄ *falsÄ*, fiindcÄ Ã®n ora 2 `Li1` are lecÈie împreunÄ cu `Li2` la clasa `10A`; se vede uÈor cÄ `Li1` are de fÄcut nu douÄ lecÈii câte apar pe linia proprie, ci 4 lecÈii, în orele `1:4` (fÄrÄ nicio fereastrÄ). `Li2` are lecÈii, singur sau în cuplaje, în orele 1, 2, 4 Èi 6, deci are douÄ ferestre (dintre care, una "ascunsÄ" în ora 3). `Li3` are 4 ore, cu o fereastrÄ Ã®n ora 3.\ Deci în total, secvenÈa de orar redatÄ mai sus conÈine 5 ferestre. BineînÈeles cÄ socotim numai ferestrele profesorilor reali, nu Èi ale celor "fictivi"; dar poate exista o excepÈie: dacÄ un profesor nu are ore proprii, ci are ore numai într-un cuplaj, atunci ferestre cuplajului respectiv reprezintÄ ferestre ale profesorului *extern* (fÄrÄ ore proprii) implicat în cuplaj. ## Cum acoperim o fereastrÄ? Reducerea numÄrului de ferestre Proprietatea principalÄ a unei matrice-orar este aceea cÄ fiecare clasÄ apare o singurÄ datÄ pe fiecare coloanÄ orarÄ de rang cel mult egal cu numÄrul de ore/zi ale clasei respective (altfel, ar fi doi profesori la aceeaÈi clasÄ, într-o aceeaÈi orÄ). Ãn setul de linii redat mai sus, `Gg1` are douÄ ferestre, în orele 4 Èi 5; le-am putea elimina mutând `9D` din coloana 6 în coloana 4 (ar rezulta orarul individual fÄrÄ ferestre `9E 10B 5A 9D - - -`) --- dar `9D` *exista deja* în coloana 4, pe linia lui `Li2`; deci, pentru a pÄstra unicitatea clasei pe coloanÄ, trebuie sÄ continuÄm mutÄrile de clase între cele douÄ coloane: interschimbÄ `9D` din coloana 4 cu `5B` din coloana 6, apoi `5B` care se gÄsea deja pe o anumitÄ linie în coloana 4, cu clasa existentÄ pe linia respectivÄ Ã®n coloana 6, Èi aÈa mai departe. SecvenÈa de mutÄri succesive care asigurÄ schimbarea unei clase dintr-o coloanÄ Ã®n alta, pÄstrând unicitatea pe coloane a fiecÄrei clase, formeazÄ un *circuit* al grafului $\Gamma$ care are drept arce perechile (q1 q2) de pe liniile setului constituit de cele douÄ coloane orare; dat fiind cÄ singura valoare care se poate repeta pe o coloanÄ este "`-`" (orÄ liberÄ, nu Èi vreo clasÄ), rezultÄ cÄ circuitele lui $\Gamma$ fie trec prin vârful "`-`", fie sunt componente conexe (Èi sunt *lanÈuri Kempe* ale lui $\Gamma$; *v.* `https://en.wikipedia.org/wiki/Kempe_chain`). FuncÈia *internÄ* `move_cls()` asigurÄ mutarea unei clase din coloana care o conÈine într-o altÄ coloanÄ, modelând parcurgerea lanÈului Kempe care conÈine clasa respectivÄ (din graful $\Gamma$ asociat celor douÄ coloane) Èi returneazÄ matricea-orar rezultatÄ astfel --- sau `NULL`, în trei cazuri: când rangul coloanei-destinaÈie depÄÈeÈte numÄrul de ore/zi ale clasei; când lanÈul Kempe respectiv, conÈine o clasÄ care *nu* poate fi mutatÄ Ã®ntr-o altÄ coloanÄ, fiind dintre cele angajate în tuplaje; respectiv, când prin efectuarea mutÄrii cerute, ar rezulta o suprapunere între un cuplaj Èi vreunul dintre membrii acestuia. Pe de altÄ parte, avem o listÄ internÄ 'SBC', care asociazÄ fiecÄrui Èablon de orar individual cu ferestre, mutÄrile de clasÄ dintr-o coloanÄ Ã®n alta care ar modifica (nu neapÄrat în jos) numÄrul de ferestre din Èablonul orar respectiv; de exemplu, pentru Èablonul "`-*--***`" (de patru lecÈii cu douÄ ferestre) avem: ```{verbatim} h1 h2 result # mutÄ '*' din locul h1, în locul h2 1 2 3 --*-*** 2 2 4 ---**** # s-ar elimina ambele ferestre iniÈiale 3 5 3 -**--** # douÄ ferestre, în loc de singura iniÈialÄ 4 5 4 -*-*-** 5 6 3 -**-*-* 6 6 4 -*-**-* 7 7 1 **--**- 8 7 3 -**-**- 9 7 4 -*-***- # de parcÄ Èablonul iniÈial a fost translatat cu o poziÈie ``` Am inclus Èi mutÄri care *mÄresc* numÄrul de ferestre din Èablonul individual respectiv (dar am exclus mutÄri care duc la apariÈia a 3 sau mai multe ferestre; de exemplu, în lista de mutÄri de mai sus nu avem Èi mutarea (3 1), care ar duce la un Èablon cu trei ferestre) --- pentru cÄ urmÄrim sÄ reducem numÄrul *total* de ferestre (Èi nicidecum, dintr-un *anumit* orar individual). Ideea de bazÄ a programului de reducere a numÄrului total de ferestre (modelatÄ Ã®n funcÈia publicÄ `recast()`) este urmÄtoarea: din matricea-orar *curentÄ* se aleg la întâmplare, câteva dintre liniile cu ferestre Èi se executÄ (prin `move_cls()`) una oarecare, dintre mutÄrile asociate prin 'SBC' Èabloanelor de orar de pe liniile respective; dacÄ matricea-orar rezultatÄ are mai puÈine ferestre, sau mÄcar tot atâtea ca matricea-orar curentÄ, atunci ea devine noua matrice *curentÄ* Èi lucrul se reia asupra acesteia; dacÄ dupÄ un anumit numÄr de iteraÈii (suficient de mare, dar... rezonabil), numÄrul de ferestre din orarul curent nu mai poate fi coborât, atunci se încheie, returnând ultima matrice-orar "curentÄ" (care de regulÄ, are un numÄr acceptabil de ferestre, iar uneori, poate dupÄ mai multe invocÄri `recast()`, chiar unul *minim posibil*). Fiind implicate aspecte aleatorii, la fiecare nouÄ invocare a funcÈiei `recast()` va rezulta un alt orar, cu altÄ alocare de ore Èi eventual cu alt numÄr de ferestre. ## Un exemplu de lucru Am încorporat o matrice-orar '`MOZ`' obÈinutÄ anterior prin pachetul `hours2lessons` (... deci una care sigur, are *multe* ferestre), împreunÄ cu setul de tuplaje '`TPL`' asociat ei; Èinând seama cÄ prima coloanÄ conÈine toate clasele câte o singurÄ datÄ, putem afla numÄrul de clase: ```{r} sum(MOZ[, 1] != "-") # numÄrul de clase prezente în orar ``` Dar sÄ aflÄm mai degrabÄ, numÄrul de ferestre: ```{r} HG <- have_gaps(MOZ) # subsetul liniilor pe care existÄ ferestre stringr::str_extract(HG$ore, "\\*.+\\*") %>% paste0(collapse = "") %>% stringr::str_count("-") ``` DacÄ ne gândim cÄ pe primele 6 coloane avem câte 32 de clase (poate ceva mai puÈine, în a 6-a orÄ) Èi adÄugÄm câteva clase care apar Èi în a 7-a coloanÄ orarÄ --- deducem cÄ Ã®n `MOZ` avem în total cam 200 de lecÈii, faÈÄ de care proporÈia celor 42 de ferestre (cam 20%) este chiar foarte mare...\ Ar fi acceptabil sÄ avem numai vreo 5% ferestre (faÈÄ de totalul lecÈiilor), iar aceasta este chiar posibil, dacÄ setul tuplajelor nu este prea mare, sau întortochiat. RepetÄm execuÈia lui `recast()` pânÄ ce rezultÄ un orar cu mai puÈin de 10 ferestre: ```{r eval = FALSE} prnTime <- function(NL = " ") # afiÈeazÄ timpul curent cat(strftime(Sys.time(), format = "%H:%M:%S"), NL) prnTime("\n") repeat { ORR <- recast(MOZ, TPL) cat(ORR[[2]], " gaps ") prnTime('\n') if(ORR[[2]] < 10) break } ``` RedÄm parcursul a *douÄ* execuÈii ale secvenÈei de mai sus: ```{verbatim} 04:13:06 04:30:54 11 gaps 04:13:48 13 gaps 04:31:34 11 gaps 04:14:28 13 gaps 04:32:15 11 gaps 04:15:08 11 gaps 04:32:54 11 gaps 04:15:49 14 gaps 04:33:36 10 gaps 04:16:29 7 gaps 04:34:15 14 gaps 04:17:10 12 gaps 04:17:51 12 gaps 04:18:32 8 gaps 04:19:12 ``` Ãn cele douÄ execuÈii am ajuns la un orar cu 8 Èi respectiv, 7 ferestre (în 6 Èi respectiv, 3 minute); cu `have_gaps(ORR[[1]])` am putut constata cum sunt distribuite ferestrele respective pe profesori --- în primul caz avem 8 profesori cu câte o fereastrÄ Èi l-am prefera celuilalt caz, în care ne-au rezultat 5 profesori cu câte o fereastrÄ Èi unul cu *douÄ* ferestre (desigur, executând pe un alt calculator, în alt moment de timp, rezultatele vor fi altele decât cele evocate mai sus).
RetroSearch is an open source project built by @garambo
| Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4