Cea mai bună alegere: cam la întâmplare

Pentru 7 ore/zi avem 99 de șabloane de orar individual cu ferestre, iar SBC asociază fiecăruia toate mutările posibile (h1 h2) prin care în șablonul respectiv, lecția din ora h1 se mută pe locul liber h2 (eventual, o fereastră a șablonului).
Avem de făcut o corectură, față de [3]:

> SBC |> unlist() |> length()
[1] 2184  # totalul mutărilor care acoperă ferestre (?)

De fapt mutările (h1 h2) sunt în număr de 2184/2=1092 — fiindcă unlist() a înregistrat separat valorile h1 și h2, nicidecum perechile (h1 h2); în plus, o bună parte a mutărilor respective nu prea, "acoperă ferestre" (poate rezulta un șablon care are mai multe ferestre decât cel inițial).

Cum am mai precizat anterior, bin_patt() transformă în șabloane binare orarele individuale dintr-o matrice-orar (pe profesori) dată:

> bin_patt
function(Mop) 
    apply(Mop, 1, function(Row) sum(h2bin[which(! Row %in% "-")])) %>%
    as.vector()  # șabloanele binare ale orarelor individuale

De observat o mică îmbunătățire față de versiunea inițială (din [2]): se returnează vectorul "curat" al șabloanelor, fără numele de linie asociate acestora (nu vom avea nevoie de numele profesorilor cărora le corespund șabloanele respective).

Ne interesează șablonele cu ferestre, existente în matricea-orar curentă — deci acelea dintre cele returnate de bin_patt() care sunt printre cele 99 chei ale dicționarului SBC:

    Vsb <- bin_patt(Mop)
    B1 <- which(Vsb %in% names(SBC))  # șabloanele cu ferestre

Avem astfel încă o mică îmbunătățire față de [2] (unde aplicam cnt_holes() fiecărui șablon, pentru a vedea dacă acesta are ferestre).

Aceste "mici îmbunătățiri" se dovedesc importante: reducerea de ferestre inițiată de search_better() — care apelează de mii de ori cover_gaps(), implicând de fiecare dată secvențele de mai sus — decurge cu vreo 30 de secunde mai rapid, decât în cazul folosirii versiunilor din [2] (și de fapt, mult mai rapid dacă și modificăm ca mai jos, mecanismul din cover_gaps()).

Pentru cover_gaps() avem trei versiuni: inițial (în [2]), returnam o mutare la întâmplare, din lista de "mutări corectoare" asociată orarului curent; apoi, în [3], alegeam (la întâmplare) una dintre clasele de coeficient betweenness mare care sunt implicate în mutările corectoare și returnam o mutare oarecare dintre cele corespunzătoare acelei clase — cu defectul de principiu, că spre sfârșitul iterațiilor de reducere crește riscul de a da mereu peste câte o aceeași clasă (cu prea puține mutări corectoare).
În sfârșit, avem varianta de mai jos, în care selectăm la întâmplare câteva dintre liniile pe care avem ferestre și returnăm una oarecare, dintre mutările corectoare asociate prin SBC liniilor respective:

load("SBC.Rda")
namesSBC <- names(SBC)
# nCOL indică numărul de coloane ale matricei-orar a zilei
cover_gaps <- function(Mop) {
    Vsb <- bin_patt(Mop)
    B1 <- which(Vsb %in% namesSBC)  # indecșii liniilor cu ferestre
    wg <- length(B1)
    if(wg == 0) return(NULL)  # Bravo! zero ferestre...
    lh1 <- lh2 <- vector("integer", 0)
    lql <- vector("character", 0)
    sz <- if(wg > 10) wg %/% 10 else (wg+1) %/% 2
    B <- B1 %>% sample(size = sz)  # un subset aleatoriu de șabloane
    for(id in B) {
        h12 <- SBC[[as.character(Vsb[id])]]
        H1 <- h12[["h1"]]; H2 <- h12[["h2"]]
        for(i in seq_along(H1)) {
            h1 <- H1[i]; h2 <- H2[i]
            if(max(h1, h2) > nCOL)
                next  # ocolește mutările în afara coloanelor existente
            lql <- c(lql, Mop[id, h1])
            lh1 <- c(lh1, h1)
            lh2 <- c(lh2, h2)
        }
    } 
    wh <- sample(x = 1:length(lh1), size = 1) 
    c(lh1[wh], lh2[wh], lql[wh])  # una dintre mutările asociate subsetului
}

Am modulat față de 10 — mai mult sau mai puțin inspirat — numărul sz de linii selectate dintre cele cu ferestre (dacă sunt cel mult 10 profesori cu ferestre, selectăm la întâmplare cam jumătate; altfel, selectăm câte o linie din 10); dar (după caz, sau… inspirație), putem modifica definiția de mai sus a variabilei sz.

Precizăm fără a mai detalia, că acum search_better() se finalizează cam în jumătate din timpul necesar în cazul când s-ar folosi prima dintre variantele cover_gaps() amintite mai sus (3 minute față de peste 6 minute, pentru orarul evocat în [3]).
Dar subliniem din nou că search_better() nu conduce neapărat, la un orar cu număr minim de ferestre (ci de obicei, la unul care are cu una-două, poate trei ferestre mai mult decât minimul posibil); repetând eventual execuția (pentru ziua curentă), a doua sau a treia oară, de obicei se ajunge la un orar pe care nu se mai poate reduce numărul de ferestre (și putem considera acest număr ca "minimul posibil").