André Hatlo-Johansen André Hatlo-Johansen - 1 month ago 13
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

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)