Revenim aici asupra unor construcţii din Ambiţiile Cavalerului; vizam drumuri hamiltoniene pe graful săriturii calului; dar… cavalerii ăştia erau în stare să susţină o cauză până-n pânzele albe.

Obiecţiuni la un obiect

Pentru rezolvarea problemei concepeam noi, următorul obiect Javascript:

function knightPath(rows, start_node, func_adj) { 
    this.rows = rows;                             
    this.size = rows * rows;            
    this.lists = func_adj(rows);        
    this.path = new Array(this.size); 
    this.find_path(start_node, 1);      // (1)
};

La instanţiere (prin var prob1 = new knightPath()), obiectul îşi execută în final funcţia find_path() (din prototipul cu care a fost înzestrat), prin care se determină un drum hamiltonian:

knightPath.prototype.find_path = function(square, depth) { 
    this.path[square] = depth; 
    if(depth == this.size)  { 
        this.dump();                    // (2)
        throw "done";                   // (3)
    }
    var lad = this.lists[square];
    var ln = lad.length; 
/* omitem aici secvenţa de ordonare a adiacenţilor după "grad()" */
    for(var i = 0; i < ln; i++) { 
        var next_sq = lad[i]; 
        if(!this.path[next_sq]) 
            this.find_path(next_sq, depth + 1); // (4)
    }
    this.path[square] = 0; // (5)
};

...dar (1) implică execuţia unei funcţii complexe proprii obiectului, de către chiar constructorul acestuia. Regula rezonabilă este rezumarea construcţiei la a pune la dispoziţie metodele de exploatare; decizia şi momentul aplicării uneia sau alteia dintre metodele cu care a fost înzestrat obiectul trebuie lăsată celui care îl instanţiază.

La (2) se afişează rezultatul… Dar find_path() are marea sarcină de a găsi un drum hamiltonian; "efectele laterale" trebuie evitate. Exploatarea rezultatului returnat (se afişează, sau se foloseşte ulterior în alte prelucrări) este treaba celui care a invocat metoda.

Pentru a ieşi din funcţia recursivă find_path() imediat ce s-a obţinut un drum hamiltonian, cea mai simplă soluţie a fost folosirea instrucţiunii throw (vezi (3)). Dar - similar funcţiei exit() din C - throw încheie execuţia întregului script; de exemplu, dacă am vrea să obţinem un drum hamiltonian pe tabla 6×6 şi apoi unul pe tabla 8×8 astfel: var p1 = new knightPath(6, ...); var p2 = new knightPath(8, ...); vom avea "surpriza" că se va instanţia doar p1 - scriptul respectiv se va încheia automat după ce se va fi executat primul throw (din p1.find_path()). Singura soluţie este ambalarea instanţierilor p1, p2 în blocuri try / catch, ceea ce este incomod şi restrictiv.

..."merg" ele, programele din Ambiţiile Cavalerului, dar modelarea, separarea şi corelarea obiectelor respective trebuie regândită şi probabil vom mai reveni asupra acestui aspect; aici însă ne vom ocupa numai de două reformulări - una recursivă şi una iterativă - ale funcţiei principale find_path().

Cursivitatea recursivităţii

find_path() este o funcţie recursivă, dar nu una de tip tail recursion (când reapelarea este ultima operaţie); în formularea redată mai sus, ultima operaţie este (5) şi nu reapelarea (4). Ori o funcţie "tail recursivă" este mai uşor de transformat într-o variantă iterativă (în plus, unele limbaje sau compilatoare asigură deja optimizări pentru codurile de tip "tail recursion", încât este preferabil de gândit astfel).

Că n-am nimerit iniţial o formulare cursivă ("tail recursion"), se datorează şi faptului că am implicat doi parametri: square care viza adiacentul curent şi depth, care numerota săriturile consecutive. Avantajul era că path[square] servea şi pentru marcarea situaţiei de "vizitat/nevizitat"; reiniţializarea din ultima operaţie (5) era necesară pentru situaţia în care reapelările (4) nu reuşeau să extindă drumul curent - deci… dacă renunţăm să întreţinem direct marcaje de "vizitat/nevizitat", scăpăm de operaţia de reiniţializare (5).

Puteam să angajăm numai parametrul depth, cu semnificaţia path[depth] = câmpul pe care sare calul a depth-a oară. Pentru eliminarea operaţiei (5) din final, angajăm cea mai simplă idee: adiacentul curent poate fi adăugat în path[] pe locul curent depth dacă el nu apare în path[] pe vreunul dintre locurile anterioare nivelului depth. Se va câştiga ceva timp prin faptul că find_path() ar avea un singur parametru şi nu doi, dar se va şi pierde timp datorită căutării pe rangurile anterioare; însă astfel, ajungem la o formulare "tail recursion".

Definiţia următoare ilustrează şi faptul că în Javascript funcţiile sunt obiecte (ca oricare altele); în particular, o funcţie poate fi inclusă în contextul unei alte funcţii (şi are acces la variabilele interne acesteia). Funcţia find_path_tr() pregăteşte funcţia grad() şi nişte variabile prin care se va simplifica accesul la câmpurile interne obiectului knightPath; apoi lansează funcţia internă trec() (tocmai aceasta corespunde funcţiei find_path() evocate mai sus), care formulează "tail recursion" combinaţia de backtracking şi euristică Warnsdorff (a vedea Ambiţiile Cavalerului) prin care se determină un drum hamiltonian.

knightPath.prototype.find_path_tr = function() { // ambalează funcţia tail-recursivă trec()
    var size = this.size; // numărul de câmpuri ale tablei de şah

    var L = this.lists, P = this.path; // referinţe la tabloul listelor de adiacenţă şi respectiv
                                       // la tabloul în care se va înregistra drumul hamiltonian 
    function grad(node) { // funcţie "privată" ajutătoare
        var cnt = 0, adj = L[node], d = adj.length;
        do {
            if(P.lastIndexOf(adj[--d]) == -1) cnt++;
        } while(d);
        return cnt; // numărul de câmpuri nevizitate, adiacente cu nodul dat
    };

    var beg = new Date().getTime(); // momentul la care se lansează trec(1) 
    var end = false; // trec() se va reapela cât timp end==false. La completarea soluţiei,
                     // trec() va fixa în 'end' momentul de timp respectiv.
    trec(1); // după setarea variabilelor ajutătoare de mai sus, execută funcţia trec()
    this.dump((end-beg)/1000); // alertează drumul hamiltonian obţinut şi durata execuţiei

    function trec(depth) {
        var sq = P[depth-1]; // ultimul câmp vizitat şi lista adiacenţilor săi, ordonată
        var lad = L[sq].sort(function(a, b) {  // conform principiului euristic al lui Warnsdorff
                                 return (grad(a) <= grad(b) ? -1 : 1); 
        });
        var k = 0, na = lad.length;
        for(; !end && (k < na); k++) {
            if(depth == size) // încheie dacă s-au vizitat toate câmpurile
                end = new Date().getTime(); // pentru un eventual calcul al duratei execuţiei

            else                                         // dacă adiacentul curent nu există în P, 
                if(P.lastIndexOf(lad[k], depth) == -1) { // înaintea nivelului curent (depth), 
                    P[depth] = lad[k];  // atunci îl vizitează (înscriindu-l pe nivelul depth în P)
                    trec(depth + 1);     // şi încearcă extinderea cu un adiacent al acestuia
                }
        }
    };
};

Durata execuţiei nu se reduce prin adoptarea noii funcţii trec() (faţă de cazul funcţiei iniţiale find_path()) - dar aceasta era de aşteptat, dat fiind că acum statutul de "vizitat" este determinat prin căutare în tabloul path (şi nu prin actualizarea corespunzătoare a unor marcaje, ca în funcţia iniţială). Mai mult, pentru căutare am implicat direct metoda lastIndexOf() - dar deocamdată puţine browsere au şi încorporat această extensie (desigur, ea poate fi adăugată "manual" folosind Array.prototype.lastIndexOf = function(elt) {...}).

Formula iterativă

Cu funcţiile recursive de mai sus apare şi "necazul" too much recursion (sau mai rău - browserul "îngheaţă"), începând de la o anumită dimensiune a tablei. Iar Sir Knight cel extravagant ar putea pretinde să alerge şi pe o tablă 100×100… dar mai ales ar pretinde să alerge mai repede; reformulând iterativ funcţia recursivă de mai sus putem obţine o multiplicare cu câteva ordine, a vitezei de execuţie (sporită apoi şi fiindcă am dispune de mai multă libertate pentru optimizarea codului).

knightPath.prototype.find_path_it = function() {
    var beg = new Date().getTime(); // momentul de timp la care începe

    // referinţe la câmpurile interne obiectului (grăbeşte accesarea lor)
    var L = this.lists, P = this.path, sz = this.size - 1;

    // adaugă fiecărei liste de adiacenţi un câmp "indexul adiacentului curent"
    for(var i = 0; i <= sz; i++) { L[i].idx = 0; }

    // compară pentru două noduri, numărul de adiacenţi nevizitaţi
    // adiacenţii nodului curent vor fi ordonaţi crescător după grad()
    function grad(a, b) { // pentru ordonare Warnsdorff a listei adiacenţilor unui nod
        var La = L[a], Lb = L[b];
        if(La.idx > 0) return 1000; // 'a' vizitat anterior => 'b' < 'a' (pune b la stânga lui a)
        if(Lb.idx > 0) return -1000; // 'b' vizitat anterior => 'a' < 'b' 
        var ga = 0, gb = 0, i = La.length, j = Lb.length;
        do { if(L[La[--i]].idx == 0) ga++; } while(i); // ga = câţi adiacenţi nevizitaţi are
        do { if(L[Lb[--j]].idx == 0) gb++; } while(j);
        return (ga - gb <= 0 ? -1 : 1); // sort() va fi ceva mai rapidă, decât cu  return (ga - gb);
    };
    
    var dh = 0 /* avem deja P[0] = nodul de plecare */, nend = true;
    while(nend) { 
        if(dh == sz) { // încheie după obţinerea unui drum hamiltonian
            this.dump((new Date().getTime()-beg)/1000); // afişează rezultatul şi durata
            nend = false; // semnalează încheierea execuţiei
        }
        else {
            var lad = L[P[dh]]; // lista adiacenţilor nodului P[dh] din care se încearcă extinderea
            if(lad.idx == 0) // dacă > 0 atunci lad[] a fost deja sortat, pe un nivel dh anterior
                lad.sort(function(a, b){ return grad(a, b); });
            if(lad.idx < lad.length) { // Dacă în lista lad[] mai există noduri neconsiderate deja,
                var sq = lad[lad.idx]; // alege pe cel care urmează şi actualizează
                lad.idx++;             // indexul de adiacent curent în lista lad[]
                if(L[sq].idx == 0) { // Dacă nu s-a trecut anterior prin nodul ales, 
                    dh++;            // atunci el este înregistrat în P[], 
                    P[dh] = sq;      // reiterând apoi operaţiile while()
                }
            }
            else { // dacă nu s-a reuşit completarea drumului mai departe de nivelul dh curent,
                lad.idx = 0; // reiniţializează indexul adiacentului curent din lad[]-curent şi
                dh--;        // încearcă următorul adiacent din lad[]-ul nivelului dh precedent.
            }
        }
    }
};

knight-rec-it.zip conţine un program de testare (javascript, HTML) a celor două variante (iterativă şi recursivă) prezentate mai sus. Se poate constata (dar era de aşteptat) că versiunea iterativă este mult mai rapidă decât cea recursivă (depinzând însă de opţiunea făcută pentru funcţia de adiacenţă); a încerca pe tabla 7×7, apoi pe 49×49, 50×50 (versiunea iterativă poate fi apoi probată pe cazuri ca 100×100, 150×150 şi probabil până pe la 170×170).

Scăderea categorică a duratei (în unele cazuri - de 80 de ori) se datorează desigur "derecursivării"; dar la fel de important este faptul că n-am mai folosit lastIndexOf() şi am optimizat mecanismul de sortare a listei adiacenţilor nodului curent (adăugând listei proprietatea idx - a vedea comentariile - şi implicând o funcţie de comparare a două noduri în loc de una care să dea doar "gradul" unui nod).

Unele secvenţe de cod ar putea să pară "artificiale" (dacă nu cumva, lasă impresia dorinţei de epatare); de exemplu, de ce am folosit do...while în loc de obişnuitul for, în funcţia grad(a,b)? Iniţial am folosit for, dar funcţia grad(a,b) trebuie "muncită", fiindcă este cel mai frecvent apelată şi am constatat că înlocuind cu do...while viteza creşte binişor (a vedea optimizare Javascript). Sau, de ce compar gradele şi returnez -1 sau 1 din grad(a,b) în loc de a returna cum se obişnuieşte, diferenţa a — b? Iarăşi e vorba de experiment şi ceva documentare… Funcţia sort() face o sortare instabilă, adică modifică (uneori) ordinea şi în cazul a — b == 0; evitarea interschimbării elementelor egale - în cazul nostru, cu acelaşi număr de adiacenţi nevizitaţi - permite un (uşor) câştig de viteză (mai mic sau mai mare, depinzând şi de adâncimea curentă).

Cine aleargă… calul?! ("time-out period")

E oarecum periculos, să gândeşti şi să expui un program folosind alegorii - fie acestea şi cu Sir Knight, ale cărui ambiţii şi peripeţii le-am evocat pe-aici; s-ar putea ca cineva să înţeleagă şi să şi creadă aşa: calul aleargă prin locaţiile de memorie în care se execută programul…

În timp ce se execută un script, browserul "îngheaţă"; dacă scriptul nu se încheie într-un anumit timp, browserul atenţionează printr-un mesaj de genul "Unresponsive script...".

Timpul afectat execuţiei unui script este un parametru global, având o anumită valoare implicită: pentru Interner Explorer - 5 milioane de instrucţiuni executate (google "how to set time-out period for script"), independent de viteza microprocesorului; pentru Firefox - 10 secunde. Dacă este cazul, în Firefox se poate modifica această valoare astfel: se tastează în bara de adresă config:about; se identifică parametrul dom.max_script_run_time şi se înscrie noua valoare (după aceea, browserul trebuie închis şi redeschis, pentru a activa noua opţiune).