Travelling salesman using brute-force and heuristicsFunction to print command-line usage for a programSolving the travelling salesman problem using a genetic algorithmCalculating Travelling Salesman - memory consumption and speedTravelling salesman with four citiesTravelling Salesman in QtTravelling Salesman Problem with visualisation in JavaTravelling Salesman problem using GA, mutation, and crossoverTravelling Salesman Problem solverAttempting to solve the Travelling Salesman Problem using idiomatic C++Travelling salesman with something like MSTGoogle FooBar “Prepare The Bunnies Escape”

Unreliable Magic - Is it worth it?

Is the destination of a commercial flight important for the pilot?

Flow chart document symbol

How do we know the LHC results are robust?

What does "I’d sit this one out, Cap," imply or mean in the context?

Is there a problem with hiding "forgot password" until it's needed?

Did Dumbledore lie to Harry about how long he had James Potter's invisibility cloak when he was examining it? If so, why?

Why, precisely, is argon used in neutrino experiments?

What happens if you roll doubles 3 times then land on "Go to jail?"

Different result between scanning in Epson's "color negative film" mode and scanning in positive -> invert curve in post?

What does 算不上 mean in 算不上太美好的日子?

Lay out the Carpet

How does buying out courses with grant money work?

Pre-amplifier input protection

Opposite of a diet

Is there a korbon needed for conversion?

Is exact Kanji stroke length important?

How does it work when somebody invests in my business?

How did Doctor Strange see the winning outcome in Avengers: Infinity War?

Why not increase contact surface when reentering the atmosphere?

Implement the Thanos sorting algorithm

Pole-zeros of a real-valued causal FIR system

Valid Badminton Score?

Is expanding the research of a group into machine learning as a PhD student risky?



Travelling salesman using brute-force and heuristics


Function to print command-line usage for a programSolving the travelling salesman problem using a genetic algorithmCalculating Travelling Salesman - memory consumption and speedTravelling salesman with four citiesTravelling Salesman in QtTravelling Salesman Problem with visualisation in JavaTravelling Salesman problem using GA, mutation, and crossoverTravelling Salesman Problem solverAttempting to solve the Travelling Salesman Problem using idiomatic C++Travelling salesman with something like MSTGoogle FooBar “Prepare The Bunnies Escape”













11












$begingroup$


I have implemented both a brute-force and a heuristic algorithm to solve the travelling salesman problem.



import doctest
from itertools import permutations


def distance(point1, point2):
"""
Returns the Euclidean distance of two points in the Cartesian Plane.

>>> distance([3,4],[0,0])
5.0
>>> distance([3,6],[10,6])
7.0
"""
return ((point1[0] - point2[0])**2 + (point1[1] - point2[1])**2) ** 0.5


def total_distance(points):
"""
Returns the length of the path passing throught
all the points in the given order.

>>> total_distance([[1,2],[4,6]])
5.0
>>> total_distance([[3,6],[7,6],[12,6]])
9.0
"""
return sum([distance(point, points[index + 1]) for index, point in enumerate(points[:-1])])


def travelling_salesman(points, start=None):
"""
Finds the shortest route to visit all the cities by bruteforce.
Time complexity is O(N!), so never use on long lists.

>>> travelling_salesman([[0,0],[10,0],[6,0]])
([0, 0], [6, 0], [10, 0])
>>> travelling_salesman([[0,0],[6,0],[2,3],[3,7],[0.5,9],[3,5],[9,1]])
([0, 0], [6, 0], [9, 1], [2, 3], [3, 5], [3, 7], [0.5, 9])
"""
if start is None:
start = points[0]
return min([perm for perm in permutations(points) if perm[0] == start], key=total_distance)


def optimized_travelling_salesman(points, start=None):
"""
As solving the problem in the brute force way is too slow,
this function implements a simple heuristic: always
go to the nearest city.

Even if this algoritmh is extremely simple, it works pretty well
giving a solution only about 25% longer than the optimal one (cit. Wikipedia),
and runs very fast in O(N^2) time complexity.

>>> optimized_travelling_salesman([[i,j] for i in range(5) for j in range(5)])
[[0, 0], [0, 1], [0, 2], [0, 3], [0, 4], [1, 4], [1, 3], [1, 2], [1, 1], [1, 0], [2, 0], [2, 1], [2, 2], [2, 3], [2, 4], [3, 4], [3, 3], [3, 2], [3, 1], [3, 0], [4, 0], [4, 1], [4, 2], [4, 3], [4, 4]]
>>> optimized_travelling_salesman([[0,0],[10,0],[6,0]])
[[0, 0], [6, 0], [10, 0]]
"""
if start is None:
start = points[0]
must_visit = points
path = [start]
must_visit.remove(start)
while must_visit:
nearest = min(must_visit, key=lambda x: distance(path[-1], x))
path.append(nearest)
must_visit.remove(nearest)
return path


def main():
doctest.testmod()
points = [[0, 0], [1, 5.7], [2, 3], [3, 7],
[0.5, 9], [3, 5], [9, 1], [10, 5]]
print("""The minimum distance to visit all the following points:
starting at is .

The optimized algoritmh yields a path long .""".format(
tuple(points),
points[0],
total_distance(travelling_salesman(points)),
total_distance(optimized_travelling_salesman(points))))


if __name__ == "__main__":
main()









share|improve this question











$endgroup$











  • $begingroup$
    The multiline string could be neater - see e.g. codereview.stackexchange.com/q/60366/32391. Also, you could remove the very long test line by either including a slice (e.g. check every 5th item from it) or having a separate (multiline) assignment so you can compare the result of the function to the list as >>> result == expected then just True.
    $endgroup$
    – jonrsharpe
    Feb 18 '15 at 23:08











  • $begingroup$
    optimized_travelling_salesman feels like a misnomer to me, probably should be greedy_travelling_salesman
    $endgroup$
    – Akavall
    May 13 '17 at 0:30







  • 1




    $begingroup$
    Quite interesting code, esp. because of its simplicity. I also checked it against my standard TSP algo and it issues indeed the shortest path. What I don't get is the "optimized" path. Applied to your 'points it is only 8% longer but you say it can be up to 25% longer. Well, the algo may be faster but what's optimizing about it?
    $endgroup$
    – Apostolos
    Dec 4 '18 at 23:08











  • $begingroup$
    @Apostolos running time is optimized, it is a simple heuristic (practical shortcut) to always go to the nearest city to save computational time. The route is only a bit longer but runnning time is drastically shorter
    $endgroup$
    – Caridorc
    Dec 5 '18 at 14:36











  • $begingroup$
    Yes, this is clear. But my question is if the route obtained is 25% longer, what's the use of the heuristic algo? And then, how do you mean "dramatically"? Can you give a percentage of time reduced and the size of the data sample that you used for testing time? (It's also OK if can't or don't wish to! :)
    $endgroup$
    – Apostolos
    Dec 5 '18 at 17:20















11












$begingroup$


I have implemented both a brute-force and a heuristic algorithm to solve the travelling salesman problem.



import doctest
from itertools import permutations


def distance(point1, point2):
"""
Returns the Euclidean distance of two points in the Cartesian Plane.

>>> distance([3,4],[0,0])
5.0
>>> distance([3,6],[10,6])
7.0
"""
return ((point1[0] - point2[0])**2 + (point1[1] - point2[1])**2) ** 0.5


def total_distance(points):
"""
Returns the length of the path passing throught
all the points in the given order.

>>> total_distance([[1,2],[4,6]])
5.0
>>> total_distance([[3,6],[7,6],[12,6]])
9.0
"""
return sum([distance(point, points[index + 1]) for index, point in enumerate(points[:-1])])


def travelling_salesman(points, start=None):
"""
Finds the shortest route to visit all the cities by bruteforce.
Time complexity is O(N!), so never use on long lists.

>>> travelling_salesman([[0,0],[10,0],[6,0]])
([0, 0], [6, 0], [10, 0])
>>> travelling_salesman([[0,0],[6,0],[2,3],[3,7],[0.5,9],[3,5],[9,1]])
([0, 0], [6, 0], [9, 1], [2, 3], [3, 5], [3, 7], [0.5, 9])
"""
if start is None:
start = points[0]
return min([perm for perm in permutations(points) if perm[0] == start], key=total_distance)


def optimized_travelling_salesman(points, start=None):
"""
As solving the problem in the brute force way is too slow,
this function implements a simple heuristic: always
go to the nearest city.

Even if this algoritmh is extremely simple, it works pretty well
giving a solution only about 25% longer than the optimal one (cit. Wikipedia),
and runs very fast in O(N^2) time complexity.

>>> optimized_travelling_salesman([[i,j] for i in range(5) for j in range(5)])
[[0, 0], [0, 1], [0, 2], [0, 3], [0, 4], [1, 4], [1, 3], [1, 2], [1, 1], [1, 0], [2, 0], [2, 1], [2, 2], [2, 3], [2, 4], [3, 4], [3, 3], [3, 2], [3, 1], [3, 0], [4, 0], [4, 1], [4, 2], [4, 3], [4, 4]]
>>> optimized_travelling_salesman([[0,0],[10,0],[6,0]])
[[0, 0], [6, 0], [10, 0]]
"""
if start is None:
start = points[0]
must_visit = points
path = [start]
must_visit.remove(start)
while must_visit:
nearest = min(must_visit, key=lambda x: distance(path[-1], x))
path.append(nearest)
must_visit.remove(nearest)
return path


def main():
doctest.testmod()
points = [[0, 0], [1, 5.7], [2, 3], [3, 7],
[0.5, 9], [3, 5], [9, 1], [10, 5]]
print("""The minimum distance to visit all the following points:
starting at is .

The optimized algoritmh yields a path long .""".format(
tuple(points),
points[0],
total_distance(travelling_salesman(points)),
total_distance(optimized_travelling_salesman(points))))


if __name__ == "__main__":
main()









share|improve this question











$endgroup$











  • $begingroup$
    The multiline string could be neater - see e.g. codereview.stackexchange.com/q/60366/32391. Also, you could remove the very long test line by either including a slice (e.g. check every 5th item from it) or having a separate (multiline) assignment so you can compare the result of the function to the list as >>> result == expected then just True.
    $endgroup$
    – jonrsharpe
    Feb 18 '15 at 23:08











  • $begingroup$
    optimized_travelling_salesman feels like a misnomer to me, probably should be greedy_travelling_salesman
    $endgroup$
    – Akavall
    May 13 '17 at 0:30







  • 1




    $begingroup$
    Quite interesting code, esp. because of its simplicity. I also checked it against my standard TSP algo and it issues indeed the shortest path. What I don't get is the "optimized" path. Applied to your 'points it is only 8% longer but you say it can be up to 25% longer. Well, the algo may be faster but what's optimizing about it?
    $endgroup$
    – Apostolos
    Dec 4 '18 at 23:08











  • $begingroup$
    @Apostolos running time is optimized, it is a simple heuristic (practical shortcut) to always go to the nearest city to save computational time. The route is only a bit longer but runnning time is drastically shorter
    $endgroup$
    – Caridorc
    Dec 5 '18 at 14:36











  • $begingroup$
    Yes, this is clear. But my question is if the route obtained is 25% longer, what's the use of the heuristic algo? And then, how do you mean "dramatically"? Can you give a percentage of time reduced and the size of the data sample that you used for testing time? (It's also OK if can't or don't wish to! :)
    $endgroup$
    – Apostolos
    Dec 5 '18 at 17:20













11












11








11


2



$begingroup$


I have implemented both a brute-force and a heuristic algorithm to solve the travelling salesman problem.



import doctest
from itertools import permutations


def distance(point1, point2):
"""
Returns the Euclidean distance of two points in the Cartesian Plane.

>>> distance([3,4],[0,0])
5.0
>>> distance([3,6],[10,6])
7.0
"""
return ((point1[0] - point2[0])**2 + (point1[1] - point2[1])**2) ** 0.5


def total_distance(points):
"""
Returns the length of the path passing throught
all the points in the given order.

>>> total_distance([[1,2],[4,6]])
5.0
>>> total_distance([[3,6],[7,6],[12,6]])
9.0
"""
return sum([distance(point, points[index + 1]) for index, point in enumerate(points[:-1])])


def travelling_salesman(points, start=None):
"""
Finds the shortest route to visit all the cities by bruteforce.
Time complexity is O(N!), so never use on long lists.

>>> travelling_salesman([[0,0],[10,0],[6,0]])
([0, 0], [6, 0], [10, 0])
>>> travelling_salesman([[0,0],[6,0],[2,3],[3,7],[0.5,9],[3,5],[9,1]])
([0, 0], [6, 0], [9, 1], [2, 3], [3, 5], [3, 7], [0.5, 9])
"""
if start is None:
start = points[0]
return min([perm for perm in permutations(points) if perm[0] == start], key=total_distance)


def optimized_travelling_salesman(points, start=None):
"""
As solving the problem in the brute force way is too slow,
this function implements a simple heuristic: always
go to the nearest city.

Even if this algoritmh is extremely simple, it works pretty well
giving a solution only about 25% longer than the optimal one (cit. Wikipedia),
and runs very fast in O(N^2) time complexity.

>>> optimized_travelling_salesman([[i,j] for i in range(5) for j in range(5)])
[[0, 0], [0, 1], [0, 2], [0, 3], [0, 4], [1, 4], [1, 3], [1, 2], [1, 1], [1, 0], [2, 0], [2, 1], [2, 2], [2, 3], [2, 4], [3, 4], [3, 3], [3, 2], [3, 1], [3, 0], [4, 0], [4, 1], [4, 2], [4, 3], [4, 4]]
>>> optimized_travelling_salesman([[0,0],[10,0],[6,0]])
[[0, 0], [6, 0], [10, 0]]
"""
if start is None:
start = points[0]
must_visit = points
path = [start]
must_visit.remove(start)
while must_visit:
nearest = min(must_visit, key=lambda x: distance(path[-1], x))
path.append(nearest)
must_visit.remove(nearest)
return path


def main():
doctest.testmod()
points = [[0, 0], [1, 5.7], [2, 3], [3, 7],
[0.5, 9], [3, 5], [9, 1], [10, 5]]
print("""The minimum distance to visit all the following points:
starting at is .

The optimized algoritmh yields a path long .""".format(
tuple(points),
points[0],
total_distance(travelling_salesman(points)),
total_distance(optimized_travelling_salesman(points))))


if __name__ == "__main__":
main()









share|improve this question











$endgroup$




I have implemented both a brute-force and a heuristic algorithm to solve the travelling salesman problem.



import doctest
from itertools import permutations


def distance(point1, point2):
"""
Returns the Euclidean distance of two points in the Cartesian Plane.

>>> distance([3,4],[0,0])
5.0
>>> distance([3,6],[10,6])
7.0
"""
return ((point1[0] - point2[0])**2 + (point1[1] - point2[1])**2) ** 0.5


def total_distance(points):
"""
Returns the length of the path passing throught
all the points in the given order.

>>> total_distance([[1,2],[4,6]])
5.0
>>> total_distance([[3,6],[7,6],[12,6]])
9.0
"""
return sum([distance(point, points[index + 1]) for index, point in enumerate(points[:-1])])


def travelling_salesman(points, start=None):
"""
Finds the shortest route to visit all the cities by bruteforce.
Time complexity is O(N!), so never use on long lists.

>>> travelling_salesman([[0,0],[10,0],[6,0]])
([0, 0], [6, 0], [10, 0])
>>> travelling_salesman([[0,0],[6,0],[2,3],[3,7],[0.5,9],[3,5],[9,1]])
([0, 0], [6, 0], [9, 1], [2, 3], [3, 5], [3, 7], [0.5, 9])
"""
if start is None:
start = points[0]
return min([perm for perm in permutations(points) if perm[0] == start], key=total_distance)


def optimized_travelling_salesman(points, start=None):
"""
As solving the problem in the brute force way is too slow,
this function implements a simple heuristic: always
go to the nearest city.

Even if this algoritmh is extremely simple, it works pretty well
giving a solution only about 25% longer than the optimal one (cit. Wikipedia),
and runs very fast in O(N^2) time complexity.

>>> optimized_travelling_salesman([[i,j] for i in range(5) for j in range(5)])
[[0, 0], [0, 1], [0, 2], [0, 3], [0, 4], [1, 4], [1, 3], [1, 2], [1, 1], [1, 0], [2, 0], [2, 1], [2, 2], [2, 3], [2, 4], [3, 4], [3, 3], [3, 2], [3, 1], [3, 0], [4, 0], [4, 1], [4, 2], [4, 3], [4, 4]]
>>> optimized_travelling_salesman([[0,0],[10,0],[6,0]])
[[0, 0], [6, 0], [10, 0]]
"""
if start is None:
start = points[0]
must_visit = points
path = [start]
must_visit.remove(start)
while must_visit:
nearest = min(must_visit, key=lambda x: distance(path[-1], x))
path.append(nearest)
must_visit.remove(nearest)
return path


def main():
doctest.testmod()
points = [[0, 0], [1, 5.7], [2, 3], [3, 7],
[0.5, 9], [3, 5], [9, 1], [10, 5]]
print("""The minimum distance to visit all the following points:
starting at is .

The optimized algoritmh yields a path long .""".format(
tuple(points),
points[0],
total_distance(travelling_salesman(points)),
total_distance(optimized_travelling_salesman(points))))


if __name__ == "__main__":
main()






python traveling-salesman






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Feb 19 '15 at 0:30









nhgrif

23.3k354127




23.3k354127










asked Feb 18 '15 at 21:47









CaridorcCaridorc

23k538117




23k538117











  • $begingroup$
    The multiline string could be neater - see e.g. codereview.stackexchange.com/q/60366/32391. Also, you could remove the very long test line by either including a slice (e.g. check every 5th item from it) or having a separate (multiline) assignment so you can compare the result of the function to the list as >>> result == expected then just True.
    $endgroup$
    – jonrsharpe
    Feb 18 '15 at 23:08











  • $begingroup$
    optimized_travelling_salesman feels like a misnomer to me, probably should be greedy_travelling_salesman
    $endgroup$
    – Akavall
    May 13 '17 at 0:30







  • 1




    $begingroup$
    Quite interesting code, esp. because of its simplicity. I also checked it against my standard TSP algo and it issues indeed the shortest path. What I don't get is the "optimized" path. Applied to your 'points it is only 8% longer but you say it can be up to 25% longer. Well, the algo may be faster but what's optimizing about it?
    $endgroup$
    – Apostolos
    Dec 4 '18 at 23:08











  • $begingroup$
    @Apostolos running time is optimized, it is a simple heuristic (practical shortcut) to always go to the nearest city to save computational time. The route is only a bit longer but runnning time is drastically shorter
    $endgroup$
    – Caridorc
    Dec 5 '18 at 14:36











  • $begingroup$
    Yes, this is clear. But my question is if the route obtained is 25% longer, what's the use of the heuristic algo? And then, how do you mean "dramatically"? Can you give a percentage of time reduced and the size of the data sample that you used for testing time? (It's also OK if can't or don't wish to! :)
    $endgroup$
    – Apostolos
    Dec 5 '18 at 17:20
















  • $begingroup$
    The multiline string could be neater - see e.g. codereview.stackexchange.com/q/60366/32391. Also, you could remove the very long test line by either including a slice (e.g. check every 5th item from it) or having a separate (multiline) assignment so you can compare the result of the function to the list as >>> result == expected then just True.
    $endgroup$
    – jonrsharpe
    Feb 18 '15 at 23:08











  • $begingroup$
    optimized_travelling_salesman feels like a misnomer to me, probably should be greedy_travelling_salesman
    $endgroup$
    – Akavall
    May 13 '17 at 0:30







  • 1




    $begingroup$
    Quite interesting code, esp. because of its simplicity. I also checked it against my standard TSP algo and it issues indeed the shortest path. What I don't get is the "optimized" path. Applied to your 'points it is only 8% longer but you say it can be up to 25% longer. Well, the algo may be faster but what's optimizing about it?
    $endgroup$
    – Apostolos
    Dec 4 '18 at 23:08











  • $begingroup$
    @Apostolos running time is optimized, it is a simple heuristic (practical shortcut) to always go to the nearest city to save computational time. The route is only a bit longer but runnning time is drastically shorter
    $endgroup$
    – Caridorc
    Dec 5 '18 at 14:36











  • $begingroup$
    Yes, this is clear. But my question is if the route obtained is 25% longer, what's the use of the heuristic algo? And then, how do you mean "dramatically"? Can you give a percentage of time reduced and the size of the data sample that you used for testing time? (It's also OK if can't or don't wish to! :)
    $endgroup$
    – Apostolos
    Dec 5 '18 at 17:20















$begingroup$
The multiline string could be neater - see e.g. codereview.stackexchange.com/q/60366/32391. Also, you could remove the very long test line by either including a slice (e.g. check every 5th item from it) or having a separate (multiline) assignment so you can compare the result of the function to the list as >>> result == expected then just True.
$endgroup$
– jonrsharpe
Feb 18 '15 at 23:08





$begingroup$
The multiline string could be neater - see e.g. codereview.stackexchange.com/q/60366/32391. Also, you could remove the very long test line by either including a slice (e.g. check every 5th item from it) or having a separate (multiline) assignment so you can compare the result of the function to the list as >>> result == expected then just True.
$endgroup$
– jonrsharpe
Feb 18 '15 at 23:08













$begingroup$
optimized_travelling_salesman feels like a misnomer to me, probably should be greedy_travelling_salesman
$endgroup$
– Akavall
May 13 '17 at 0:30





$begingroup$
optimized_travelling_salesman feels like a misnomer to me, probably should be greedy_travelling_salesman
$endgroup$
– Akavall
May 13 '17 at 0:30





1




1




$begingroup$
Quite interesting code, esp. because of its simplicity. I also checked it against my standard TSP algo and it issues indeed the shortest path. What I don't get is the "optimized" path. Applied to your 'points it is only 8% longer but you say it can be up to 25% longer. Well, the algo may be faster but what's optimizing about it?
$endgroup$
– Apostolos
Dec 4 '18 at 23:08





$begingroup$
Quite interesting code, esp. because of its simplicity. I also checked it against my standard TSP algo and it issues indeed the shortest path. What I don't get is the "optimized" path. Applied to your 'points it is only 8% longer but you say it can be up to 25% longer. Well, the algo may be faster but what's optimizing about it?
$endgroup$
– Apostolos
Dec 4 '18 at 23:08













$begingroup$
@Apostolos running time is optimized, it is a simple heuristic (practical shortcut) to always go to the nearest city to save computational time. The route is only a bit longer but runnning time is drastically shorter
$endgroup$
– Caridorc
Dec 5 '18 at 14:36





$begingroup$
@Apostolos running time is optimized, it is a simple heuristic (practical shortcut) to always go to the nearest city to save computational time. The route is only a bit longer but runnning time is drastically shorter
$endgroup$
– Caridorc
Dec 5 '18 at 14:36













$begingroup$
Yes, this is clear. But my question is if the route obtained is 25% longer, what's the use of the heuristic algo? And then, how do you mean "dramatically"? Can you give a percentage of time reduced and the size of the data sample that you used for testing time? (It's also OK if can't or don't wish to! :)
$endgroup$
– Apostolos
Dec 5 '18 at 17:20




$begingroup$
Yes, this is clear. But my question is if the route obtained is 25% longer, what's the use of the heuristic algo? And then, how do you mean "dramatically"? Can you give a percentage of time reduced and the size of the data sample that you used for testing time? (It's also OK if can't or don't wish to! :)
$endgroup$
– Apostolos
Dec 5 '18 at 17:20










3 Answers
3






active

oldest

votes


















9












$begingroup$

I enjoyed the first look at the code as it's very clean, you have
extensive docstrings and great, expressive function names. Now you know
the deal with PEP8, but except for the one 200 character long line I
don't think it matters much really.



There're a few typo with the wrong spelling "algoritmh".



The coordinates should be immutable 2-tuples. The reason being the
safety of immutable data-structures. YMMV, but that makes it really
obvious that those are coordinates as well.



optimized_travelling_salesman should make a defensive copy of
points, or you should otherwise indicate that it's destructive on that
argument.



Instead of if start is None: start = points[0] you could also use
start = start or points[0] to save some space while still being
relatively readable.



For the algorithms the only thing I'd is not to use square root if you
don't have to. You can basically create a distance_squared and use that
instead of distance because the relationship
between a smaller and bigger distance will stay the same regardless.
That doesn't apply for the final output of course. Edit: And, as mentioned below by @JanneKarila, you can't use that for the brute-force version.






share|improve this answer











$endgroup$








  • 3




    $begingroup$
    Result will be different using the sum of squared distances. $1+3 = 2+2$ but $1+9 > 4+4$
    $endgroup$
    – Janne Karila
    Feb 19 '15 at 14:04



















3












$begingroup$

Besides thanking you for posting this, I wanted to share how I edited your code to do something I needed.



I'm implementing a survey for econ research. Part of the implementation is giving our survey team a list of addresses so that they can visit them. After geo-coding these addresses, we organized them into neighborhoods through a very simple k-means clustering process. Each member of our team is assigned a zone, therefore we needed to provide them with an optimized route within each zone.



The issue at hand was that members of our survey need additional data on top of the location data - such as unique IDs for households and basic contact info for the household. So, somehow I needed to keep some form of identification for each coordinate so I could merge it back with the relevant data.



I realize this might be a simple edit, but I couldn't figure out another way to have a relation between the two tables of data.



The code is exactly the same, except for that it returns an enumerated list (enumerated at the time of input) so that you can merge it back with other data.



I also added a haversine formula for calculating the distance between two geo-coordinates in miles.



import numpy as np
def haversine_enum(item1, item2):
"""
Returns the great-circle distance between two enumearted points
on a sphere given their indexes, longitudes, and latitudes in the
form of a tuple.

>>> haversine_enum((0, (3,5)), (1, (4,7)))
154.27478490048566

>>> haversine_enum((0, (41.325, -72.325)), (1, (41.327, -72.327)))
0.17282397386672291
"""
r = 3959 #radius of the earth
r_lat = np.radians(item1[1][0])
r_lat2 = np.radians(item2[1][0])
delta_r_lat = np.radians(item2[1][0]-item1[1][0])
delta_r_lon = np.radians(item2[1][1]-item1[1][1])

a = (np.sin(delta_r_lat / 2) * np.sin(delta_r_lat / 2) +
np.cos(r_lat) * np.cos(r_lat2) *
np.sin(delta_r_lon / 2) * np.sin(delta_r_lon / 2))

c = 2 * np.arctan2(np.sqrt(a), np.sqrt(1-a))

d = r * c

return d

def optimized_travelling_salesman_enum(points, start=None):
"""
Taken from:
https://codereview.stackexchange.com/questions/81865/
travelling-salesman-using-brute-force-and-heuristics

As solving the problem in the brute force way is too slow,
this function implements a simple heuristic: always
go to the nearest city.

Even if this algoritmh is extremely simple, it works pretty well
giving a solution only about 25% longer than the optimal one (cit. Wikipedia),
and runs very fast in O(N^2) time complexity.
"""

points = list(enumerate(points))
if start is None:
start = points[0]

must_visit = points
path = [start]
must_visit.remove(start)

while must_visit:
nearest = min(must_visit,
key=lambda x: haversine_enum(path[-1], x))
path.append(nearest)
must_visit.remove(nearest)

return path





share|improve this answer











$endgroup$












  • $begingroup$
    @Toby Speight > how it improves upon the original: 'it returns an enumerated list (enumerated at the time of input) so that you can merge it back with other data.'
    $endgroup$
    – Daniel
    Mar 14 '18 at 19:06










  • $begingroup$
    Very reasonable solution, the enumeration looks simple, otherwise maybe you could have built a dictionary putting in relation the coordinates as keys to the informations as values
    $endgroup$
    – Caridorc
    Mar 17 '18 at 10:47


















0












$begingroup$

Python code for Travelling salesman problem is:-



import numpy as np
import math
def Minimum(s):
low = math.inf
for i in s:
if i < low and i!=0:
low = i
return low

def Calc_cost(g,init):
path =[]
step1 = []

step2 = [[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]];

step3 = [[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]];

step4 =[]
step4.append(0)

temp1 = [0,1,2,3]
temp2 = [1, 2, 3,4]

for i in range (0,len(g)):
step1.append(g[i][init])
print('----------------------------------------------------------')
print('Step1')
print(step1)

for i in range (0,len(g)):
if(i!=init):
for k in range(0,len(g)):
if(k!=i and k!=init):
cost = g[i][k] + step1[k]
step2[i][k] = cost
total_cost = cost
#
print('----------------------------------------------------------')
print('Step2')
print(step2)

for i in range (0,len(g)):
if(i!=init):
for k in range(0,len(g)):
if(k!=i and k!=init):
rem = []
rem.append(i)
rem.append(k)
rem.append(init)
u = set(temp1) - set(rem)
val = u.pop()
cost = g[i][k] + step2[k][val]
step3[i][k] = cost
print('----------------------------------------------------------')
print('Step3')
print(step3)

for i in range (0,len(g)-3):
for k in range(0,len(g)):
if(k!=i and k!=init):
u = Minimum(step3[k])
cost = g[i][k] + u
step4.append( cost)
print('----------------------------------------------------------')
print('Step4')
print(step4)

path.append(1)
#Minimum of Step 4
val4 = Minimum(step4)
ind4 = step4.index(val4)
path.append(ind4+1)

# Minimum of Step 3
val3 = Minimum(step3[ind4])
ind3 = step3[ind4].index(val3)
path.append(ind3 + 1)

# Minimum of Step 2
p = set(temp2) - set(path)
value = p.pop()
path.append(value)

path.append(1)

print('----------------------------------------------------------')
print('Path')
print(path)
print('----------------------------------------------------------')
print('Total Cost')
print(val4)



def main():
graph = [[0, 10, 15, 20],
[5, 0, 9, 10],
[6, 13, 0, 12],
[8, 8, 9, 0]];
print(graph)
Calc_cost(graph,0)

main()


OUTPUT:-



[[0, 10, 15, 20], [5, 0, 9, 10], [6, 13, 0, 12], [8, 8, 9, 0]]
----------------------------------------------------------
Step1
[0, 5, 6, 8]
----------------------------------------------------------
Step2
[[0, 0, 0, 0], [0, 0, 15, 18], [0, 18, 0, 20], [0, 13, 15, 0]]
----------------------------------------------------------
Step3
[[0, 0, 0, 0], [0, 0, 29, 25], [0, 31, 0, 25], [0, 23, 27, 0]]
----------------------------------------------------------
Step4
[0, 35, 40, 43]
----------------------------------------------------------
Path
[1, 2, 4, 3, 1]
----------------------------------------------------------
Total Cost
35





share|improve this answer








New contributor




Abhishikt Kadam is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$












    Your Answer





    StackExchange.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
    );
    );
    , "mathjax-editing");

    StackExchange.ifUsing("editor", function ()
    StackExchange.using("externalEditor", function ()
    StackExchange.using("snippets", function ()
    StackExchange.snippets.init();
    );
    );
    , "code-snippets");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "196"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: false,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    imageUploader:
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    ,
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );













    draft saved

    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f81865%2ftravelling-salesman-using-brute-force-and-heuristics%23new-answer', 'question_page');

    );

    Post as a guest















    Required, but never shown

























    3 Answers
    3






    active

    oldest

    votes








    3 Answers
    3






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    9












    $begingroup$

    I enjoyed the first look at the code as it's very clean, you have
    extensive docstrings and great, expressive function names. Now you know
    the deal with PEP8, but except for the one 200 character long line I
    don't think it matters much really.



    There're a few typo with the wrong spelling "algoritmh".



    The coordinates should be immutable 2-tuples. The reason being the
    safety of immutable data-structures. YMMV, but that makes it really
    obvious that those are coordinates as well.



    optimized_travelling_salesman should make a defensive copy of
    points, or you should otherwise indicate that it's destructive on that
    argument.



    Instead of if start is None: start = points[0] you could also use
    start = start or points[0] to save some space while still being
    relatively readable.



    For the algorithms the only thing I'd is not to use square root if you
    don't have to. You can basically create a distance_squared and use that
    instead of distance because the relationship
    between a smaller and bigger distance will stay the same regardless.
    That doesn't apply for the final output of course. Edit: And, as mentioned below by @JanneKarila, you can't use that for the brute-force version.






    share|improve this answer











    $endgroup$








    • 3




      $begingroup$
      Result will be different using the sum of squared distances. $1+3 = 2+2$ but $1+9 > 4+4$
      $endgroup$
      – Janne Karila
      Feb 19 '15 at 14:04
















    9












    $begingroup$

    I enjoyed the first look at the code as it's very clean, you have
    extensive docstrings and great, expressive function names. Now you know
    the deal with PEP8, but except for the one 200 character long line I
    don't think it matters much really.



    There're a few typo with the wrong spelling "algoritmh".



    The coordinates should be immutable 2-tuples. The reason being the
    safety of immutable data-structures. YMMV, but that makes it really
    obvious that those are coordinates as well.



    optimized_travelling_salesman should make a defensive copy of
    points, or you should otherwise indicate that it's destructive on that
    argument.



    Instead of if start is None: start = points[0] you could also use
    start = start or points[0] to save some space while still being
    relatively readable.



    For the algorithms the only thing I'd is not to use square root if you
    don't have to. You can basically create a distance_squared and use that
    instead of distance because the relationship
    between a smaller and bigger distance will stay the same regardless.
    That doesn't apply for the final output of course. Edit: And, as mentioned below by @JanneKarila, you can't use that for the brute-force version.






    share|improve this answer











    $endgroup$








    • 3




      $begingroup$
      Result will be different using the sum of squared distances. $1+3 = 2+2$ but $1+9 > 4+4$
      $endgroup$
      – Janne Karila
      Feb 19 '15 at 14:04














    9












    9








    9





    $begingroup$

    I enjoyed the first look at the code as it's very clean, you have
    extensive docstrings and great, expressive function names. Now you know
    the deal with PEP8, but except for the one 200 character long line I
    don't think it matters much really.



    There're a few typo with the wrong spelling "algoritmh".



    The coordinates should be immutable 2-tuples. The reason being the
    safety of immutable data-structures. YMMV, but that makes it really
    obvious that those are coordinates as well.



    optimized_travelling_salesman should make a defensive copy of
    points, or you should otherwise indicate that it's destructive on that
    argument.



    Instead of if start is None: start = points[0] you could also use
    start = start or points[0] to save some space while still being
    relatively readable.



    For the algorithms the only thing I'd is not to use square root if you
    don't have to. You can basically create a distance_squared and use that
    instead of distance because the relationship
    between a smaller and bigger distance will stay the same regardless.
    That doesn't apply for the final output of course. Edit: And, as mentioned below by @JanneKarila, you can't use that for the brute-force version.






    share|improve this answer











    $endgroup$



    I enjoyed the first look at the code as it's very clean, you have
    extensive docstrings and great, expressive function names. Now you know
    the deal with PEP8, but except for the one 200 character long line I
    don't think it matters much really.



    There're a few typo with the wrong spelling "algoritmh".



    The coordinates should be immutable 2-tuples. The reason being the
    safety of immutable data-structures. YMMV, but that makes it really
    obvious that those are coordinates as well.



    optimized_travelling_salesman should make a defensive copy of
    points, or you should otherwise indicate that it's destructive on that
    argument.



    Instead of if start is None: start = points[0] you could also use
    start = start or points[0] to save some space while still being
    relatively readable.



    For the algorithms the only thing I'd is not to use square root if you
    don't have to. You can basically create a distance_squared and use that
    instead of distance because the relationship
    between a smaller and bigger distance will stay the same regardless.
    That doesn't apply for the final output of course. Edit: And, as mentioned below by @JanneKarila, you can't use that for the brute-force version.







    share|improve this answer














    share|improve this answer



    share|improve this answer








    edited Mar 14 '18 at 21:55

























    answered Feb 18 '15 at 22:55









    feradaferada

    9,3261557




    9,3261557







    • 3




      $begingroup$
      Result will be different using the sum of squared distances. $1+3 = 2+2$ but $1+9 > 4+4$
      $endgroup$
      – Janne Karila
      Feb 19 '15 at 14:04













    • 3




      $begingroup$
      Result will be different using the sum of squared distances. $1+3 = 2+2$ but $1+9 > 4+4$
      $endgroup$
      – Janne Karila
      Feb 19 '15 at 14:04








    3




    3




    $begingroup$
    Result will be different using the sum of squared distances. $1+3 = 2+2$ but $1+9 > 4+4$
    $endgroup$
    – Janne Karila
    Feb 19 '15 at 14:04





    $begingroup$
    Result will be different using the sum of squared distances. $1+3 = 2+2$ but $1+9 > 4+4$
    $endgroup$
    – Janne Karila
    Feb 19 '15 at 14:04














    3












    $begingroup$

    Besides thanking you for posting this, I wanted to share how I edited your code to do something I needed.



    I'm implementing a survey for econ research. Part of the implementation is giving our survey team a list of addresses so that they can visit them. After geo-coding these addresses, we organized them into neighborhoods through a very simple k-means clustering process. Each member of our team is assigned a zone, therefore we needed to provide them with an optimized route within each zone.



    The issue at hand was that members of our survey need additional data on top of the location data - such as unique IDs for households and basic contact info for the household. So, somehow I needed to keep some form of identification for each coordinate so I could merge it back with the relevant data.



    I realize this might be a simple edit, but I couldn't figure out another way to have a relation between the two tables of data.



    The code is exactly the same, except for that it returns an enumerated list (enumerated at the time of input) so that you can merge it back with other data.



    I also added a haversine formula for calculating the distance between two geo-coordinates in miles.



    import numpy as np
    def haversine_enum(item1, item2):
    """
    Returns the great-circle distance between two enumearted points
    on a sphere given their indexes, longitudes, and latitudes in the
    form of a tuple.

    >>> haversine_enum((0, (3,5)), (1, (4,7)))
    154.27478490048566

    >>> haversine_enum((0, (41.325, -72.325)), (1, (41.327, -72.327)))
    0.17282397386672291
    """
    r = 3959 #radius of the earth
    r_lat = np.radians(item1[1][0])
    r_lat2 = np.radians(item2[1][0])
    delta_r_lat = np.radians(item2[1][0]-item1[1][0])
    delta_r_lon = np.radians(item2[1][1]-item1[1][1])

    a = (np.sin(delta_r_lat / 2) * np.sin(delta_r_lat / 2) +
    np.cos(r_lat) * np.cos(r_lat2) *
    np.sin(delta_r_lon / 2) * np.sin(delta_r_lon / 2))

    c = 2 * np.arctan2(np.sqrt(a), np.sqrt(1-a))

    d = r * c

    return d

    def optimized_travelling_salesman_enum(points, start=None):
    """
    Taken from:
    https://codereview.stackexchange.com/questions/81865/
    travelling-salesman-using-brute-force-and-heuristics

    As solving the problem in the brute force way is too slow,
    this function implements a simple heuristic: always
    go to the nearest city.

    Even if this algoritmh is extremely simple, it works pretty well
    giving a solution only about 25% longer than the optimal one (cit. Wikipedia),
    and runs very fast in O(N^2) time complexity.
    """

    points = list(enumerate(points))
    if start is None:
    start = points[0]

    must_visit = points
    path = [start]
    must_visit.remove(start)

    while must_visit:
    nearest = min(must_visit,
    key=lambda x: haversine_enum(path[-1], x))
    path.append(nearest)
    must_visit.remove(nearest)

    return path





    share|improve this answer











    $endgroup$












    • $begingroup$
      @Toby Speight > how it improves upon the original: 'it returns an enumerated list (enumerated at the time of input) so that you can merge it back with other data.'
      $endgroup$
      – Daniel
      Mar 14 '18 at 19:06










    • $begingroup$
      Very reasonable solution, the enumeration looks simple, otherwise maybe you could have built a dictionary putting in relation the coordinates as keys to the informations as values
      $endgroup$
      – Caridorc
      Mar 17 '18 at 10:47















    3












    $begingroup$

    Besides thanking you for posting this, I wanted to share how I edited your code to do something I needed.



    I'm implementing a survey for econ research. Part of the implementation is giving our survey team a list of addresses so that they can visit them. After geo-coding these addresses, we organized them into neighborhoods through a very simple k-means clustering process. Each member of our team is assigned a zone, therefore we needed to provide them with an optimized route within each zone.



    The issue at hand was that members of our survey need additional data on top of the location data - such as unique IDs for households and basic contact info for the household. So, somehow I needed to keep some form of identification for each coordinate so I could merge it back with the relevant data.



    I realize this might be a simple edit, but I couldn't figure out another way to have a relation between the two tables of data.



    The code is exactly the same, except for that it returns an enumerated list (enumerated at the time of input) so that you can merge it back with other data.



    I also added a haversine formula for calculating the distance between two geo-coordinates in miles.



    import numpy as np
    def haversine_enum(item1, item2):
    """
    Returns the great-circle distance between two enumearted points
    on a sphere given their indexes, longitudes, and latitudes in the
    form of a tuple.

    >>> haversine_enum((0, (3,5)), (1, (4,7)))
    154.27478490048566

    >>> haversine_enum((0, (41.325, -72.325)), (1, (41.327, -72.327)))
    0.17282397386672291
    """
    r = 3959 #radius of the earth
    r_lat = np.radians(item1[1][0])
    r_lat2 = np.radians(item2[1][0])
    delta_r_lat = np.radians(item2[1][0]-item1[1][0])
    delta_r_lon = np.radians(item2[1][1]-item1[1][1])

    a = (np.sin(delta_r_lat / 2) * np.sin(delta_r_lat / 2) +
    np.cos(r_lat) * np.cos(r_lat2) *
    np.sin(delta_r_lon / 2) * np.sin(delta_r_lon / 2))

    c = 2 * np.arctan2(np.sqrt(a), np.sqrt(1-a))

    d = r * c

    return d

    def optimized_travelling_salesman_enum(points, start=None):
    """
    Taken from:
    https://codereview.stackexchange.com/questions/81865/
    travelling-salesman-using-brute-force-and-heuristics

    As solving the problem in the brute force way is too slow,
    this function implements a simple heuristic: always
    go to the nearest city.

    Even if this algoritmh is extremely simple, it works pretty well
    giving a solution only about 25% longer than the optimal one (cit. Wikipedia),
    and runs very fast in O(N^2) time complexity.
    """

    points = list(enumerate(points))
    if start is None:
    start = points[0]

    must_visit = points
    path = [start]
    must_visit.remove(start)

    while must_visit:
    nearest = min(must_visit,
    key=lambda x: haversine_enum(path[-1], x))
    path.append(nearest)
    must_visit.remove(nearest)

    return path





    share|improve this answer











    $endgroup$












    • $begingroup$
      @Toby Speight > how it improves upon the original: 'it returns an enumerated list (enumerated at the time of input) so that you can merge it back with other data.'
      $endgroup$
      – Daniel
      Mar 14 '18 at 19:06










    • $begingroup$
      Very reasonable solution, the enumeration looks simple, otherwise maybe you could have built a dictionary putting in relation the coordinates as keys to the informations as values
      $endgroup$
      – Caridorc
      Mar 17 '18 at 10:47













    3












    3








    3





    $begingroup$

    Besides thanking you for posting this, I wanted to share how I edited your code to do something I needed.



    I'm implementing a survey for econ research. Part of the implementation is giving our survey team a list of addresses so that they can visit them. After geo-coding these addresses, we organized them into neighborhoods through a very simple k-means clustering process. Each member of our team is assigned a zone, therefore we needed to provide them with an optimized route within each zone.



    The issue at hand was that members of our survey need additional data on top of the location data - such as unique IDs for households and basic contact info for the household. So, somehow I needed to keep some form of identification for each coordinate so I could merge it back with the relevant data.



    I realize this might be a simple edit, but I couldn't figure out another way to have a relation between the two tables of data.



    The code is exactly the same, except for that it returns an enumerated list (enumerated at the time of input) so that you can merge it back with other data.



    I also added a haversine formula for calculating the distance between two geo-coordinates in miles.



    import numpy as np
    def haversine_enum(item1, item2):
    """
    Returns the great-circle distance between two enumearted points
    on a sphere given their indexes, longitudes, and latitudes in the
    form of a tuple.

    >>> haversine_enum((0, (3,5)), (1, (4,7)))
    154.27478490048566

    >>> haversine_enum((0, (41.325, -72.325)), (1, (41.327, -72.327)))
    0.17282397386672291
    """
    r = 3959 #radius of the earth
    r_lat = np.radians(item1[1][0])
    r_lat2 = np.radians(item2[1][0])
    delta_r_lat = np.radians(item2[1][0]-item1[1][0])
    delta_r_lon = np.radians(item2[1][1]-item1[1][1])

    a = (np.sin(delta_r_lat / 2) * np.sin(delta_r_lat / 2) +
    np.cos(r_lat) * np.cos(r_lat2) *
    np.sin(delta_r_lon / 2) * np.sin(delta_r_lon / 2))

    c = 2 * np.arctan2(np.sqrt(a), np.sqrt(1-a))

    d = r * c

    return d

    def optimized_travelling_salesman_enum(points, start=None):
    """
    Taken from:
    https://codereview.stackexchange.com/questions/81865/
    travelling-salesman-using-brute-force-and-heuristics

    As solving the problem in the brute force way is too slow,
    this function implements a simple heuristic: always
    go to the nearest city.

    Even if this algoritmh is extremely simple, it works pretty well
    giving a solution only about 25% longer than the optimal one (cit. Wikipedia),
    and runs very fast in O(N^2) time complexity.
    """

    points = list(enumerate(points))
    if start is None:
    start = points[0]

    must_visit = points
    path = [start]
    must_visit.remove(start)

    while must_visit:
    nearest = min(must_visit,
    key=lambda x: haversine_enum(path[-1], x))
    path.append(nearest)
    must_visit.remove(nearest)

    return path





    share|improve this answer











    $endgroup$



    Besides thanking you for posting this, I wanted to share how I edited your code to do something I needed.



    I'm implementing a survey for econ research. Part of the implementation is giving our survey team a list of addresses so that they can visit them. After geo-coding these addresses, we organized them into neighborhoods through a very simple k-means clustering process. Each member of our team is assigned a zone, therefore we needed to provide them with an optimized route within each zone.



    The issue at hand was that members of our survey need additional data on top of the location data - such as unique IDs for households and basic contact info for the household. So, somehow I needed to keep some form of identification for each coordinate so I could merge it back with the relevant data.



    I realize this might be a simple edit, but I couldn't figure out another way to have a relation between the two tables of data.



    The code is exactly the same, except for that it returns an enumerated list (enumerated at the time of input) so that you can merge it back with other data.



    I also added a haversine formula for calculating the distance between two geo-coordinates in miles.



    import numpy as np
    def haversine_enum(item1, item2):
    """
    Returns the great-circle distance between two enumearted points
    on a sphere given their indexes, longitudes, and latitudes in the
    form of a tuple.

    >>> haversine_enum((0, (3,5)), (1, (4,7)))
    154.27478490048566

    >>> haversine_enum((0, (41.325, -72.325)), (1, (41.327, -72.327)))
    0.17282397386672291
    """
    r = 3959 #radius of the earth
    r_lat = np.radians(item1[1][0])
    r_lat2 = np.radians(item2[1][0])
    delta_r_lat = np.radians(item2[1][0]-item1[1][0])
    delta_r_lon = np.radians(item2[1][1]-item1[1][1])

    a = (np.sin(delta_r_lat / 2) * np.sin(delta_r_lat / 2) +
    np.cos(r_lat) * np.cos(r_lat2) *
    np.sin(delta_r_lon / 2) * np.sin(delta_r_lon / 2))

    c = 2 * np.arctan2(np.sqrt(a), np.sqrt(1-a))

    d = r * c

    return d

    def optimized_travelling_salesman_enum(points, start=None):
    """
    Taken from:
    https://codereview.stackexchange.com/questions/81865/
    travelling-salesman-using-brute-force-and-heuristics

    As solving the problem in the brute force way is too slow,
    this function implements a simple heuristic: always
    go to the nearest city.

    Even if this algoritmh is extremely simple, it works pretty well
    giving a solution only about 25% longer than the optimal one (cit. Wikipedia),
    and runs very fast in O(N^2) time complexity.
    """

    points = list(enumerate(points))
    if start is None:
    start = points[0]

    must_visit = points
    path = [start]
    must_visit.remove(start)

    while must_visit:
    nearest = min(must_visit,
    key=lambda x: haversine_enum(path[-1], x))
    path.append(nearest)
    must_visit.remove(nearest)

    return path






    share|improve this answer














    share|improve this answer



    share|improve this answer








    edited Mar 14 '18 at 19:47

























    answered Mar 14 '18 at 17:33









    Manuel MartinezManuel Martinez

    315




    315











    • $begingroup$
      @Toby Speight > how it improves upon the original: 'it returns an enumerated list (enumerated at the time of input) so that you can merge it back with other data.'
      $endgroup$
      – Daniel
      Mar 14 '18 at 19:06










    • $begingroup$
      Very reasonable solution, the enumeration looks simple, otherwise maybe you could have built a dictionary putting in relation the coordinates as keys to the informations as values
      $endgroup$
      – Caridorc
      Mar 17 '18 at 10:47
















    • $begingroup$
      @Toby Speight > how it improves upon the original: 'it returns an enumerated list (enumerated at the time of input) so that you can merge it back with other data.'
      $endgroup$
      – Daniel
      Mar 14 '18 at 19:06










    • $begingroup$
      Very reasonable solution, the enumeration looks simple, otherwise maybe you could have built a dictionary putting in relation the coordinates as keys to the informations as values
      $endgroup$
      – Caridorc
      Mar 17 '18 at 10:47















    $begingroup$
    @Toby Speight > how it improves upon the original: 'it returns an enumerated list (enumerated at the time of input) so that you can merge it back with other data.'
    $endgroup$
    – Daniel
    Mar 14 '18 at 19:06




    $begingroup$
    @Toby Speight > how it improves upon the original: 'it returns an enumerated list (enumerated at the time of input) so that you can merge it back with other data.'
    $endgroup$
    – Daniel
    Mar 14 '18 at 19:06












    $begingroup$
    Very reasonable solution, the enumeration looks simple, otherwise maybe you could have built a dictionary putting in relation the coordinates as keys to the informations as values
    $endgroup$
    – Caridorc
    Mar 17 '18 at 10:47




    $begingroup$
    Very reasonable solution, the enumeration looks simple, otherwise maybe you could have built a dictionary putting in relation the coordinates as keys to the informations as values
    $endgroup$
    – Caridorc
    Mar 17 '18 at 10:47











    0












    $begingroup$

    Python code for Travelling salesman problem is:-



    import numpy as np
    import math
    def Minimum(s):
    low = math.inf
    for i in s:
    if i < low and i!=0:
    low = i
    return low

    def Calc_cost(g,init):
    path =[]
    step1 = []

    step2 = [[0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0]];

    step3 = [[0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0],
    [0, 0, 0, 0]];

    step4 =[]
    step4.append(0)

    temp1 = [0,1,2,3]
    temp2 = [1, 2, 3,4]

    for i in range (0,len(g)):
    step1.append(g[i][init])
    print('----------------------------------------------------------')
    print('Step1')
    print(step1)

    for i in range (0,len(g)):
    if(i!=init):
    for k in range(0,len(g)):
    if(k!=i and k!=init):
    cost = g[i][k] + step1[k]
    step2[i][k] = cost
    total_cost = cost
    #
    print('----------------------------------------------------------')
    print('Step2')
    print(step2)

    for i in range (0,len(g)):
    if(i!=init):
    for k in range(0,len(g)):
    if(k!=i and k!=init):
    rem = []
    rem.append(i)
    rem.append(k)
    rem.append(init)
    u = set(temp1) - set(rem)
    val = u.pop()
    cost = g[i][k] + step2[k][val]
    step3[i][k] = cost
    print('----------------------------------------------------------')
    print('Step3')
    print(step3)

    for i in range (0,len(g)-3):
    for k in range(0,len(g)):
    if(k!=i and k!=init):
    u = Minimum(step3[k])
    cost = g[i][k] + u
    step4.append( cost)
    print('----------------------------------------------------------')
    print('Step4')
    print(step4)

    path.append(1)
    #Minimum of Step 4
    val4 = Minimum(step4)
    ind4 = step4.index(val4)
    path.append(ind4+1)

    # Minimum of Step 3
    val3 = Minimum(step3[ind4])
    ind3 = step3[ind4].index(val3)
    path.append(ind3 + 1)

    # Minimum of Step 2
    p = set(temp2) - set(path)
    value = p.pop()
    path.append(value)

    path.append(1)

    print('----------------------------------------------------------')
    print('Path')
    print(path)
    print('----------------------------------------------------------')
    print('Total Cost')
    print(val4)



    def main():
    graph = [[0, 10, 15, 20],
    [5, 0, 9, 10],
    [6, 13, 0, 12],
    [8, 8, 9, 0]];
    print(graph)
    Calc_cost(graph,0)

    main()


    OUTPUT:-



    [[0, 10, 15, 20], [5, 0, 9, 10], [6, 13, 0, 12], [8, 8, 9, 0]]
    ----------------------------------------------------------
    Step1
    [0, 5, 6, 8]
    ----------------------------------------------------------
    Step2
    [[0, 0, 0, 0], [0, 0, 15, 18], [0, 18, 0, 20], [0, 13, 15, 0]]
    ----------------------------------------------------------
    Step3
    [[0, 0, 0, 0], [0, 0, 29, 25], [0, 31, 0, 25], [0, 23, 27, 0]]
    ----------------------------------------------------------
    Step4
    [0, 35, 40, 43]
    ----------------------------------------------------------
    Path
    [1, 2, 4, 3, 1]
    ----------------------------------------------------------
    Total Cost
    35





    share|improve this answer








    New contributor




    Abhishikt Kadam is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.






    $endgroup$

















      0












      $begingroup$

      Python code for Travelling salesman problem is:-



      import numpy as np
      import math
      def Minimum(s):
      low = math.inf
      for i in s:
      if i < low and i!=0:
      low = i
      return low

      def Calc_cost(g,init):
      path =[]
      step1 = []

      step2 = [[0, 0, 0, 0],
      [0, 0, 0, 0],
      [0, 0, 0, 0],
      [0, 0, 0, 0]];

      step3 = [[0, 0, 0, 0],
      [0, 0, 0, 0],
      [0, 0, 0, 0],
      [0, 0, 0, 0]];

      step4 =[]
      step4.append(0)

      temp1 = [0,1,2,3]
      temp2 = [1, 2, 3,4]

      for i in range (0,len(g)):
      step1.append(g[i][init])
      print('----------------------------------------------------------')
      print('Step1')
      print(step1)

      for i in range (0,len(g)):
      if(i!=init):
      for k in range(0,len(g)):
      if(k!=i and k!=init):
      cost = g[i][k] + step1[k]
      step2[i][k] = cost
      total_cost = cost
      #
      print('----------------------------------------------------------')
      print('Step2')
      print(step2)

      for i in range (0,len(g)):
      if(i!=init):
      for k in range(0,len(g)):
      if(k!=i and k!=init):
      rem = []
      rem.append(i)
      rem.append(k)
      rem.append(init)
      u = set(temp1) - set(rem)
      val = u.pop()
      cost = g[i][k] + step2[k][val]
      step3[i][k] = cost
      print('----------------------------------------------------------')
      print('Step3')
      print(step3)

      for i in range (0,len(g)-3):
      for k in range(0,len(g)):
      if(k!=i and k!=init):
      u = Minimum(step3[k])
      cost = g[i][k] + u
      step4.append( cost)
      print('----------------------------------------------------------')
      print('Step4')
      print(step4)

      path.append(1)
      #Minimum of Step 4
      val4 = Minimum(step4)
      ind4 = step4.index(val4)
      path.append(ind4+1)

      # Minimum of Step 3
      val3 = Minimum(step3[ind4])
      ind3 = step3[ind4].index(val3)
      path.append(ind3 + 1)

      # Minimum of Step 2
      p = set(temp2) - set(path)
      value = p.pop()
      path.append(value)

      path.append(1)

      print('----------------------------------------------------------')
      print('Path')
      print(path)
      print('----------------------------------------------------------')
      print('Total Cost')
      print(val4)



      def main():
      graph = [[0, 10, 15, 20],
      [5, 0, 9, 10],
      [6, 13, 0, 12],
      [8, 8, 9, 0]];
      print(graph)
      Calc_cost(graph,0)

      main()


      OUTPUT:-



      [[0, 10, 15, 20], [5, 0, 9, 10], [6, 13, 0, 12], [8, 8, 9, 0]]
      ----------------------------------------------------------
      Step1
      [0, 5, 6, 8]
      ----------------------------------------------------------
      Step2
      [[0, 0, 0, 0], [0, 0, 15, 18], [0, 18, 0, 20], [0, 13, 15, 0]]
      ----------------------------------------------------------
      Step3
      [[0, 0, 0, 0], [0, 0, 29, 25], [0, 31, 0, 25], [0, 23, 27, 0]]
      ----------------------------------------------------------
      Step4
      [0, 35, 40, 43]
      ----------------------------------------------------------
      Path
      [1, 2, 4, 3, 1]
      ----------------------------------------------------------
      Total Cost
      35





      share|improve this answer








      New contributor




      Abhishikt Kadam is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






      $endgroup$















        0












        0








        0





        $begingroup$

        Python code for Travelling salesman problem is:-



        import numpy as np
        import math
        def Minimum(s):
        low = math.inf
        for i in s:
        if i < low and i!=0:
        low = i
        return low

        def Calc_cost(g,init):
        path =[]
        step1 = []

        step2 = [[0, 0, 0, 0],
        [0, 0, 0, 0],
        [0, 0, 0, 0],
        [0, 0, 0, 0]];

        step3 = [[0, 0, 0, 0],
        [0, 0, 0, 0],
        [0, 0, 0, 0],
        [0, 0, 0, 0]];

        step4 =[]
        step4.append(0)

        temp1 = [0,1,2,3]
        temp2 = [1, 2, 3,4]

        for i in range (0,len(g)):
        step1.append(g[i][init])
        print('----------------------------------------------------------')
        print('Step1')
        print(step1)

        for i in range (0,len(g)):
        if(i!=init):
        for k in range(0,len(g)):
        if(k!=i and k!=init):
        cost = g[i][k] + step1[k]
        step2[i][k] = cost
        total_cost = cost
        #
        print('----------------------------------------------------------')
        print('Step2')
        print(step2)

        for i in range (0,len(g)):
        if(i!=init):
        for k in range(0,len(g)):
        if(k!=i and k!=init):
        rem = []
        rem.append(i)
        rem.append(k)
        rem.append(init)
        u = set(temp1) - set(rem)
        val = u.pop()
        cost = g[i][k] + step2[k][val]
        step3[i][k] = cost
        print('----------------------------------------------------------')
        print('Step3')
        print(step3)

        for i in range (0,len(g)-3):
        for k in range(0,len(g)):
        if(k!=i and k!=init):
        u = Minimum(step3[k])
        cost = g[i][k] + u
        step4.append( cost)
        print('----------------------------------------------------------')
        print('Step4')
        print(step4)

        path.append(1)
        #Minimum of Step 4
        val4 = Minimum(step4)
        ind4 = step4.index(val4)
        path.append(ind4+1)

        # Minimum of Step 3
        val3 = Minimum(step3[ind4])
        ind3 = step3[ind4].index(val3)
        path.append(ind3 + 1)

        # Minimum of Step 2
        p = set(temp2) - set(path)
        value = p.pop()
        path.append(value)

        path.append(1)

        print('----------------------------------------------------------')
        print('Path')
        print(path)
        print('----------------------------------------------------------')
        print('Total Cost')
        print(val4)



        def main():
        graph = [[0, 10, 15, 20],
        [5, 0, 9, 10],
        [6, 13, 0, 12],
        [8, 8, 9, 0]];
        print(graph)
        Calc_cost(graph,0)

        main()


        OUTPUT:-



        [[0, 10, 15, 20], [5, 0, 9, 10], [6, 13, 0, 12], [8, 8, 9, 0]]
        ----------------------------------------------------------
        Step1
        [0, 5, 6, 8]
        ----------------------------------------------------------
        Step2
        [[0, 0, 0, 0], [0, 0, 15, 18], [0, 18, 0, 20], [0, 13, 15, 0]]
        ----------------------------------------------------------
        Step3
        [[0, 0, 0, 0], [0, 0, 29, 25], [0, 31, 0, 25], [0, 23, 27, 0]]
        ----------------------------------------------------------
        Step4
        [0, 35, 40, 43]
        ----------------------------------------------------------
        Path
        [1, 2, 4, 3, 1]
        ----------------------------------------------------------
        Total Cost
        35





        share|improve this answer








        New contributor




        Abhishikt Kadam is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.






        $endgroup$



        Python code for Travelling salesman problem is:-



        import numpy as np
        import math
        def Minimum(s):
        low = math.inf
        for i in s:
        if i < low and i!=0:
        low = i
        return low

        def Calc_cost(g,init):
        path =[]
        step1 = []

        step2 = [[0, 0, 0, 0],
        [0, 0, 0, 0],
        [0, 0, 0, 0],
        [0, 0, 0, 0]];

        step3 = [[0, 0, 0, 0],
        [0, 0, 0, 0],
        [0, 0, 0, 0],
        [0, 0, 0, 0]];

        step4 =[]
        step4.append(0)

        temp1 = [0,1,2,3]
        temp2 = [1, 2, 3,4]

        for i in range (0,len(g)):
        step1.append(g[i][init])
        print('----------------------------------------------------------')
        print('Step1')
        print(step1)

        for i in range (0,len(g)):
        if(i!=init):
        for k in range(0,len(g)):
        if(k!=i and k!=init):
        cost = g[i][k] + step1[k]
        step2[i][k] = cost
        total_cost = cost
        #
        print('----------------------------------------------------------')
        print('Step2')
        print(step2)

        for i in range (0,len(g)):
        if(i!=init):
        for k in range(0,len(g)):
        if(k!=i and k!=init):
        rem = []
        rem.append(i)
        rem.append(k)
        rem.append(init)
        u = set(temp1) - set(rem)
        val = u.pop()
        cost = g[i][k] + step2[k][val]
        step3[i][k] = cost
        print('----------------------------------------------------------')
        print('Step3')
        print(step3)

        for i in range (0,len(g)-3):
        for k in range(0,len(g)):
        if(k!=i and k!=init):
        u = Minimum(step3[k])
        cost = g[i][k] + u
        step4.append( cost)
        print('----------------------------------------------------------')
        print('Step4')
        print(step4)

        path.append(1)
        #Minimum of Step 4
        val4 = Minimum(step4)
        ind4 = step4.index(val4)
        path.append(ind4+1)

        # Minimum of Step 3
        val3 = Minimum(step3[ind4])
        ind3 = step3[ind4].index(val3)
        path.append(ind3 + 1)

        # Minimum of Step 2
        p = set(temp2) - set(path)
        value = p.pop()
        path.append(value)

        path.append(1)

        print('----------------------------------------------------------')
        print('Path')
        print(path)
        print('----------------------------------------------------------')
        print('Total Cost')
        print(val4)



        def main():
        graph = [[0, 10, 15, 20],
        [5, 0, 9, 10],
        [6, 13, 0, 12],
        [8, 8, 9, 0]];
        print(graph)
        Calc_cost(graph,0)

        main()


        OUTPUT:-



        [[0, 10, 15, 20], [5, 0, 9, 10], [6, 13, 0, 12], [8, 8, 9, 0]]
        ----------------------------------------------------------
        Step1
        [0, 5, 6, 8]
        ----------------------------------------------------------
        Step2
        [[0, 0, 0, 0], [0, 0, 15, 18], [0, 18, 0, 20], [0, 13, 15, 0]]
        ----------------------------------------------------------
        Step3
        [[0, 0, 0, 0], [0, 0, 29, 25], [0, 31, 0, 25], [0, 23, 27, 0]]
        ----------------------------------------------------------
        Step4
        [0, 35, 40, 43]
        ----------------------------------------------------------
        Path
        [1, 2, 4, 3, 1]
        ----------------------------------------------------------
        Total Cost
        35






        share|improve this answer








        New contributor




        Abhishikt Kadam is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.









        share|improve this answer



        share|improve this answer






        New contributor




        Abhishikt Kadam is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.









        answered 11 mins ago









        Abhishikt KadamAbhishikt Kadam

        1




        1




        New contributor




        Abhishikt Kadam is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.





        New contributor





        Abhishikt Kadam is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.






        Abhishikt Kadam is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
        Check out our Code of Conduct.



























            draft saved

            draft discarded
















































            Thanks for contributing an answer to Code Review Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid


            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.

            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f81865%2ftravelling-salesman-using-brute-force-and-heuristics%23new-answer', 'question_page');

            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            名間水力發電廠 目录 沿革 設施 鄰近設施 註釋 外部連結 导航菜单23°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.7113923°50′10″N 120°42′41″E / 23.83611°N 120.71139°E / 23.83611; 120.71139計畫概要原始内容臺灣第一座BOT 模式開發的水力發電廠-名間水力電廠名間水力發電廠 水利署首件BOT案原始内容《小檔案》名間電廠 首座BOT水力發電廠原始内容名間電廠BOT - 經濟部水利署中區水資源局

            Prove that NP is closed under karp reduction?Space(n) not closed under Karp reductions - what about NTime(n)?Class P is closed under rotation?Prove or disprove that $NL$ is closed under polynomial many-one reductions$mathbfNC_2$ is closed under log-space reductionOn Karp reductionwhen can I know if a class (complexity) is closed under reduction (cook/karp)Check if class $PSPACE$ is closed under polyonomially space reductionIs NPSPACE also closed under polynomial-time reduction and under log-space reduction?Prove PSPACE is closed under complement?Prove PSPACE is closed under union?

            Is my guitar’s action too high? Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)Strings too stiff on a recently purchased acoustic guitar | Cort AD880CEIs the action of my guitar really high?Μy little finger is too weak to play guitarWith guitar, how long should I give my fingers to strengthen / callous?When playing a fret the guitar sounds mutedPlaying (Barre) chords up the guitar neckI think my guitar strings are wound too tight and I can't play barre chordsF barre chord on an SG guitarHow to find to the right strings of a barre chord by feel?High action on higher fret on my steel acoustic guitar