Show HN: Interactive visual solver for the traveling salesman problem

Re:Show HN: Interactive visual solver for the traveling sale... by jdmg718 on Wednesday October 16, 2019 @10:36AM (#21270809)

I've been thinking about this problem for a while with a little twist. What if you wanted to run/walk all the streets in your city? What is the shortest path to do it? How do you calculate the number of kilometers of streets in a city?

[ Parent | on HN ]

Re:Show HN: Interactive visual solver for the traveling sale... by hxhxhrra on Wednesday October 16, 2019 @02:21PM (#21273612)

This problem is called Chinese Postman Problem and can be solved in polynomial time using matching algorithms:

https://en.m.wikipedia.org/wiki/Route_inspection_problem

[ Parent | on HN ]