Dinamică pe stări exponențiale

Determinarea unui ciclu hamiltonian într-un graf este o cerință ce poate fi rezolvată doar cu algoritmi ce au grad de complexitate exponențial.

În aceste cazuri rezolvările sunt practice doar pe structuri de dimensiuni mici, deci este foarte important să optimizăm cât mai bine algoritmii.

Programarea dinamică folosind stări exponențiale oferă la această problemă o soluție mai bună decât un algoritm backtracking.