Traveling Salesman Problem - Nearest Neighbor Heuristic

Hi,

there is a set of points (max. 100 pts), sorted in x direction. From the sorted set I would like to start the distance measurement with Item Index 0 along x axis. The set of points should be entirely connected and always by the nearest neighbor (closest point) started by Item Index 0. This repetitive calculation should be started by the result (closest point) of the previous calculation. It is not clear to me how to define this iteration and code with grasshopper components.

I searched about this topic and know that it is a asymmetric system type of the Traveling Salesman Problem. Unfortunately I am not that experienced with this kind of mathematical problems and python coding for finding solutions.

Thanks a lot for your help and time!

Forum1.gh (7.0 KB)

Have a try NeoArchaic’s Sequential Closest Poins.



Forum1_re.gh (13.9 KB)
2 Likes

Translate this to P (NOT a traveling salesman solution) if you are after an iterative proximity.

1 Like

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)

3 Likes

There is no reason to sort the list by X because 1) it was already sorted that way using MA ‘Pr’ and 2) it’s irrelevant using Closest Point.

Here is the Anemone way with Jitter thrown in to prove the point:


cp_walk_2020Sep25a.gh (18.3 KB)

My coolest use of this technique was here:

pavilion_2017Jan20c

This is a slightly updated R6 version of that code that hopefully won’t lose the Image Sampler:
pavilion_2017Jan20b.gh (55.1 KB)

5 Likes

Hi @diff-arch,

thank you so much for your lovely post. I need a little bit more time to understand your script and the overall topic of the math behind, but thank you as well for the recommended video. This could be a good introduction to the topic. I will check everything out.

Thanks again for your time and help!

1 Like

Hello again @diff-arch,

When it comes to the transformation of the code by searching the second closest point, starting always from 0 of my pt cloud, I think I can not use .closestPoint() command (line 37) because it does not really produce a list where I can pick the second item.

Do I have to substitute the .ClosestPoint() command with a distance measurement command and continuing after that with sorting this list and picking the second item (or shifting the list by 1) to get the second closest point?

Thank you again!

No, you don’t have to. You can for instance first search for the closest point, delete that one from the point cloud, and again search for the closest point to find the second closest one.

1 Like

I think I have to correct myself, sorry for being unclear. I wanted the second closest point from each individual point of the former result of your code (Sorted Point Output). Eg. connections between 0-2, 1-4, 2-4, 4-6, etc.
I hope that you can help me with this @p1r4t3b0y

Forum3.gh (20.1 KB)
Thank you :slight_smile:

Have you already figured it out?

If not, do you want something like this:

0-2, 1-3, 2-4, 3-5, 4-6, 5-7, …

I’m asking, because your sequence above seems to be different than what you describe?

Just to be clear, you now want to connect each point to the closest point of its closest point?
I guess this would result in two separate polylines, and not one like before, like so:

Are you fine with that?

Hello back again,

I think we are still talking about different ways.

First component:
Your first solution and code of the sequentially sorting by closest neighbour is the first part of what I needed and is already solved. Your code repeats the function of the closest point searching from the closest point again and involves all points (destinations) of the cloud.

Second component:
The second part, a new script component should take the sorted point output of the first code as input. From here I would like to check each point in order of the output of the first component for the second closest point along the order. The resulting second closest point to each point of the output points of the first component should be a shortcut option at each point from the path that was generated with the first component. It represents like a skipping option along the path at each stage. The result will No be a continues path, rather line connections between test pt and second closest point.

I tried to do it with python but I was not able to bring it to work

Yes, my diagram above shows the result of what you’re describing, if I’m not mistaken! You can interpret the different polyline segments as lines, if you prefer, but does this represent your desired outcome?

I understand. What should the data structure of the output of the second component look like? Simply a list of second closest points that matches the list length of the output of the first component, meaning a second closest point for each point from the output of the first component?

I’ll see what I can come up with. May take some time though!

Hi @diff-arch,
first of all, thank you so much for helping me that much.
I draw the connections I am talking about in the following picture.

The grey path represents the path you coded inside your first script. The black lines are showing the second closest point from each point.
0-2 connection = two is second closest (1 is closest)
1-4 connection = four is second closest (2 is closest, 4 is closer than 3)
etc.

The output of the component (second closest point from each point) could be structured like the test point order:
test point order:
1
2
3
4
5
etc.

Resulting order of the component:
2
4
4
5
6
7
8
10
10
12
12

I hope very much that this makes it easier to understand.

Hey @STUDENT_F,

Here’s what I’ve come up with!

import Rhino.Geometry as rg


def get_second_closest(points):
    """Finds the second closest point of sequentially sorted points.
    
    Args:
      points (list): A list of sequentially sorted points
    
    Returns:
      The list of second closest points.
    """
    sec_closest_pts = []
    pt_cloud = rg.PointCloud(points[1:])
    
    for i in range(len(points)):
        if pt_cloud.Count <= 1:
            break
        pt_cloud.RemoveAt(0)
        closest = pt_cloud.ClosestPoint(Points[i])
        if closest > -1:
            sec_closest_pts.append(pt_cloud.PointAt(closest))
                
    return sec_closest_pts


if __name__ == "__main__":
    # Outputs
    Closest2 = get_second_closest(Points)

I hope this helps!

Forum4.gh (12.9 KB)

1 Like

Thank you so much for your help. To be a able to learn from you I have just a few more questions what you did exactly.

You used a pt_cloud that starts reducing itself from start > you defined a variable “closest” that represents the closest pt with an index > from here I do not understand what is happening. How can an index represents the distance to a point and why is the second closest point the result of “closest > -1”? It is also not clear to me what “return” does in your code.

That is the last if condition with the name doing?

Thank you so much for bringing me a little bit further with coding and I am very sorry for this basic questions. I am trying to find a way to learn python coding for grasshopper, but it seams difficult for me to find a way to learn it.

Best!!

You’re welcome! :slight_smile:

Haha, it doesn’t represent a distance, just the index of the closest point.

First, we instantiate/create a point cloud that excludes the first point - hence points[1:] -, which means get everything from points starting at index 1. It’s called list slicing in Python.
We exclude the first index because, for each iteration of the for loop, we first delete index 0 of the point cloud, to avoid the closest neighbor search to find the “real” closest point, because we want the second closest. However, the first iteration iteration is an exception. Here we’d have to delete index 0 and index 1. This could also be done with an if statement inside the for loop, but I find this more elegant. At the very first iteration, we have to delete index 0 to prevent the closest neighbor search to find points[0] for points[i], where i is 0, meaning itself. The iterations after that, this isn’t a problem, because we already removed the current point with pt_cloud.RemoveAt(0) at the previous iteration.
Your absolutely right that pt_cloud is a sacrificial container, from which we delete items that we don’t need anymore.

Inside the for loop, we go through all the previously, sequentially by distance sorted points one by one.
First, we check if the point cloud has less than or equal to 1 point and if so break out of the entire loop. This is necessary because we need at least two points! The first one would be removed from the point cloud during the following step, and the second one would be the only possible second closest neighbor to the current point points[i].

As you noted correctly, now we search for a second closest point, but pt_cloud.ClosestPoint(Points[i]) returns the index of the closest point in the point cloud, which is fine!
We don’t really need a distance, since only the second closest neighbor can be found in the first place. Remember, we removed the closest neighbor before, with pt_cloud.RemoveAt(0), and points[i] can’t find itself, because it was removed at the previous iteration or for points[i], where i is 0, already omitted while creating the point cloud.
All that remains, is to check whether closest is greater than -1, because pt_cloud.ClosestPoint(Points[i]) return -1, in case it didn’t find a closest point.
If closest is a valid index, we append the closest point from the point cloud to the sec_closest_pts list.

Lastly, sec_closest_pts is returned from the function.

The return keyword is used to return data from a function or method. A method is also a function, but lives inside a class.

def add(a, b):
    return a + b

result = add(1, 4) # result is 5

# Vs.

def add(a, b):
    r = a + b

result = add(1, 4) # result is None

If you want to get something out of a function, you need to return it at the end or even a strategic place inside the function. You can read more about return here.

if __name__ == "__main__": executes the code after it, only if the Python file itself is run. If it is for instance executed as a part of another Python script, the code from the if statement is not run.
It’s a nice convention to use it in Python, but not really necessary in the context of GHPython.
You can read up on it here, if you’re interested.

For GHPython and Rhino.Python, you can find some great resources here. There’s also a great variety of Grasshopper specific Python tutorials on YouTube.
For learning Python in general you should visit this site.

Addenum:
I just noticed a typo!! Points[i] in closest = pt_cloud.ClosestPoint(Points[i]) should be lower case, like this closest = pt_cloud.ClosestPoint(points[i]). :wink:
It still works because the input Points is a global variable, but should be corrected to prevent future errors.

2 Likes
2 Likes

Thank you so much for all this extra information. I will go through this and learn from you! Best!

One more thing about the result of the code. The input has a length of 13 points. The output should have 12 points. I thing that point no. 11 has the problem that the second closest point is 12, but is already connected from the path of your first component.
Do you know how to get the output with a length of 12 points?
Best!

If I remember correctly the output of the second component has only 11 points, compared to the output of the first component, because the first (0) and last (12) points of the sequentially sorted points are not members of the second closest points.

The first point (0) has a second closest point, but can’t be the second closest point of any other point, since it precedes all of them in the sequential order.
The last point (12) has no closest and no second closest point, because it’s the last point in the sequential order.

Remember the second component only looks for second closest points of each point in the sequenctially sorted points and outputs them! It really doesn’t make sense to “pollute” these second closest points with points that well aren’t second closest points.

Why do you need this?