CODEWITHSUNDEEP
pythonarrayspython-3.xeuclidean-distancetraveling-salesman
Sergey Ronin
Sergey Ronin

Reputation: 776

How to apply the distance formula to a list of [x,y] coordinates in python

In order to solve the Traveling Salesman Problem (TSP) using a genetic algorithm, I am randomly generating a list of Z points on an N by N grid:

field = [random.sample(range(N), 2) for x in range(Z)]

Afterwards, to create a random path that the traveling salesman could take, I shuffle the points and append the first point to the last one in order to make the path a "round trip".

path = random.sample(field, len(field))
path.append(member[0])

This is one of the possible "paths":

[[0, 7], [167, 118], [150, 173], [37, 21], [48, 150], [0, 7]]

However, I also need to measure the fitness, i.e. the length of the path in order to determine which paths to eliminate and which to keep (as it is a genetic algorithm). And this is where I do not understand how to proceed further.

My current idea is to use the Distance Formula for a pair of points, but then all the values must be duplicated for me to pass each pair of x,y coordinates into my calculator for finding the distance formula.

For example, for the points above, it will have to look something like this:

[[[0, 7], [167, 118]], [[167, 118], [150, 173]], [[150, 173], [37, 21]],....]

From a technical standpoint I have no idea how I'd be able to generate such list.

P.S I've found this answer addressing the issue, however it is in R, and I still do not understand how to approach this problem.

Upvotes: 0

Views: 1269

Answers (2)

shahaf
shahaf

Reputation: 4973

def dist(p1, p2):
    return math.hypot(p2[0] - p1[0], p2[1] - p1[1])

route = [[3, 0], [0, 4], [1, 4], [2, 1], [1, 4], [3, 0]]

total_dist = 0.0
for i in range(len(route) -1):
    total_dist += dist(route[i], route[i+1])

Upvotes: 1

Mark Ransom
Mark Ransom

Reputation: 308186

It's easy to do with zip using slices, except that zip creates tuples instead of lists:

>>> list(zip(path[0:], path[1:]))
[([0, 7], [167, 118]), ([167, 118], [150, 173]), ([150, 173], [37, 21]), ([37, 21], [48, 150]), ([48, 150], [0, 7])]

If you absolutely need lists instead of tuples, you can create it similarly with a list comprehension.

>>> [[a, b] for a, b in zip(path[0:], path[1:])]
[[[0, 7], [167, 118]], [[167, 118], [150, 173]], [[150, 173], [37, 21]], [[37, 21], [48, 150]], [[48, 150], [0, 7]]]

Upvotes: 1

Related Questions