André Hatlo-Johansen - 1 year ago 61

Python Question

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)
```