是否有更有效、更可靠的方法来为距离矩阵创建最小接近度算法？

Question

我正在尝试制作一种算法，该算法使用附近的最小距离在距离矩阵中从一个点传播到另一个点。代码有两个条件：最小距离必须不小于0且每个点必须访问一次并且return到起始位置。

这是我的完整代码：

def totalDistance(aList):
    path = []
    for j in range(0,len(aList)):                  
        k=j
        order = []
        for l in range(0,len(aList)):
                order.append(k)
                initval= min(x for x in aList[k] if x > 0 )
                k = aList[k].index(initval)
                for s in range(0,len(aList)):
                    for t in range(0,len(aList[s])):
                        aList[s][k] = 0
        path.append(order)
    return path

该代码旨在 return 评估点附近的点的索引。

aList = [[0,3,4,6],[3,0,7,3],[4,7,0,9],[6,3,9,0]]表示距离矩阵。

当运行代码时，我得到以下错误：

initval= min(x for x in aList[k] if x > 0 )

ValueError: min() arg 是一个空序列

我假设当我使用以下函数将距离矩阵中的列设为零时：

            for s in range(0,len(aList)):
                for t in range(0,len(aList[s])):
                    aList[s][k] = 0

min() 函数无法找到符合给定条件的值。有没有更好的方法来格式化我的代码以防止这种情况发生，或者有更好的方法来解决这个问题？

Answer 1

您说的一项技术和其余部分的指示有效...

用于防止重访/回溯。一种常见的设计模式是保留一个单独的数据结构来“标记”你去过的地方。因为你的点数是数字索引的，所以你可以使用布尔值列表，但我认为只保留一组你去过的地方要容易得多。像这样...

visited = set()  # places already seen

# If I decide to visit point/index "3"...
visited.add(3)

像你现在这样修改输入数据并不是一个很好的做法，尤其是当你循环输入数据时，你...会让人头疼。

那么...您当前的错误发生是因为当您筛选 x>0 的行时，您最终会得到一个空列表，因为您正在更改值然后 min() 阻塞。所以上面的部分可以解决这个问题，你不需要归零，只需标记它们。

然后，显而易见的问题...如何使用标记？您可以将其用作搜索的一部分。它可以很好地与 enumerate 命令一起使用，该命令可以 return 索引值和枚举值。

试试这样的方法，它会生成一个包含距离和索引位置的“合格”元组列表。

    pts_to_consider = [(dist, idx) for idx, dist in enumerate(aList[k])
                        if dist > 0
                        and idx not in visited]

还有其他方法可以使用 numpy 和其他东西来执行此操作，但这是一种合理的方法，并且接近于您现在在代码中拥有的方法。如果卡住了，请评论回来。我不想放弃整个农场，因为这可能是 H/W。也许您可以使用此处的一些提示。

是否有更有效、更可靠的方法来为距离矩阵创建最小接近度算法？

Is there a more efficient an robust way to create a minimum proximity algorithm for a distance matrix?

python

list

propagation

python-3.x