[1] (2009) Ambiţiile Cavalerului şi Saltul recursiv şi alergarea iterativă
În [1] am implicat javaScript pentru a determina un drum hamiltonian pe "graful calului de şah", compunând backtracking şi regula lui Warnsdorff (aceasta conduce liniar la soluţie în multe cazuri, dar - ea singură - nu poate garanta obţinerea unei soluţii); remodelăm acest mecanism în C++ (cu elemente de C++11), experimentând nu numai pe graful calului, dar şi pe diverse alte grafuri.
Instituirea într-un program a unui obiect graf implică două etape distincte: definirea unui container în care să se poată înregistra adiacenţa vârfurilor şi respectiv, înregistrarea propriu-zisă a relaţiei de adiacenţă. Clasa de bază Graph alege un anumit tip ("Bin") de container şi se ocupă de alocarea şi dealocarea în memorie a acestuia - exportând metoda addEdge(), prin care utilizatorul (main(), sau altă funcţie din program) va putea înregistra adiacenţa dorită.
/** graph.h **/ #include <vector> typedef std::vector<int> Bin; // "dulap" pentru adiacenţii vârfului typedef Bin::iterator Bin_it; // referă iterativ adiacenţii vârfului class Graph { // graf neorientat, cu vârfurile 0..V-1 public: Graph(int V): V(V), adj(new Bin[V]) {} ~Graph() { delete [] adj; } bool isEdge(int, int); // testează existenţa muchiei void addEdge(int, int); // adaugă muchie, dacă nu există protected: // asigură claselor derivate, acces direct la date int V; // numărul de vârfuri Bin *adj; // adj[w] = lista adiacenţilor lui w, w=0..V-1 };
Utilizatorul nu are nevoie să cunoască natura containerului "Bin", dar pentru cazul claselor derivate ("utilizatori" de Graph) am prevăzut posibilitatea accesării directe a acestui container (specificându-l sub protected) - astfel că adiacenţa va putea fi setată apelând în constructorul clasei derivate o metodă proprie acesteia, după modelul Extensie(int n): Graph(n*n) {set_adj();}.
/** graph.cpp **/ #include "graph.h" #include <algorithm> // find() void Graph::addEdge(int v, int w) { if(! isEdge(v,w)) { adj[v].push_back(w); adj[w].push_back(v); } } bool Graph::isEdge(int v, int w) { return find(adj[v].begin(), adj[v].end(), w) != adj[v].end(); }
std::find() returnează un iterator ("pointer") pentru elementul căutat; diferenţa acestui iterator faţă de "begin()" va indica indexul elementului (în containerul respectiv).
Avem de specificat o metodă find_path(), pentru determinarea unui drum sau ciclu hamiltonian; metoda dump_path() va reda soluţia obţinută şi o prevedem virtual, asigurând claselor derivate posibilitatea de a o suprascrie după caz (permiţându-le în acest scop, acces direct la containerul "path" (prevăzut prin protected) în care este constituită soluţia).
/** hamilton.h **/ #include "graph.h" class Hamilton: public Graph { public: Hamilton(int n): Graph(n), path(n, 0), cont(0) {} void find_path(int start, bool cycle=false, int num_sol=1) { this->cycle = cycle; // ciclu, sau numai drum? (implicit - drum) this->num_sol = num_sol; // câte soluţii? (implicit - una) find_path(start, 1); // găseşte soluţii, plecând din nodul `start` } virtual void dump_path(bool); // redă traseul găsit (drum/ciclu) void reset(); // reiniţializare (path[]=0 şi cont=0) protected: Bin path; // ordinea pe traseu a vârfurilor (1..V) int cont; // contorizează soluţiile găsite private: bool cycle; int num_sol; int start(); // returnează vârful v pentru care path[v]=1 void find_path(int, int); // caută recursiv, drum/ciclu hamiltonian void reorder(Bin&); // reordonează adiacenţii unui nod };
Se exportă find_path(int start), care de fapt lansează metoda privată find_path(int, int) - cu doi parametri, al doilea menţinând adâncimea curentă pe parcursul căutării specifice mecanismului backtracking (utilizatorul nu are de ştiut că nodul de start este marcat cu 1, în path[]).
Prin această interfaţă, anticipăm următoarea manieră de lucru:
/* class Knight: public Hamilton {...; set_knight_adj(); } */ Knight K(6); // graful calulul de şah pe tabla 6x6 K.find_path(5); // un drum, cu nodul de start 5 (colţul dreapta-sus) K.reset(); // pregăteşte o nouă căutare, pe aceeaşi instanţă K K.find_path(20, true, 3); // trei cicluri, plecând de pe un câmp central
Clasele derivate vor putea folosi "cont" (acesta fiind protected), pentru a număra soluţiile.
/** hamilton.cpp **/ #include "hamilton.h" #include <iostream> #include <algorithm> // find(), fill(), sort() #include <unordered_map> // C++11 // identifică nodul de start (marcat 1, în path[]) al traseului int Hamilton::start() { return (find(path.begin(), path.end(), 1) - path.begin()); } void Hamilton::reset() { // pentru a relansa (cu alţi parametri) find_path() fill(path.begin(), path.end(), 0); // path[v] = 0, v=0..V-1 cont = 0; // reiniţializează contorul de soluţii } void Hamilton::find_path(int node, int depth) { // nodul şi adâncimea curente path[node] = depth; if(depth == V) { // dacă s-a trecut prin toate vârfurile if(cycle) { if(isEdge(node, start())) { // dacă 'node' este adiacent cu 'start' cont++; // contorizează soluţiile obţinute dump_path(true); // redă soluţia găsită (ciclu) } } else { cont++; dump_path(false); // redă soluţia găsită (drum) } } if(cont < num_sol) { // dacă s-au cerut mai multe soluţii reorder(adj[node]); // reordonează adiacenţii nodului curent (*) for(auto next: adj[node]) if(!path[next]) find_path(next, depth+1); // mecanismul backtracking path[node] = 0; // revine, pentru a încerca altă variantă } } // fără (*), am avea backtracking "curat" (fără euristică Warnsdorff) // ordonează adiacenţii nevizitaţi, după numărul adiacenţilor acestora nevizitaţi void Hamilton::reorder(Bin& neighbor) { std::unordered_map<int,int> wrn; // wrn[s] = numărul adiacenţilor lui s nevizitaţi for(auto s: neighbor) if(!path[s]) { // dacă nu s-a trecut anterior prin nodul s wrn[s] = 0; for(auto ps: adj[s]) // parcurge adiacenţii lui s if(! path[ps]) // contorizează adiacenţii nevizitaţi ai lui s wrn[s] ++; } else wrn[s] = 9; // nodurile vizitate anterior vor fi plasate la sfârşit sort(neighbor.begin(), neighbor.end(), // "lambda" - vezi C++11 [&](int i, int j)->bool {return wrn[i] < wrn[j];}); } void Hamilton::dump_path(bool cycle) { std::unordered_map<int,int> dp; // inversează path[]: dp[i] = al i-lea nod al traseului if(num_sol > 1) std::cout << cont << ". "; std::cout << (cycle? "Ciclu": "Drum") << " hamiltonian:\n"; for(int i=0; i < V; ++i) dp[path[i]] = i; for(auto idp: dp) std::cout << (idp.second + 1) << " "; // afişează cu 1..V, în loc de 0..V-1 std::cout << "\n"; }
find_path() găseşte traseul hamiltonian folosind bactraking în combinaţie cu o reordonare a adiacenţilor nodului curent (după numărul adiacenţilor nevizitaţi ai acestora); eliminând această reordonare (se comentează linia marcată mai sus cu "(*)" şi se recompilează) - soluţia va fi găsită într-un timp mult mai mare (faţă de cazul când păstrăm apelul reorder(adj[node]);).
Pentru ce n este posibilă o secvenţă circulară a numerelor 1..n, astfel încât suma oricăror doi termeni vecini să fie pătrat perfect? (OEIS /A071984)
Şirul cerut (un "ciclu pătratic") este un ciclu hamiltonian al grafului cu vârfurile 1..n în care avem câte o muchie pentru fiecare două valori a căror sumă este un pătrat perfect. Modelăm asemenea grafuri ("Square"), derivând din clasa "Hamilton" (constituită mai sus):
/** square.cpp **/ #include "hamilton.h" #include <cmath> bool is_square(int n) { // stabileşte dacă n este pătrat perfect int h = n & 0xF; // ultima cifră hexazecimală switch(h) { // în hexazecimal, pătratele se termină cu 0, 1, 4, sau 9 (25=0x19) case 0: case 1: case 4: case 9: int t = static_cast<int>(floor(sqrt(static_cast<double>(n)) + 0.5)); return t*t == n; } return false; } class Square: public Hamilton { public: Square(int n): Hamilton(n) { square_loop(); } private: void square_loop() { // i+j=pătrat perfect (i,j=1..V) for(int i=1; i < V; ++i) for(int j=i+1; j <= V; ++j) if(is_square(i+j)) // dacă i+j este pătrat perfect, addEdge(i-1, j-1); // atunci instituim muchia [i-1, j-1] } }; #include <cstdlib> // atoi() #include <iostream> int main(int argc, char** argv) { int n = argc > 1? atoi(argv[1]): 41; // h-minim pentru care 1..h admite un "ciclu pătratic" for(int h=4; h < n; h++) { std::cout << h << ": "; Square S(h); S.find_path(0, true); // caută un ciclu hamiltonian (**) } }
Compilând şi executând, vedem că pentru h < 32 nu există cicluri pătratice, iar pentru h = 32 (sau mai mare) obţinem un astfel de ciclu:
vb@vb:~/KNIGHT$ g++ --std=gnu++0x -O2 -o square square.cpp hamilton.cpp graph.cpp
vb@vb:~/KNIGHT$ ./square
4: 5: 6: 7: 8: /* ... */ 31: 32: Ciclu hamiltonian:
1 8 28 21 4 32 17 19 30 6 3 13 12 24 25 11 5 31 18 7 29 20 16 9 27 22 14 2 23 26 10 15
Nu a fost cazul să redefinim (în "Square") metoda dump_path(), încât pentru afişarea ciclului s-a invocat metoda din clasa de bază, Hamilton::dump_path().
Dar oare există măcar drumuri pătratice (nu cicluri), pentru h < 32? Înlocuind în funcţia main() linia marcată (**) cu S.find_path(0) găsim (recompilând şi apoi executând programul) că pentru h = 27..31 există "drumuri pătratice", plecând din 1:
vb@vb:~/KNIGHT$ ./square 32
4: 5: 6: 7: 8: /* ... */ 26: 27: Drum hamiltonian:
1 8 17 19 6 3 13 12 24 25 11 14 22 27 9 16 20 5 4 21 15 10 26 23 2 7 18
28: Drum hamiltonian:
1 15 10 26 23 13 3 6 19 17 8 28 21 4 12 24 25 11 5 20 16 9 27 22 14 2 7 18
29: Drum hamiltonian:
1 24 25 11 5 4 12 13 3 6 19 17 8 28 21 15 10 26 23 2 14 22 27 9 16 20 29 7 18
30: Drum hamiltonian:
1 24 25 11 5 4 12 13 3 6 30 19 17 8 28 21 15 10 26 23 2 14 22 27 9 16 20 29 7 18
31: Drum hamiltonian:
1 15 10 26 23 13 12 24 25 11 14 2 7 29 20 16 9 27 22 3 6 30 19 17 8 28 21 4 5 31 18
Dar poate (pentru h < 27) există drumuri pătratice plecând dintr-un alt nod (decât 1)? Reformulând secvenţa "for" din funcţia main() astfel:
for(int h=4; h < n; h++) {
Square S(h);
std::cout << h << ": ";
for(int i=1; i < h; i++) {
S.find_path(i); // caută un drum hamiltonian, cu start=i (1..h)
S.reset();
}
}
constatăm (după recompilare şi execuţie) că pentru h < 15 nu există nici un drum pătratic; pentru h = 15, 16, 17 există câte un singur astfel de drum (plecând respectiv din 8, 8, 16):
vb@vb:~/KNIGHT$ ./square 27
4: 5: 6: 7: 8: /* ... */ 14: 15: Drum hamiltonian:
8 1 15 10 6 3 13 12 4 5 11 14 2 7 9
16: Drum hamiltonian:
8 1 15 10 6 3 13 12 4 5 11 14 2 7 9 16
17: Drum hamiltonian:
16 9 7 2 14 11 5 4 12 13 3 6 10 15 1 8 17
Apoi, pentru h = 18..22 nu există nici un drum pătratic (indiferent ce nod am lua ca start), iar pentru h = 23..26 găsim în fiecare caz, mai multe astfel de drumuri.
Cu o funcţie main() precum următoarea:
int main(int argc, char** argv) { int n = argc > 1? atoi(argv[1]): 51; Square S(n); S.find_path(0, true); }
putem constata efectul reordonării Warnsdorff a adiacenţilor nodului curent, în contextul curent de lucru al metodei find_path(). Astfel, păstrând linia reorder(adj[node]); marcată (*) în "hamilton.cpp" - obţinem instantaneu:
vb@vb:~/KNIGHT$ time ./square 51 Ciclu hamiltonian: 1 48 16 33 31 50 14 35 29 20 44 5 11 25 24 40 9 27 37 12 4 32 49 51 13 36 45 19 17 47 34 30 6 43 38 26 10 39 42 22 3 46 18 7 2 23 41 8 28 21 15 real 0m0.014s vb@vb:~/KNIGHT$ time ./square 52 Ciclu hamiltonian: 1 8 28 36 45 19 17 32 49 51 30 6 43 21 4 5 44 20 16 48 33 31 50 14 11 38 26 10 15 34 47 2 7 18 46 35 29 52 12 37 27 9 40 41 23 13 3 22 42 39 25 24 real 0m0.010s
iar timpul de furnizare a soluţiei rămâne acceptabil (sub 1 minut) şi pentru valori mai mari:
vb@vb:~/KNIGHT$ time ./square 100 Ciclu hamiltonian: 1 63 81 88 56 65 35 86 58 42 79 90 54 67 14 50 94 27 37 84 85 36 64 80 89 32 68 53 91 78 22 59 41 40 60 61 83 17 8 28 72 9 16 20 44 77 92 29 52 48 33 31 18 46 3 97 99 45 55 66 15 49 95 5 76 93 7 57 43 21 100 69 75 6 19 62 82 87 34 47 2 98 23 13 51 30 70 74 26 38 11 25 39 10 71 73 96 4 12 24 real 0m45.700s
În schimb, dacă eliminăm linia (*) menţionată mai sus (apoi recompilăm şi executăm) vom obţine rezultatele într-un timp mult mai mare (de mii de ori, mai mare):
vb@vb:~/KNIGHT$ time ./square 51 Ciclu hamiltonian: 1 3 6 10 15 21 43 38 26 23 2 7 9 27 22 42 39 25 24 40 41 8 28 36 13 51 49 32 17 47 34 30 19 45 4 12 37 44 5 11 14 50 31 18 46 35 29 20 16 33 48 real 0m23.233s (faţă de 0m0.014s obţinut folosind reordonarea Warnsdorff) vb@vb:~/clasa11/OOP/KNIGHT$ time ./square 52 Ciclu hamiltonian: 1 3 6 10 15 21 43 38 26 23 2 7 9 16 33 48 52 12 37 27 22 42 39 25 11 14 50 31 18 46 35 29 20 44 5 4 45 19 30 34 47 17 32 49 51 13 36 28 8 41 40 24 real 1m16.638s (faţă de 0m0.010s obţinut folosind reordonarea)
Operând şi reordonarea Warnsdorff (din linia (*)), pentru foarte multe valori probate n = 100..1000 - timpul de obţinere a ciclului pătratic este de ordinul zecimilor de secundă. Pentru n = 2015, 4000, 8000, 10000 şi multe alte valori cu ordinul de mărime al miilor - rezultatul s-a obţinut în cel mult două-trei secunde; în schimb, pentru n = 100 timpul a fost de 45 secunde (cum am relevat mai sus), iar pentru n = 300 (şi pentru diverse alte valori) - n-am obţinut un rezultat nici după o oră…
Pentru n = 300 am obţinut totuşi un ciclu pătratic chiar în mai puţin de 1 zecime de secundă, folosind însă find_path(2, true) - adică indicând 3 ca start, în loc de 1:
vb@vb:~/KNIGHT$ time ./square 300 Ciclu hamiltonian: 3 222 262 267 174 226 258 271 170 230 299 277 207 154 135 265 219 142 182 179 221 263 178 183 217 224 176 185 215 269 260 181 180 220 264 177 147 253 231 298 102 259 141 300 276 208 233 296 104 257 184 140 85 84 172 228 256 144 145 216 225 136 188 101 223 261 268 173 227 214 270 171 153 288 112 212 229 255 186 103 297 187 213 111 289 72 97 128 272 169 192 132 124 200 56 25 96 100 189 252 148 108 292 69 52 237 204 196 93 28 36 64 105 295 146 254 275 49 120 241 48 33 16 240 121 75 249 280 161 163 278 83 61 60 109 116 284 245 239 17 152 44 20 149 175 266 95 130 39 157 68 32 137 88 273 168 193 291 150 211 113 143 218 106 294 67 77 119 205 51 13 12 37 287 242 82 279 250 234 127 129 232 209 47 53 236 248 76 24 40 156 285 244 80 281 8 41 23 98 191 293 107 89 235 165 4 21 15 1 195 94 131 65 160 164 92 197 203 158 166 59 5 139 117 283 201 123 133 11 38 251 73 27 9 55 45 99 22 122 74 26 199 125 71 29 167 274 50 14 35 86 110 115 81 63 162 238 246 43 57 87 34 66 78 91 30 70 126 18 31 90 54 46 243 118 138 151 290 286 155 206 19 62 194 2 79 210 114 247 282 7 42 58 198 202 159 10 134 190 6 real 0m0.090s
Desigur, putem reformula ciclul, încât să înceapă totuşi din 1 şi nu din 3 - citim începând de la 1: 1, 195, 94, ..., 134, 190, 6 şi apoi continuăm de la începutul secvenţei de mai sus: 3, 222, ..., 4, 21, 15.
Este greu de lămurit de ce se petrec lucrurile aşa cum am evidenţiat mai sus… Dar am verificat pe mai multe cazuri 100..10000, că putem proceda la fel ca în cazul n=300: avem cel puţin o alegere pentru nodul de start, astfel încât ciclul pătratic demarat din acest nod să se obţină prin programul de mai sus în mai puţin de 3 secunde.
De exemplu, pentru n = 100 - plecând din ultimul nod, avem rezultatul în 2 secunde:
vb@vb:~/clasa11/OOP/KNIGHT$ time ./square 100 Ciclu hamiltonian: 100 69 52 92 29 71 50 94 75 25 96 73 48 16 65 56 88 33 31 90 79 42 39 82 18 46 98 2 62 38 83 61 20 44 77 67 54 10 26 23 58 86 35 14 11 89 55 66 34 87 57 7 74 95 5 59 41 80 64 17 8 1 63 81 19 6 43 78 3 22 27 37 84 85 15 49 32 68 53 47 97 99 70 30 91 9 72 28 36 13 51 93 76 45 4 12 24 40 60 21 real 0m2.055s (faţă de 0m45.700s cu start = 1 - vezi mai sus)
Cum am ales să demarăm find_path() din ultimul nod? Am listat în prealabil gradele vârfurilor, constatând că şirul gradelor are tendinţă descrescătoare: pentru n=100, primele vârfuri au gradele 9, 8, 9, 8, 8; vârfurile 8..15 au gradul 7 şi gradele descresc (cu rare excepţii) în continuare; apoi, vârfurile 81..95 au gradul 4, iar ultimele vârfuri au gradele 5, 5, 4, 5, 4.
În principiu, cel mai avantajos pare a fi demararea căutării repetate începând din nodul de grad minim (în ideea de a evita blocajele în momente îndepărtate - caz în care va trebui să reluăm dintr-un nod anterior şi cel mai convenabil este ca acesta să aibă cât mai puţine ramificaţii); dar acest principiu (în baza căruia am ales ca start, ultimul nod) nu este nici el, infailibil…
Să vedem şi pentru graful calului de şah, ce posibilităţi (şi limite) apar prin construcţia "Hamilton" de mai sus, pentru a determina un drum sau un ciclu hamiltonian (şi poate, să numărăm câte drumuri sunt), de pe un câmp de start sau altul, pe tabla de şah de diverse dimensiuni (vezi şi [1]).
Tablei de dimensiune N trebuie să-i asociem un graf - un obiect Hamilton() - cu NxN vârfuri, a cărui matrice de adiacenţă să corespundă săriturilor calului de şah:
/** knight.h **/ #include "hamilton.h" class Knight: public Hamilton { // graful calului de şah public: Knight(int n): Hamilton(n*n), size(n) { knight_adj(); } void dump_path(bool); // redă traseul sub forma unei table de şah private: int size; // dimensiunea tablei (utilizat în dump_path()) void knight_adj(); // instituie adiacenţa săriturilor calului de şah };
Câmpurile tablei sunt indexate cu 0..NxN-1, linie după linie de sus în jos şi pe fiecare linie, de la stânga spre dreapta.
/** knight.cpp **/ #include "knight.h" #include <iostream> void Knight::knight_adj() { // adiacenţa săriturilor calului pe tabla de şah int n = size; int jump[][2] = {{-1,2}, {1,2}, {-2,1}, {2,1}, {-1,-2}, {1,-2}, {-2,-1}, {2,-1}}; for(int row=0; row < n; ++row) for(int col=0; col < n; ++col) { int from = n*row + col; // indexul câmpului aflat pe linia i şi coloana j for(int k=0; k < 8; k++) { int to_row = row + jump[k][0]; // linia câmpului pe care sare calul if((to_row >= 0) && (to_row < n)) { int to_col = col + jump[k][1]; // coloana câmpului destinaţie if((to_col >= 0) && (to_col < n)) { addEdge(from, n*to_row + to_col); } } } } } // Rescrie Hamilton::dump_path(), pentru a reda traseul hamiltonian sub forma tablei de şah void Knight::dump_path(bool cycle) { std::cout << cont << (cycle? " (ciclu": " (drum") << " hamiltonian):\n"; for(int i=0; i < V; i += size) { // path[], câte 'size' linii a câte 'size' valori for(int j=0; j < size; ++j) std::cout << path[i+j] << '\t'; std::cout << "\n\n"; } std::cout << "\n\n"; }
Pentru cazul când ne-ar interesa numărul de soluţii (şi nu soluţiile ca atare), vom putea considera o clasă derivată din "Knight" în cadrul căreia să redefinim dump_path() { num_sol++; }, "num_sol" fiind iniţializată cu 0 în constructorul acestei clase (sau printr-o nouă metodă adăugată ei).
Următorul "main()" ne poate servi pentru testarea construcţiilor de mai sus:
#include "knight.h" #include <cstdlib> // atoi() int main(int argc, char** argv) { int n = argc > 1? atoi(argv[1]): 6; // implicit: tabla 6x6 int start = argc > 2? atoi(argv[2]): 0; // implicit: colţul stânga-sus Knight K(n); // instanţiază graful calului pe tabla nxn K.find_path(start); // drum, plecând din nodul `start` K.reset(); // pregăteşte căutarea unui nou traseu (pe aceeaşi "tablă") K.find_path(start, true); // caută un ciclu hamiltonian }
În general, un drum hamiltonian va rezulta mult mai rapid, decât un ciclu - iar aceasta depinde (mai ales pentru ciclu) de câmpul prevăzut ca iniţial (şi eventual, de dimensiunea tablei).
vb@vb:~/KNIGHT$ time ./knight 6 de pe câmpul 1 şi apoi, de pe un câmp central
1 (drum hamiltonian): 1 (ciclu hamiltonian): 1 (ciclu hamiltonian):
1 28 9 20 3 30 1 28 15 12 3 34 8 31 10 27 6 33
10 21 2 29 16 19 16 11 2 35 22 13 11 20 7 32 17 26
35 8 27 18 31 4 27 36 29 14 33 4 30 9 28 19 34 5
22 11 34 15 26 17 10 17 8 23 30 21 21 12 1 16 25 18
7 36 13 24 5 32 7 26 19 32 5 24 2 29 14 23 4 35
12 23 6 33 14 25 18 9 6 25 20 31 13 22 3 36 15 24
real 2m8.502s real 0m0.020s
Avem aici, pe tabla de şah de numai 6x6 - drumul din colţul stânga-sus (obţinut instantaneu) şi ciclurile startate din colţ (după două minute) şi respectiv, de pe un câmp central (0.02 secunde).
Pentru tabla 8x8 (şi în diverse alte cazuri), indicând ca start colţul stânga-sus - n-am avut şansa să obţinem un ciclu, nici după minute bune de timp; dar indicând ca start vreun alt câmp (preferabil - dintre cele apropiate de centrul tablei), ciclul rezultă într-un timp infim:
vb@vb:~/KNIGHT$ time ./knight 8 20 vb@vb:~/KNIGHT$ time ./knight 10 25
1 (ciclu hamiltonian): 1 (ciclu hamiltonian):
39 20 17 2 41 30 15 32 44 41 26 33 2 39 28 9 4 7
18 3 40 35 16 33 42 29 25 34 43 40 27 32 3 6 29 10
21 38 19 58 1 44 31 14 42 45 62 35 48 1 38 31 8 5
4 57 36 45 34 63 28 43 63 24 47 60 65 36 49 56 11 30
37 22 53 64 59 46 13 48 46 61 64 67100 59 54 37 50 57
8 5 56 51 54 49 62 27 23 68 83 88 75 66 95 58 55 12
23 52 7 10 25 60 47 12 84 89 74 99 82 93 76 53 80 51
6 9 24 55 50 11 26 61 69 22 87 92 73 96 81 94 13 16
real 0m0.006s 90 85 20 71 98 77 18 15 52 79
21 70 91 86 19 72 97 78 17 14
real 0m0.006s
Alte exemple, cu rezultate temporale similare celor de mai sus: ./knight 12 28, ./knight 14 70. Dar pe table mai mari decât 14x14, reuşim foarte rar să nimerim un nod de start de pe care obţinerea unui ciclu să decurgă într-un timp rezonabil.
Renunţând la ultimele două linii din main()-ul de mai sus, putem investiga mai comod obţinerea de drumuri hamiltoniene pe table mai mari. Pentru n < 30 drumul (din colţul stânga-sus) rezultă în timpi de ordinul sutimilor de secundă, iar pentru n = 30 se obţine astfel doar dacă indicăm un alt nod de start, decât colţul stânga-sus. Am verificat că obţinem un drum hamiltonian (cu timpi de până la 1-2 secunde) pentru n < 305, schimbând însă în unele cazuri, nodul de start (pentru 30 < n < 100 avem numai 16 astfel de cazuri).
În modelul nostru, colţul stânga-sus are indexul 0; câmpurile pare sunt "albe", iar cele impare sunt "negre". Calul sare de pe alb pe negru, sau invers; ca urmare, în oricare drum cu număr impar de vârfuri, câmpul iniţial şi cel final au aceeaşi culoare (deci primul şi ultimul vârf al drumului nu sunt adiacente). Rezultă că pe graful calului de ordin impar nu există cicluri hamiltoniene; în plus, nu există drumuri hamiltoniene care să plece de pe un câmp negru (s-ar încheia pe un câmp negru, ori acestea sunt în număr mai mic cu 1, decât cele albe).
Am putea eventual, verifica: ./knight 5 1 se încheie după 2 secunde fără să afişeze vreun rezultat - ceea ce înseamnă că într-adevăr, pe tabla 5x5 nu există nici un drum hamiltonian care să plece de pe câmpul 1 (care este "negru"). Dar nu prea are sens să încercăm aceasta şi pe table mai mari: ./knight 7 1 determină explorarea tuturor posibilităţilor de prelungire a drumurilor parţiale startate de pe câmpul 1 - ori socotind că în medie am avea 5 adiacenţi de câmp, numărul încercărilor ar fi de ordinul 548 (imens - are peste 30 de cifre zecimale).
Instituim prin derivare din "Knight", o clasă care să permită aflarea numărului de drumuri:
#include "knight.h" #include <iostream> class Knight_: public Knight { public: Knight_(int n): Knight(n) {num_sol = 0;} void dump_path(bool cycle) { // Hamilton::dump_path(false); // (eventual) afişează fiecare drum num_sol++; } void get_sol() { std::cout << num_sol; num_sol = 0; } private: int num_sol; // numărul de soluţii dintr-un nod iniţial dat }; // numărul drumurilor hamiltoniene pe tabla 5x5 int main() { int max_sol = 305; // 1000 Knight_ K(5); for(int field = 0; field < 25; field += 2) { // numai de pe câmpuri pare (albe) K.find_path(field, false, max_sol); // drumurile calului, de pe câmpul dat std::cout << (field+1) << ": "; K.get_sol(); // Numărul de drumuri hamiltoniene din acel nod std::cout << '\n'; K.reset(); } }
Desigur, puteam ţine seama de simetriile existente, reducând numărul câmpurilor pentru care să apelăm K.find_path() (e clar de exemplu, că din fiecare colţ al tablei vom găsi acelaşi număr de drumuri): era suficient să considerăm colţul 0, câmpul central 12 şi câmpurile 2 şi 6.
Redăm rezultatul (obţinut în circa 20 de secunde), în formatul tablei de şah:
vb@vb:~/KNIGHT$ ./knight5
0: 304 2: 56 4: 304
6: 56 8: 56
10: 56 12: 64 14: 56
16: 56 18: 56
20: 304 22: 56 24: 304
Rezultă că pe graful calului 5x5 avem un număr de 4*304 + 8*56 + 64 = 1728 drumuri hamiltoniene, ceea ce corespunde cu valoarea dată de OEIS /A165134.
Teoretic, am avea cam de 5 ori mai mari şanse de a nimeri un drum hamiltonian plecând dintr-un colţ (304/1728), decât plecând de pe oricare alt câmp. Colţurile sunt într-adevăr "avantajate": pe graful calului 5x5, orice drum hamiltonian începe sau se termină într-un colţ (observaţie făcută de Euler şi posibil de verificat prin listarea celor 1728 de drumuri).
De fapt, valoarea 1728 poate fi "amendată", dacă privim drumurile ca subgrafuri (nu ca succesiuni ordonate de vârfuri): fiecare drum care pleacă dintr-un colţ şi se încheie în nodul X (colţ sau nu), se va regăsi în ordine inversă între drumurile care pleacă din nodul X; prin urmare, avem 1728/2 = 864 de drumuri hamiltoniene distincte ca subgrafuri.
Decomentând linia Hamilton::dump_path() în programul de mai sus (recompilând şi executând cu redirectare la un fişier text), vom obţine şi cele 1728 de drumuri:
1. Drum hamiltonian: // primul dintre cele 304 care pleacă din colţul 0 1 8 5 14 25 18 21 12 3 10 19 22 11 2 9 20 23 16 7 4 15 24 13 6 17 // nod final: 16 /* ... */ 55. Drum hamiltonian: // al 55-lea dintre cele 56 care pleacă de pe câmpul 16 17 6 13 24 15 4 7 16 23 20 9 2 11 22 19 10 3 12 21 18 25 14 5 8 1 /* ... */
Cele două drumuri redate aici sunt inverse unul altuia (ca grafuri parţiale, ele coincid), iar cele 56 de drumuri care pleacă de pe câmpul 16 sunt inversele a câte 14 drumuri originate din câte un colţ al tablei (analog, pentru celelalte câmpuri).
vezi Cărţile mele (de programare)