Se observă că soluţia prezentată anterior nu verifică existenţa arcelor decât când întreaga permutare este generată. Această verificare se poate face în timpul generării permutării şi astfel se poate îmbunătăţi timpul de rulare. Această abordare se poate implementa şi sub forma unei 'parcurgeri în adâncime':problema/dfs care generează toate lanţurile din graf; în cazul în care se determină un lanţ cu $N$ noduri este verificată condiţia de închidere a ciclului (adică dacă există arcul dintre ultimul nod din lanţ şi nodul de start). În caz afirmativ, se verifică dacă ciclul găsit are un cost mai mic decât soluţia curentă. Acestă abordare are tot complexitate $O(N!)$, dar timpul de rulare este mai bun. O implementare a acestui algoritm se găseşte 'aici':job_detail/381246?action=view-source şi obţine $40$ de puncte.

O îmbunătăţire a complexităţii se poate obţine folosind metoda programării dinamice. Vom considera matricea $C$ având următoarea semnificaţie $C[i][j][k]=$ costul minim al unui lanţ ce începe în nodul $i$ se termină în nodul $k$ şi conţine toate nodurile identificate cu $1$ în configuraţia binară a lui $j$ exact o singură dată. De exemplu, pentru graful din enunţ, starea caracterizată de tripletul $(4, 23, 0)$ va avea valoarea $7$ şi va reprezenta costul minim al unui lanţ ce începe în nodul $4$, se termină în nodul $0$ şi conţine exact o singură dată nodurile ${0, 1, 2, 4}$, deoarece $23 = (10111){~2~}$ (ordinea biţilor este considerată cea inversă scrierii în baza $2$). Lanţul corespunzător acestei stări este $4 1 2 0$. Recurenţa este $C[i][j][k] = min{C[i][j xor 2^k^}][v] + Cost[v][k]}$, unde $v$ este un nod al cărui bit corespunzător din $j$ este $1$ şi care are un arc spre $k$, iar $Cost[v][k]$ reprezintă costul arcului respectiv. Complexitatea timp a acestei rezolvări este $O(M*N*2^N^)$. Din punctul de vedere al complexităţii memorie, se observă că indicele $i$ este inutil, deoarece în recurenţă acesta nu se modifică şi poate fi fixat anterior. Astfel se poate obţine o complexite memorie $O(N*2^N^)$. O implementare a acestei idei poate fi studiată 'aici':job_detail/381247?action=view-source şi obţine $70$ de puncte.
 

h2. Aplicaţii
Pentru a vă consolida cunoştinţele privind algoritmul prezentat in această problemă, vă recomandăm să rezolvaţi următoarele probleme:
* 'Segmente':problema/seg

* 'Morcovi':problema/morcovi
* 'Gather':problema/gather

* 'Bibel':problema/bibel

* 'Gather':problema/gather

* 'ADN':problema/adn
* "PermRLE":http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtchALEghjb250ZXN0cxiL4AYM, _Google Codejam 2008_
* "Yet Another Palindrome":http://acm.sgu.ru/problem.php?contest=0&problem=327, _SGU_
* 'Santa':problema/santa

Dacă doriţi să vă consolidaţi cunoştinţele privind programarea dinamică cu număr exponenţial de stări, puteţi încerca să rezolvaţi una din problemele următoare:
 
* 'Morcovi':problema/morcovi
* 'Ture':problema/ture
* 'Sobo':problema/sobo
* 'Pavare':problema/pavare
* 'Choco':problema/choco
 

== include(page="template/taskfooter" task_id="hamilton") ==