Shortest Overall Path Between All Random Points

I am trying to find the shortest overall path between a random set of points, where all points are used. I have found the following links that are similar but not exactly what I'm trying to achieve:

http://www.food4rhino.com/project/shortestwalkgh?ufh

http://www.grasshopper3d.com/forum/topics/draw-poly-line-in-order-o...

The problem with the "Shortest Walk" is that it does not take into account all points listed. And the problem with "draw polyline in order of distance" is that it does not create the overall shortest distance between the list of points.

My first thought is to introduce some randomness to the "draw polyline" definition and then analyze the results to find the shortest path. (It also seems like a task that could benefit from using Galapagos) Has anyone tried this before? What are y'all's thoughts?

See attached image that shows a path between all points, but what I want to achieve is the shortest overall version of such a path. (The start point can be anywhere)

(I'm also looking to move this from 2D into 3D)

Attachments:

Capture.JPG, 45 KB

Replies to This Discussion

Permalink Reply by Andrew Heumann on October 12, 2015 at 11:01am

this is a classic "Traveling Salesman" Problem. I don't know of any simple solution to this in GH, but here are a few resources that might help:

http://www.gbl.tuwien.ac.at/_docs/GrasshopperScriptum/GrasshopperSc...

(Richard Schaffranek, the creator of Spiderweb, would be a good one to ask about this)

http://www.grasshopper3d.com/forum/topics/problems-of-a-quirky-trav... (note that I don't think this python script actually provides an optimal solution)

Permalink Reply by John Baker on October 12, 2015 at 11:07am

Thanks Andrew! I will check out those links.

Permalink Reply by Richard Schaffranek on November 20, 2017 at 4:15am

Late replay but:

The shortest overall path that connects all points is called the "TravelingSalesmanProblem". This is NP hard and most likley cannot be solved in linear time. So yes it is something that potentialy could be solved with Galapagos.

If you want a minimal spanning tree then you can use spiderweb but this is not a path but a tree. (llok up Wikipedia for difference..)

RSS