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]$ este 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. La început, $C[i][2^i^][i] = 0$, iniţilizând astfel orice lanţ format dintr-un singur nod cu costul $0$. Soluţia problemei este $min{C[i][2^N^-1][j] + Cost[j][i]}$, unde $j$ este un nod dinspre care porneşte un arc spre $i$, deoarecere $2^N^-1 = (111...11){~2~}$. Complexitatea timp a acestei rezolvări este $O(M*N*2^N^)$. Din punctul de vedere al complexităţii spaţiu, 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 spaţiu $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.
Ideea care duce la rezolvarea ce obţine $100$ de puncte se bazează pe următoarea observaţie: deoarece ne propunem să obţinem un ciclu care conţine toate nodurile, nu este relevant nodul de start şi, deci, se poate fixa orice nod ca nod de început. Astfel, indicele $i$ din dinamica prezentată mai sus devine complet inutil. Complexitatea timp devine astfel $O(M*2^N^)$. Această idee poate fi implementată 'în mod clasic':job_detail/381244?action=view-source sau 'folosind memoizare':job_detail/381239?action=view-source. Memoizarea este o tehnică specifică programării dinamice bazată pe o funcţie recursivă cu ajutorul căreia se calculează doar stările necesare pentru obţinerea rezultatului (se ignoră astfel stările invalide sau inutile). Conceptul este simplu: în recurenţă se apelează aceeaşi funcţie pentru noua stare, iar valoarea este calculată doar dacă nu a mai fost calculată în prealabil. Această tehnică produce deseori timpi de rulare mai buni, fapt ce poate fi observat şi comparând cele două implementări de mai sus.
Ideea care duce la rezolvarea ce obţine $100$ de puncte se bazează pe următoarea observaţie: deoarece ne propunem să obţinem un ciclu care conţine toate nodurile, nu este relevant nodul de start şi, deci, se poate fixa orice nod ca nod de început. Astfel, indicele $i$ din dinamica prezentată mai sus devine complet inutil. Complexitatea timp devine astfel $O(M*2^N^)$. Această idee poate fi implementată 'în mod clasic':job_detail/381390?action=view-source sau 'folosind memoizare':job_detail/381349?action=view-source. Memoizarea este o tehnică specifică programării dinamice bazată pe o funcţie recursivă cu ajutorul căreia se calculează doar stările necesare pentru obţinerea rezultatului (se ignoră astfel stările invalide sau inutile). Conceptul este simplu: în recurenţă se apelează aceeaşi funcţie pentru noua stare, iar valoarea este calculată doar dacă nu a mai fost calculată în prealabil. Această tehnică produce deseori timpi de rulare mai buni, fapt ce poate fi observat şi comparând cele două implementări de mai sus.
Menţionăm că problema determinării unui ciclu hamiltonian (de cost minim) este $NP$-completă şi, deci, nu se cunoaşte, până în prezent, nici un algoritm care să rezolve problema în timp polinomial. Cu toate acestea, există câteva tipuri de grafuri particulare pentru care există un astfel de algoritm polinomial. Unul dintre aceste cazuri este tratat într-un articol prezent pe infoarena, 'Ciclu hamiltonian într-un graf dens':ciclu-hamiltonian-in-graf-dens.
