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”
$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()
python traveling-salesman
$endgroup$
|
show 2 more comments
$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()
python traveling-salesman
$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 justTrue
.
$endgroup$
– jonrsharpe
Feb 18 '15 at 23:08
$begingroup$
optimized_travelling_salesman
feels like a misnomer to me, probably should begreedy_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
|
show 2 more comments
$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()
python traveling-salesman
$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
python traveling-salesman
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 justTrue
.
$endgroup$
– jonrsharpe
Feb 18 '15 at 23:08
$begingroup$
optimized_travelling_salesman
feels like a misnomer to me, probably should begreedy_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
|
show 2 more comments
$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 justTrue
.
$endgroup$
– jonrsharpe
Feb 18 '15 at 23:08
$begingroup$
optimized_travelling_salesman
feels like a misnomer to me, probably should begreedy_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
|
show 2 more comments
3 Answers
3
active
oldest
votes
$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 ofpoints
, or you should otherwise indicate that it's destructive on that
argument.
Instead of if start is None: start = points[0]
you could also usestart = 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.
$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
add a comment |
$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
$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
add a comment |
$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
New contributor
$endgroup$
add a comment |
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
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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 ofpoints
, or you should otherwise indicate that it's destructive on that
argument.
Instead of if start is None: start = points[0]
you could also usestart = 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.
$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
add a comment |
$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 ofpoints
, or you should otherwise indicate that it's destructive on that
argument.
Instead of if start is None: start = points[0]
you could also usestart = 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.
$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
add a comment |
$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 ofpoints
, or you should otherwise indicate that it's destructive on that
argument.
Instead of if start is None: start = points[0]
you could also usestart = 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.
$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 ofpoints
, or you should otherwise indicate that it's destructive on that
argument.
Instead of if start is None: start = points[0]
you could also usestart = 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.
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
add a comment |
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
add a comment |
$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
$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
add a comment |
$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
$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
add a comment |
$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
$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
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
add a comment |
$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
add a comment |
$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
New contributor
$endgroup$
add a comment |
$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
New contributor
$endgroup$
add a comment |
$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
New contributor
$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
New contributor
New contributor
answered 11 mins ago
Abhishikt KadamAbhishikt Kadam
1
1
New contributor
New contributor
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
$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 justTrue
.$endgroup$
– jonrsharpe
Feb 18 '15 at 23:08
$begingroup$
optimized_travelling_salesman
feels like a misnomer to me, probably should begreedy_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