Într-un articol mai vechi am prezentat problema comis-voiajorului și rezolvarea ei prin backtracking. Totuși, pentru date de intrare mici (numărul de noduri sub 20), există o soluție mai eficientă, bazată pe programare dinamică. Tehnica folosită se numește dinamică pe stări exponențiale, sau dinamică pe configurații. În continuare, vom avea în vedere restricțiile din problema Ciclu hamiltonian de cost minim de pe InfoArena.

Enunț

Se dă un graf orientat ponderat cu n ≤ 18 vârfuri (indexate de la 0) și m arce. Fiecare arc (i, j) are asociat un cost ad[i][j]. Să se determine un ciclu hamiltonian de cost minim în acest graf, sau să se afișeze "Nu exista solutie" dacă graful nu este hamiltonian. Fiind vorba despre un graf orientat, corect ar fi să spunem circuit hamiltonian, dar voi păstra formularea de pe InfoArena.

Soluție prin programare dinamică

Faptul că numărul de noduri este foarte mic (maxim 18) ne duce cu gândul că probabil o soluție exponențială se va încadra în timp. Dacă ați mai rezolvat până acum vreo problemă de dinamică pe stări exponențiale, sau dacă vă pricepeți la programare dinamică în general, probabil că deja v-ați prins cum arată subproblemele. Dacă nu, veți afla acum tehnica prin care se abordează o astfel de problemă.

Formularea subproblemelor

Dinamica va fi dp[mask][i] = costul minim al unui drum ce vizitează exact o singură dată fiecare nod din submulțimea mask, care începe din nodul 0, și se termină în nodul i, sau $\infty$ în caz că nu există un astfel de drum. Veți afla mai încolo de ce am fixat începutul drumului în 0. Parametrul mask este o mască de biți ce codifică o submulțime de noduri ale grafului: Bitul k este setat la 1 dacă și numai dacă nodul k face parte din submulțimea respectivă.

Găsirea relației de recurență

Acum că am formulat subproblema, este relativ simplu să deducem recurența. Dacă drumul se termină în nodul i, cu siguranță penultimul nod din componența drumului va fi un nod j pentru care există arcul (j, i). Evident, costul minim al unui drum optim pentru submulțimea mask ce se termină în j, i este egal cu costul minim al unui drum optim pentru submulțimea mask ^ (1 << i), la care se adaugă costul arcului (j, i), adică ad[j][i]. (Prin mask ^ (1 << i) se codifică submulțimea obținută eliminându-l pe i din mask. Este echivalent cu mask - (1 << i).) Calculăm această valoare pentru fiecare j posibil, și alegem minimul dintre ele, recurența fiind:

$$\mathrm{dp}[mask][i] = \min_{\forall j, \exists (j, i)} \left\{\mathrm{dp}[mask - 2^i][j] + \mathrm{ad}[j][i]\right\}$$

Folosirea rezultatelor

După ce am calculat dinamica, mai avem de făcut ceva pentru a ajunge la soluție. În dp[(1 << n) - 1][i] avem costul minim al unui drum hamiltonian pentru întregul graf. Pentru a-l transforma în ciclu, mai rămâne să-i adăugăm la final arcul (i, 0). Acum se poate vedea de ce am fixat nodul de start în 0. Dacă n-ar fi fost fixat, n-am fi știut ce arc să adăugăm pentru a forma ciclu, așa că ar fi trebuit să mai avem o dimensiune la dinamică – nodul de start. Însă, acesta poate fi ales de la început, deoarece ciclul final oricum trebuie să conțină toate nodurile. Așadar, rezultatul problemei va fi dat de:

$$\mathrm{sol} = \min_{0 \le i \lt n} \left\{\mathrm{dp}[2^n - 1][i] + \mathrm{ad}[i][0]\right\}$$

Dacă am obținut $\infty$, înseamnă că nu există soluție.

Implementare în C++

Câteva detalii de implementare: În in[i] am reținut o listă cu nodurile j pentru care există arcul (j, i), iar în ad[i][j] costul arcului (i, j). Am avut nevoie și de liste și de matrice de adiacență pentru a putea parcurge vecinii unui nod eficient, dar și ca să accesez ad[i][0] în $O(1)$.

Pentru calcularea stărilor dinamicii, am început cu cazul de bază (dp[1][0] = 0), iar pe restul submulțimilor le-am parcurs din 2 în 2, pentru că submulțimile care nu au bitul 0 setat la 1 nu sunt valide. Infinitul l-am reprezentat prin constanta 1e9, care este suficient de mare pentru problema noastră.

Complexitate

Se vede clar că numărul de stări ale dinamicii crește exponențial din cauza numărului de submulțimi ale nodurilor. De aici și numele de programare dinamică pe stări exponențiale. Complexitatea în spațiu a algoritmului este $O(n \cdot 2^n)$.

Timpul de calculare a unei stări dp[mask][i] este egal cu numărul de noduri j ce „intră” în i. Astfel, timpul necesar pentru calcularea tuturor stărilor ce îl au ca prim parametru pe mask se amortizează la $O(m)$. Deci, complexitatea în timp a algoritmului este $O(m \cdot 2^n)$.

Probleme recomandate

Problemele recomandate nu sunt legate tocmai de problema comis-voiajorului, dar se folosesc de conceptul de programare dinamică pe stări exponențiale. Cea mai interesantă mi se pare problema Pavare, pentru că îmbină backtracking-ul cu dinamica. Pe lângă aceste probleme, un exercițiu bun este să vă gândiți cum se poate reconstitui soluția având deja calculată matricea dp. Dacă aveți vreo întrebare despre această tehnică de programare dinamică, o puteți lăsa într-un comentariu mai jos 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!