Win a copy of Micro Frontends in Action this week in the Server-Side JavaScript and NodeJS forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
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
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android Firefox Browser Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Wasn't travelling salesman problem part of "graph theory"? Or maybe I am missing sth...
- Manish
 
Ranch Hand
Posts: 275
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
 
reply
    Bookmark Topic Watch Topic
  • New Topic