# Traveling Salesman Problem - Nearest Neighbor Heuristic

Hi @STUDENT_F,

Here’s a Python recipe for sequential sorting, inspired by @HS_Kim’s and @PeterFotiadis’ great replies.

It’s unnecessary to presort the points, because a start point is defined and the script automatically evaluates its next closest point. This means that the presorting isn’t taken into account.

``````import Rhino.Geometry as rg

def sort_sequentially_rec(pt_cloud, start=0, _sorted_pts=[]):
"""Recursively sorts points by distance.

Args:
pt_cloud (Rhino.Geometry.PointCloud): A point cloud to sort
start (int): A start point index to sort from

Returns:
The sequentially sorted points.
"""
if pt_cloud.Count < 1:
return _sorted_pts

test_pt = pt_cloud.PointAt(start)
_sorted_pts.append(test_pt)
pt_cloud.RemoveAt(start)

closest = pt_cloud.ClosestPoint(test_pt)
if closest == -1:
return _sorted_pts

return sort_sequentially_rec(pt_cloud, closest, _sorted_pts)

if __name__ == "__main__":
# Create a point cloud from the list of points
pt_cloud = rg.PointCloud(Points)
# Outputs
Sorted = sort_sequentially_rec(pt_cloud, Start)
``````

Here’s an example on how it works in three dimensions, with the start point being the one with the lowest z-value:

If you’re still interested in learning about the Travelling Salesman Problem, you can check out Daniel Shiffman’s video on YouTube - it’s for Processing but his explanation is great -, or my discussion and example from some time ago:

I hope this helps.

Forum2.gh (11.1 KB)

5 Likes