Andr&#233; Hatlo-Johansen - 1 year ago 80
Python Question

# Python algorithm, not returning what it should be returning

TSP random iterative algorithm in python

I'm pretty much new too python. Picking it up as i go along. The problem i am struck with now is probably a very arbitrary problem; but i've given up. When returning the "best" out of all my iterative paths, it returns the last one posted. I cant understand why it does this. The if statement should sort the best path and cost until the end of the while statement.

The algorithm creates random different paths for my matrix too then calculate the cost of each tour, if said tour is cheaper than the previous tour the new tour is set too the best tour.

But it doesnt.

``````from random import randint
from random import shuffle
from time import *

class main():

def calc(self, path, matrix, w):

pathen = path
matrix = matrix
nCost = 0

for x in range(int(w)):
if pathen[x] == 0:
first = x
prev = x

for x in range(int(w)):
for y in range(int(w)):
if pathen[y] == x:
next = y

nCost += matrix[prev][next]
prev = next

nCost += matrix[prev][first]

return nCost

def ranIterative(self, matrix, w, stop):
best = 9999
path = [0 for x in range(int(w))]
bestPath = path

print(path)

while stop:

cost = 0

for x in range(int(w)):
path[x] = x

shuffle(path)

print(path)

for x in range(int(w)):
if path[x] == 0:
first = x
prev = x

for x in range(1, int(w)):
for y in range(int(w)):
if path[y] == x:
next = y

cost += matrix[prev][next]

prev = next

cost += matrix[prev][first]

print("Cost: " + str(cost))
print("Bst: " + str(best))

if cost < best:
best = cost
bestPath = path
bestest = bestPath
print(path)
print("Best path1: " + str(bestPath))

stop -= 1
print("Best path2: " + str(bestPath))

print("Best path3: " + str(bestPath))
print("Best path3: " + str(bestest))
return bestest

def matrix(self, w):
matrix = [[0 for x in range(int(w))] for y in range(int(w))]

for x in range(int(w)):
for y in range(int(w)):
if y < x:
matrix[x][y] = randint(1, 9)
matrix[y][x] = matrix[x][y]
return matrix

main = main()
print("How many cities?")
w = input()
matrix = main.matrix(int(w))
print("How many iterations?")
stop = input()
path1 = main.ranIterative(matrix, int(w), int(stop))
cost = main.calc(path1, matrix, int(w))
print("With " + str(stop) + " iterations on " + str(w) + " cities gives:")
print("Best path :" + str(path1))
print("Costs: " + str(cost))
``````

OUTPUT:

``````How many cities?
5
How many iterations?
10
[0, 0, 0, 0, 0]
[0, 1, 3, 4, 2]
Cost: 30
Bst: 9999
[0, 1, 3, 4, 2]
Best path1: [0, 1, 3, 4, 2]
Best path2: [0, 1, 3, 4, 2]
[0, 3, 4, 2, 1]
Cost: 28
Bst: 30
[0, 3, 4, 2, 1]
Best path1: [0, 3, 4, 2, 1]
Best path2: [0, 3, 4, 2, 1]
[4, 3, 0, 1, 2]
Cost: 29
Bst: 28
Best path2: [4, 3, 0, 1, 2]
[3, 1, 4, 0, 2]
Cost: 25
Bst: 28
[3, 1, 4, 0, 2]
Best path1: [3, 1, 4, 0, 2]
Best path2: [3, 1, 4, 0, 2]
[0, 4, 3, 1, 2]
Cost: 33
Bst: 25
Best path2: [0, 4, 3, 1, 2]
[2, 0, 1, 3, 4]
Cost: 26
Bst: 25
Best path2: [2, 0, 1, 3, 4]
[3, 0, 2, 4, 1]
Cost: 28
Bst: 25
Best path2: [3, 0, 2, 4, 1]
[2, 3, 0, 4, 1]
Cost: 32
Bst: 25
Best path2: [2, 3, 0, 4, 1]
[0, 1, 3, 2, 4]
Cost: 32
Bst: 25
Best path2: [0, 1, 3, 2, 4]
[2, 1, 4, 0, 3]
Cost: 32
Bst: 25
Best path2: [2, 1, 4, 0, 3]
Best path3: [2, 1, 4, 0, 3]
Best path3: [2, 1, 4, 0, 3]
With 10 iterations on 5 cities gives:
Best path :[2, 1, 4, 0, 3]
Costs: 32
``````

As you see, my result is very wrong for such a simple task.
I cant seem to find out how too fix this problem.

Answer Source

you have to make a difference between what's mutable (`list`, `dict`,`set`, ...) and what isn't (`int`, `float`, `str`, `tuple`, ...)

Since `path` is a `list` so it is mutable, the classical error is this:

``````bestPath = path
``````

you think you're storing the best path (and freezing it) to `bestPath` variable, but you're just getting another reference to the `path` array. Subsequent changes on `path` reflect on `bestPath` and you always get the last value computed.

(that would work for a value like an integer, a float, a string because they're stored by immutable types: modifying the original wouldn't modify the copy)

Fix it by creating a copy for instance like this:

``````bestPath = list(path)
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download