# 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)
3 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)

5 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:

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

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!

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.

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.

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])`.
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?