Traveling Salesman Problem - Nearest Neighbor Heuristic


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.

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

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

    test_pt = pt_cloud.PointAt(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. (11.1 KB)