A part of a university assignment which I didn't complete many years ago (it wasn't actually graded): Given a fixed area eg a unit square, what is the longest 'minimal' path that can be formed from N points? Has anyone encountered a similar problem? Is there a solution? eg. for two points the longest path in a unit square is achieved by placing the points in opposite corners and has length 2sqrt(2) (you have to finish at the point you started from) My solution was heading towards equilateral triangles, but I didn't finish the last step - providing a solution...
Creating an algorithm for TSP will make you rich and famous. Unfortunately there is no nobel prize for Mathematics or else you would be a Nobel laureate too.
posted 16 years ago
Yah TSP is graph theory. Tt's NP complete (ie, no deterministic algorithm that finishes in polynomial time), so a solution (or proof that none exists) is a bit of a Holy Grail. I'm still inclined to think that the problem described in the OP isn't exactly TSP though. Ahh well
The problem we were assigned stated a unit square (ie all points inside a 1x1 square). It's still the Travelling Salesman, but we're looking at a way to select N points in the square so that there is no way to select a second set of points with an optimal TSP solution.