Quinty - 2 months ago 10

Python Question

I have a list of tuples and an individual point in python e.g. [(1,2) , (2,5), (6,7), (9,3)] and (2,1) , and I want to figure out the fastest path possible created by all combinations of the individual point to the list of points.(Basically I want to find the most efficient way to get to all of the points starting from (2,1)). I have a manhattanDistance function that can take it 2 points and output the distance. However, my algorithm is giving me inconsistent answers (The heuristic is off for some reason)

What would be the correct way to accomplish this?

Here is my previous algorithm:

`def bestPath(currentPoint,goalList):`

sum = 0

bestList = []

while len(goallist) > 0:

for point in list:

bestList.append((manhattanD(point,currentPoint),point))

bestTup = min(bestList)

bestList = []

dist = bestTup[0]

newP = bestTup[1]

currentPoint = newP

sum += dist

return sum

Answer

Since you don't have so many point, you can easily use a solution that try every possibility.

Here is what you can do:

First get all combinations:

```
>>> list_of_points = [(1,2) , (2,5), (6,7), (9,3)]
>>> list(itertools.permutations(list_of_points))
[((1, 2), (2, 5), (6, 7), (9, 3)),
((1, 2), (2, 5), (9, 3), (6, 7)),
((1, 2), (6, 7), (2, 5), (9, 3)),
((1, 2), (6, 7), (9, 3), (2, 5)),
((1, 2), (9, 3), (2, 5), (6, 7)),
((1, 2), (9, 3), (6, 7), (2, 5)),
((2, 5), (1, 2), (6, 7), (9, 3)),
((2, 5), (1, 2), (9, 3), (6, 7)),
((2, 5), (6, 7), (1, 2), (9, 3)),
((2, 5), (6, 7), (9, 3), (1, 2)),
((2, 5), (9, 3), (1, 2), (6, 7)),
((2, 5), (9, 3), (6, 7), (1, 2)),
((6, 7), (1, 2), (2, 5), (9, 3)),
((6, 7), (1, 2), (9, 3), (2, 5)),
((6, 7), (2, 5), (1, 2), (9, 3)),
((6, 7), (2, 5), (9, 3), (1, 2)),
((6, 7), (9, 3), (1, 2), (2, 5)),
((6, 7), (9, 3), (2, 5), (1, 2)),
((9, 3), (1, 2), (2, 5), (6, 7)),
((9, 3), (1, 2), (6, 7), (2, 5)),
((9, 3), (2, 5), (1, 2), (6, 7)),
((9, 3), (2, 5), (6, 7), (1, 2)),
((9, 3), (6, 7), (1, 2), (2, 5)),
((9, 3), (6, 7), (2, 5), (1, 2))]
```

Then create a function that give you the length of a combination:

```
def combination_length(start_point, combination):
lenght = 0
previous = start_point
for elem in combination:
lenght += manhattanDistance(previous, elem)
return length
```

Finally a function that test every possibility:

```
def get_shortest_path(start_point, list_of_point):
min = sys.maxint
combination_min = None
list_of_combinations = list(itertools.permutations(list_of_points))
for combination in list_of_combination:
length = combination_length(start_point, combination)
if length < min:
min = length
combination_min = combination
return combination_min
```

Then finally you can have:

```
import sys, itertools
def combination_length(start_point, combination):
lenght = 0
previous = start_point
for elem in combination:
lenght += manhattanDistance(previous, elem)
return length
def get_shortest_path(start_point, list_of_point):
min = sys.maxint
combination_min = None
list_of_combinations = list(itertools.permutations(list_of_points))
for combination in list_of_combination:
length = combination_length(start_point, combination)
if length < min:
min = length
combination_min = combination
return combination_min
list_of_points = [(1,2) , (2,5), (6,7), (9,3)]
print get_shortest_path((2,1), list_of_points)
```

Source (Stackoverflow)

Comments