最近邻居(图论)的 Python 实现由于通过引用而不是值传递的多维数组而无法工作

Question

我尝试构建最近邻算法，通过选择权重最小的节点前往所有节点，然后重复直到遍历所有节点，找到一条跨越所有节点的路线。我已经对其进行了测试，但由于数组是通过引用而不是通过值传递的，因此代码似乎无法正常工作。尽管使用了 [:]

我哪里做错了？任何帮助将不胜感激

def nearest_neighbour(matrix):
    shortest = sum(row[0] for row in matrix[:])+1
    best_route = None

    for row_index in range(len(matrix[:])):
        test_time = 0
        route = [row_index]
        temp_matrix = matrix[:]
        index = row_index
        for i in temp_matrix:

            for row in temp_matrix:
                row[index] = sum(row)

            current_row = temp_matrix[row_index]
            score = min(current_row)
            index = current_row.index(score)
            test_time += score
            route.append(index)
        if shortest > test_time:
                    shortest = test_time
                    best_route = route
    return shortest, best_route[:-1]



a = [
    [0, 3610, 2959, 3536],
    [3861, 0, 1828, 243],
    [3129, 1706, 0, 1632],
    [3731, 242, 1698, 0]
    ]

nearest_neighbour(a[:])

编辑:我在最初没有的函数末尾添加了一个 if 语句

Answer 1

使用像 matrix[:] 这样的切片只会生成列表列表的浅拷贝。也就是说，您已经复制了外部列表，但新列表包含对与原始列表相同的内部列表的引用。如果您要重写它们的值并且不希望看到原始列表列表中的效果，您可能也需要复制内部列表。

使用copy.deepcopy 复制嵌套数据结构可能是个好主意。也就是说，您当前的代码制作了一大堆可能不必要的副本。如果您只是要对其调用 len 或对其进行迭代而不添加或删除元素，则无需复制某些内容。

我也很怀疑你的 for i in temp_matrix[:] 循环，因为你从不在循环体中使用 i。不过，我实际上并不了解您要计算的内容，因此我没有推荐的具体修复方法。