Ideea care duce la rezolvarea ce obţine $100$ de puncte se bazează pe urmatoarea 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 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.

Menţionăm că problema determinării unui ciclu hamiltonian este $NP$-completă şi, deci, nu se cunoaşte până în prezent nici un algoritm în timp polinomial care să rezolve problema. 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.

Menţionăm că problema determinării unui ciclu hamiltonian 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.

h2. Aplicaţii