Python算法，不返回它应该返回的内容

Question

python中的TSP随机迭代算法

我也是新来的。我边走边捡。我现在遇到的问题可能是一个非常武断的问题；但我已经放弃了。当返回所有迭代路径中的“最佳”时，它将返回最后发布的路径。我不明白为什么会这样。if语句应该对最佳路径和开销进行排序，直到while语句结束

算法也为我的矩阵创建随机不同的路径，然后计算每次旅行的成本，如果所说的旅行比上一次旅行便宜，那么新的旅行也被设置为最佳旅行

但事实并非如此

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

输出：

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

正如你所看到的，对于这样一个简单的任务，我的结果是非常错误的。 我似乎不知道该怎么解决这个问题

Answer 1

你必须区分什么是可变的（list，dict，set，…）和什么不是可变的（int，float，str，tuple，…）

因为path是list，所以它是可变的，经典的错误是：

bestPath = path

您认为您正在存储（并冻结）到bestPath变量的最佳路径，但您只是得到了对path数组的另一个引用。对path的后续更改反映在bestPath上，并且您总是得到最后计算的值

（这适用于整数、浮点、字符串等值，因为它们由不可变类型存储：修改原始值不会修改副本）

通过创建一个副本来修复它，例如：

bestPath = list(path)