Travelling Salesman via dynamic programming

Maksym Bortin 📧

September 24, 2026

Abstract

Travelling Salesman Problem (TSP) is well-known to be NP-hard. The computational solution, derived in this theory, follows the Bellman-Held-Karp approach utilising the power set of locations to be visited by the salesman.

License

GNU Lesser General Public License (LGPL)

Topics

Related publications

Session TSP_Dyn_Prog

Cite

× 
@article{TSP_Dyn_Prog-AFP,
  author  = {Maksym Bortin},
  title   = {Travelling Salesman via dynamic programming},
  journal = {Archive of Formal Proofs},
  month   = {September},
  year    = {2026},
  note    = {\url{https://isa-afp.org/entries/TSP_Dyn_Prog.html},
             Formal proof development},
  ISSN    = {2150-914x},
}
Download