Win a copy of Micro Frontends in Action this week in the Server-Side JavaScript and NodeJS forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Paul Clapham
• Bear Bibeault
• Junilu Lacar
Sheriffs:
• Jeanne Boyarsky
• Tim Cooke
• Henry Wong
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Tim Holloway
• salvin francis
• Frits Walraven
Bartenders:
• Scott Selikoff
• Piet Souris
• Carey Brown

# Travelling Salesman: longest 'minimal' path

Rancher
Posts: 13459
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...

Ranch Hand
Posts: 539
Is that in an arbitrary 2D shape, or just a square?
Having spent a few minutes thinking, it sounds like it'd get pretty tough pretty quick...out of interest, what course was that in?

--Tim

Ranch Hand
Posts: 2596
Wasn't travelling salesman problem part of "graph theory"? Or maybe I am missing sth...
- Manish

Ranch Hand
Posts: 275
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.

Tim West
Ranch Hand
Posts: 539
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

- Tim

David O'Meara
Rancher
Posts: 13459
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.

Ranch Hand
Posts: 1907
1

Originally posted by Sahir Shibley:
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.

There is Field Medal ,also other prizes like Wolf Prize etc.Now you can try