Vizăm acum o chestiune care atârna în mod tacit de mult timp: câte mutări de clase, dintr-o coloană orară în alta, au loc succesiv în cursul procesului de reducere a numărului inițial de ferestre? Altfel spus, câte orare intermediare sunt produse? Sunt toate aceste mutări, necesare? Poate fi totuși redus, numărul acestora?

Drept ecou de control (pe ecran) al procesului de reducere succesivă a numărului de ferestre — redam mereu numai reducerile petrecute (nu și etape intermediare):

07:56:06   Jo (76 ferestre)
75  74  73  72  71  70  69  68  67  66  65  64  63  62  61  60  59  58  57  56  55  54  53  52  51  49  48  47  46  45  44  43  42  41  40  39  38  37  36  35  34  33  32  31  30  * 30  29  28  27  * 27  * 27  * 27  * 27  07:57:02 

În prima serie de iterații din search_better(), cele 76 de ferestre inițiale au fost reduse succesiv până la 30, pe un număr de 45 de orare intermediare; în a doua serie de iterații (despărțită pe ecran prin '*'), numărul de ferestre a ajuns de la 30 la 27 (cu 3 orare intermediare); reluând apoi de încă 4 ori, iterațiile respective — n-au mai rezultat orare intermediare cu mai puțin de 27 de ferestre (încât ajungem să considerăm că 27 este "minim posibil", de ferestre).
La prima vedere, luându-ne după datele afișate, au fost în total 48 de "orare intermediare" — ceea ce este fals: pentru prima serie de iterații de exemplu, s-au afișat numai stările în care numărul de ferestre s-a micșorat succesiv (nu și pentru orarele intermediare cu un același număr de ferestre — rezultate și acestea pe parcurs, prin diversele mutări efectuate).

Este totuși ușor de găsit numărul tuturor orarelor intermediare și chiar, lista mutărilor corectoare efectuate succesiv (rămâne de văzut dacă este și important…).
Fiecare serie de iterații prevăzută în search_better() (v. [3]) începe cu:

 mpn <- choose_next(Best)  # aplică o mutare corectoare

Prin choose_next() se preia de la cover_gaps() o "mutare corectoare" (reținând-o în 'mpn'):

     swp <- cover_gaps(Mop)  # o mutare corectoare, (h1 h2 cls)

și dacă numărul de ferestre din orarul intermediar produs prin mutarea respectivă este mai mic sau egal cu cel din orarul curent, atunci se returnează orarul intermediar rezultat și numărul său de ferestre; n-avem decât să adăugăm și mutarea respectivă:

    list(mor, ng, swp)

Revenind în search_better() și acceptând orarul intermediar curent, n-avem decât să înregistrăm într-un vector global HK, mutarea care produsese acest orar intermediar:

HK <<- rbind(HK, mpn[[3]])

Bineînțeles că programul principal trebuie rescris față de [3], pentru a avea în vedere acum și vectorii HK corespunzători respectiv, fiecărei zile:

source("gaps.R")
ORR <- readRDS("Orar1.RDS")  # listă [[Zi]]: lecții prof|cls|ora
mORR <- map(ORR, hourly_matrix)
W <- list()  # va înregistra orarele cu număr redus de ferestre
stakes <- c(28, 29, 27, 27, 28) %>% 
          setNames(Zile)  # numărul mizat de ferestre/zi
lHK <- list()  # înregistrează mutările efectuate
for(zi in Zile) {
    repeat {
        HK <- c("", "", "")  # inițializează vectorul mutărilor
        NG1 <- count_gaps(OZ) # numărul inițial de ferestre
        prnTime(paste0("  ", zi, " (", NG1, " ferestre)\n"))
        orr <- search_better(OZ) 
        if(NG1 <= stakes[zi]) 
            break  # încheie la un orar cu număr minim de ferestre
        prnTime(paste0(" (", nrow(HK)," mutări)\n")) 
    }
    lHK[[zi]] <- HK[-1, ] %>% as.data.frame() %>% 
                 setNames(c("h1","h2","ql")) %>%
                 `rownames<-`(NULL)
    W[[zi]] <- orr  # fără ordonare după numele profesorilor  
    prnTime(paste0(" (", nrow(HK)," mutări)\n")) 
}
saveRDS(W, "orarMar3.RDS")
saveRDS(lHK, "lHK3.RDS")

De observat că acum va fi afișat și numărul de mutări nrow(HK) (dar fără a mai ține seama că prima din HK este de fapt "vidă" și trebuia exclusă).
search_better() se execută într-un timp aproape constant (un minut, fără 1-4 secunde — pentru cazul, foarte dens, din [3]); dar până la nimerirea unei secvențe de orare intermediare încheiate cu unul care are minimul posibil de ferestre, search_better() trebuie (eventual) repetat de mai multe ori, pentru ziua curentă:

07:02:52   Ma (74 ferestre)  # o primă execuție search_better()
73  72  70  69  67  66  65  64  63  62  61  60  59  58  57  56  55  54  53  52  51  50  49  48  47  46  45  44  43  42  41  40  39  38  37  36  35  34  33  32  31  * 31  * 31  * 31  * 31  30  * 30  07:03:50  (1779 mutări)
07:03:50   Ma (74 ferestre)  # o altă execuție search_better()
73  72  71  70  69  67  66  65  63  62  61  60  59  58  57  56  55  54  53  51  50  49  48  47  46  45  44  43  42  41  40  39  38  37  36  35  34  33  * 33  32  31  * 31  * 31  30  * 30  29  * 29  07:04:48  (1872 mutări)

În [3] am evocat o instanță de execuție fericită a programului (dar fără infrastructura adăugată mai sus pentru vectorii HK), finalizată în doar 11 minute; acum, una dintre execuțiile programului redat mai sus a consumat aproape o oră și putem constata că numărul orarelor intermediare produse pe parcurs pentru fiecare zi este enorm (iar dintre acestea, numai 40-50 sunt orare intermediare pe care numărul de ferestre a devenit mai mic — și nu egal — față de orarul intermediar precedent):

> sapply(lHK, nrow)
      Lu   Ma   Mi   Jo   Vi  # iar într-o altă execuție, mai scurtă (40 min.):
    1945 1759 1698 1953 1929  #     1443 1487 1624 1614 2287

Este ușor să verificăm că de exemplu pentru ziua Lu, prin efectuarea succesivă a celor 1945 de mutări (h1 h2 ql) înregistrate în lHK[["Lu"]], obținem în final un orar identic celui cu 28 de ferestre depus prin programul de mai sus în W[["Lu"]] (cu observația că dacă la depunerea în lista W ordonam liniile după 'prof', cum avem în [3] — atunci orarele comparate n-ar mai fi fost găsite ca identice):

source("gaps.R")
ORR <- readRDS("Orar1.RDS") 
mORR <- map(ORR, hourly_matrix)
mOZ <- mORR[["Lu"]]  # matricea-orar inițială pe Lu (cu 70 ferestre)
HK <- readRDS("lHK3.RDS")[["Lu"]]  # lista celor 1945 mutări succesive
G <- vector("integer", length = nrow(HK)) 
for(i in 1:nrow(HK)) {
    G[i] <- count_gaps(mOZ)  # numărul de ferestre după mutarea curentă 
    mOZ <- move_cls(mOZ, HK[i,1], HK[i,2], HK[i,3])  # orarele intermediare
}
OZ <- readRDS("orarMar3.RDS")[["Lu"]] 
print(identical(mOZ, OZ))  # [1] TRUE

De observat că am considerat și un vector G în care am înregistrat (prin count_gaps()) numărul de ferestre din fiecare orar intermediar rezultat prin aplicarea mutării curente din vectorul HK — încât acum putem vedea frecvența de producere a unor orare intermediare cu câte un număr nemodificat de ferestre:

> table(G) %>% as.data.frame() %>% arrange(desc(G))
        G Freq          G Freq          G Freq          G Freq          G Freq
    1  70    4      11 58    8      21 48    1      31 38    8      41 28  376
    2  69    9      12 57    3      22 47   10      32 37   38
    3  68   10      13 56   21      23 46    2      33 36    1
    4  67   12      14 55    6      24 45    5      34 35   28
    5  66    2      15 54    7      25 44   20      35 34  116
    6  65    6      16 53    4      26 43   20      36 33   22
    7  63    1      17 52   10      27 42   23      37 32  480
    8  62   11      18 51    3      28 41   11      38 31   64
    9  61    4      19 50    4      29 40   33      39 30   80
    10 60    5      20 49   14      30 39   11      40 29  452

Prin primele 4 mutări din HK au rezultat orare intermediare cu același număr 70 de ferestre ca și în orarul inițial; a 5-a mutare a produs din orarul intermediar precedent, un orar cu 69 de ferestre, iar următoarele 9 mutări au produs orare intermediare având tot câte 69 de ferestre; ș.a.m.d.
Cele mai multe orare cu câte un număr nemodificat de ferestre au fost produse când orarul intermediar curent a ajuns să aibă 32 de ferestre (480 orare), sau mai puține; când s-a coborât la 29 de ferestre, s-au generat 452 de orare intermediare cu câte 29 de ferestre, până ce s-a nimerit unul cu 28 de ferestre — care, după încă 376 de încercări (însemnând toate, orare cu câte 28 de ferestre), n-a mai putut fi îmbunătățit.

Experiențele anterioare ne-au arătat deja că nu putem ignora orare intermediare cu câte un același număr de ferestre: dacă în search_better() am accepta numai orare cu număr de ferestre mai mic decât cel curent, atunci numărul final de ferestre va fi departe de cel "minim posibil". Dar… nu-i obligatoriu să luăm în seamă toate orarele intermediare cu câte un același număr de ferestre, rezultate prin câte o mutare corectoare aleatorie!

Cel puțin pentru cazul orarului din [3], se dovedește suficient să acceptăm doar vreo două treimi dintre orarele intermediare cu câte un același număr de ferestre:

choose_next <- function(Mop) {
    swp <- cover_gaps(Mop)  # o mutare corectoare, (h1 h2 ql)
    if(is.null(swp)) return(NULL)
    G <- count_gaps(Mop)
    mor <- move_cls(Mop, swp[1], swp[2], swp[3])
    if(is.null(mor)) return(NULL)
    ng <- count_gaps(mor)
    if(ng > G | ng == G & sample(0:2, size=1) == 1) 
        return(NULL)  # ignoră cam o treime dintre orarele intermediare
    list(mor, ng, swp)
}

Se ajunge și așa, la orare cu "minim posibil" de ferestre (implicând acum mult mai puține orare intermediare):

> sapply(lHK, nrow)
      Lu   Ma   Mi   Jo   Vi 
    1060 1417 1114 1250 1278 

dar așteptarea aparent firească, de reducere sensibilă a timpului total de execuție a programului, nu prea se adeverește; precizăm totuși că dacă am fi ignorat nu o treime, ci de exemplu două treimi dintre orarele intermediare — atunci nu mai ajungeam (cel puțin, nu într-un timp rezonabil) la orarele cu minim de ferestre.

Totuși, a devenit clar că luarea în seamă a mutărilor care nu micșorează numărul total de ferestre (producând câte un orar intermediar cu același număr de ferestre ca orarul intermediar curent) este într-adevăr importantă, numai spre sfârșitul procesului de reducere a ferestrelor — după ce numărul de ferestre din orarul curent a coborât la o anumită valoare (să zicem, pentru cazul din [3], cu 20 mai mare ca minimul așteptat).

Să înlocuim în choose_next() condiția comentată mai sus prin "ignoră cam o treime dintre orarele intermediare", cu următoarea:

    if(ng > G) return(NULL)  # ignoră mutările care măresc numărul de ferestre
    if(ng == G & ng > Lim) return(NULL)

Astfel, se vor accepta și mutări care nu modifică numărul curent de ferestre, dar numai dacă acest număr a fost coborât deja măcar până la valoarea Lim, fixată în programul principal pentru fiecare zi:

stakes <- c(28, 29, 27, 27, 28) %>% setNames(Zile)
Lims <- c(50, 50, 52, 52, 54) %>% setNames(Zile)
for(zi in Zile) {
    nCOL <- ncol(OZ)
    Lim <- Lims[zi]  # de când se admite păstrarea numărului de ferestre
    # etc.

Executând programul astfel modificat, putem vedea o execuție search_better() cu numai 19 mutări (prin care se coboară numărul de ferestre până la 51, deasupra valorii Lim) și una în care, nimerind un orar intermediar cu mai puțin de Lim ferestre, sunt acceptate apoi și mutări care nu modifică numărul curent de ferestre — încât devine posibilă coborârea mai departe, până la minimul posibil de ferestre (numărul de orare intermediare generate ridicându-se la 1615, în cazul de față):

08:07:21   Lu (70 ferestre)
69  68  67  66  65  63  62  61  60  59  58  57  56  55  54  53  52  51  * 51  * 51  * 51  * 51  * 51  08:08:20  (19 mutări)
08:08:20   Lu (70 ferestre)
69  68  67  66  65  64  63  62  61  60  59  58  57  56  55  54  53  52  51  50  48  47  46  45  44  43  42  41  40  39  38  37  36  35  34  33  32  * 32  31  30  29  * 29  * 29  28  * 28  * 28  08:09:17  (1615 mutări)

Această ultimă versiune de choose_next() pare a fi cea mai bună: numărul de reluări search_better() până ce se ajunge la valorile minime estimate în vectorul stakes este în general mai mic (și uneori mult mai mic) decât pentru versiunile anterioare, iar timpul total de execuție a programului se menține în medie (pentru cazul din [3]) între 20 și 40 de minute; dar… pentru aceasta, trebuie efectuate câteva experimente prealabile, pentru a regla adecvat orarului respectiv valorile Lims.