时间戳

首页 > 解决方案 > 最近邻计算中的条件检查错误？

python - 最近邻计算中的条件检查错误？

问题描述

我正在尝试编写一个函数，从列出的第一个城市开始，使用最近邻算法计算通过城市列表的近似旅行推销员路线。但是，每次我运行它时，我都会得到IndexError: list index out of range.

在调试错误时，我发现index从一个循环迭代到下一个循环迭代的值保持不变，而不是改变。当需要追加时，代码会检查if not in条件；因为它是False，它添加并移动1到i循环的下一次迭代。一旦它达到比数组中存在的数字更高的数字，它就会给我错误。

所以我的问题是，为什么执行不进入第一个if not in块？似乎代码忽略了它。

对于我的实际问题，我正在阅读一个包含 317 个城市的文件，每个城市都有一个索引和两个坐标。这是一个较短的测试城市示例列表：

Nodelist = [
    (1, 63, 71),
    (2, 94, 71),
    (3, 142, 370),
    (4, 173, 1276),
    (5, 205, 1213),
    (6, 213, 69),
    (7, 244, 69),
    (8, 276, 630),
    (9, 283, 732),
    (10, 362, 69),
]

这是函数的代码：

def Nearest(Nodelist,Distance,index):
    Time_Calculation = time.time()
    Newarray=[]
    Newarray.append(Nodelist[0])
    for i in range(0,len(Nodelist)):
        for j in range(1,len(Nodelist)):
            if (Nodelist[j] not in Newarray):
                DisEquation = math.sqrt(pow(Nodelist[j][1]-Newarray[i][1],2)+pow(Nodelist[j][2]-Newarray[i][2],2))
                if Distance==0:
                    Distance=DisEquation
                if Distance > DisEquation:
                    index=j
                    Distance=DisEquation
        if(Nodelist[index] not in Newarray):
            Newarray.append(Nodelist[index])
        Distance=0
    print (time.time() - Time_Calculation)
    return Newarray

调用它的代码：

NearestMethodArr=Nearest(Cities,b,index)
print(NearestMethodArr)
print(len(NearestMethodArr))

print声明应产生：

[(1, 63, 71), (2, 94, 71), (6, 213, 69), (7, 244, 69), (10, 362, 69), (3, 142, 370), (8, 276, 630), (9, 283, 732), (5, 205, 1213), (4, 173, 1276)]
10

标签： pythontraveling-salesman

解决方案

Newarray.append(Nodelist[0])#adding Nodelist[0] to NewArray    
for i in range(0,len(Nodelist)):
        for j in range(1,len(Nodelist)):
            if (Nodelist[j] not in Newarray):
                DisEquation = math.sqrt(pow(Nodelist[j][1]-Newarray[i [1],2)+pow(Nodelist[j][2]-Newarray[i][2],2)) #you access Newarray at i
                if Distance==0:
                    Distance=DisEquation
                if Distance > DisEquation:
                    index=j
                    Distance=DisEquation
        if(Nodelist[index] not in Newarray):
            Newarray.append(Nodelist[index])#you conditionally add new elements to newarray

如果您看到我添加到您的代码中的注释，则问题应该很清楚。您遍历 Nodelist 的所有元素并调用索引 i 您已经向 NewArray 添加了一个元素，因此第一次索引 0 存在。然后你点击不在 Newarray 中的 Nodelist[index]，如果它是真的，NewArray 变大 1，然后 NewArray[1] 工作，如果由于任何原因这不是真的，那么 NewArray 保持相同的大小，下一个 NewArray[i]将是索引超出范围错误。

编辑：感谢 CrazyChucky 在评论中让我直截了当。我在下面调整了

我对失败的评论是正确的，尽管我没有确定根本原因，即没有像作者所确定的那样设置索引。我没有在脑海中正确解析代码。更新版本中的代码可以工作，但如果您执行以下操作会更快、更容易阅读：

def new_nearest(Nodelist):
    start_time = time.time()
    shortest_path = [Nodelist[0]]
    Nodelist = Nodelist[1:]
    while len(Nodelist) > 0:
        shortest_dist_sqr = -1
        next_node = None
        for potential_dest in Nodelist:
            dist_sqr = (shortest_path[-1][1] - potential_dest[1])**2 + (shortest_path[-1][2] - potential_dest[2])**2 #you don't keep the distances so there is no need to sqrt as if a > b then a**2 > b**2
            if shortest_dist_sqr < 0 or dist_sqr < shortest_dist_sqr:
                next_node = potential_dest
                shortest_dist_sqr = dist_sqr
        shortest_path.append(next_node)
        Nodelist.remove(next_node)
    print(time.time() - start_time)
    return shortest_path

这将返回相同的结果，但执行速度更快。更改为从内部循环中删除节点的方法可以更清楚地了解正在发生的事情，这可能会使代码变慢一些（它会在 C 中，但 python 在各个地方都有很多开销，这可能会使这成为净收益， ) 并且因为不需要计算实际距离，因为你不存储它，你可以比较距离的平方而不做任何平方根。如果您确实想要距离，则可以在确定最近的节点后对其进行平方根。

编辑：我忍不住检查。从 Nodelist 中删除节点实际上代表了大部分时间节省，而缺少 sqrt 确实可以可靠地加快速度（我使用了 timeit 并改变了代码。）在较低级别的语言中，做微小的事情是超快的，所以很可能更快地离开数组并跳过已经使用的元素（这实际上可能不是真的，因为它会混淆分支预测性能分析真的很难，并且取决于您使用的处理器架构......） python 尽管即使是小东西也非常昂贵（添加两个变量：找出它们是什么类型，解码可变字节长度整数，添加，为结果创建新对象...... ) 所以即使从列表中删除一个值可能比跳过值并单独留下列表更昂贵，它也会导致更多的小操作在 Python 中非常慢。如果使用低级语言，您还可以识别节点的顺序是任意的（除了哪个是第一个），因此您可以只拥有一个包含所有节点的数组，而不是创建一个新的小数组来跟踪数组中使用的值的长度，并将数组中的最后一个值复制到为路径中的下一个节点选择的值之上。

再次编辑 :P : 我又忍不住好奇。覆盖部分节点列表而不是删除条目的方法让我想知道它在 python 中是否会更快，因为它确实创建了更多在 python 中很慢的工作，但减少了删除节点元素所涉及的工作量。事实证明，即使在 python 中，这种方法也很明显（虽然不是很显着，略低于 2%，但在微基准测试中是一致的），因此下面的代码甚至更快：

def newer_nearest(Nodelist):
    shortest_path = [Nodelist[0]]
    Nodelist = Nodelist[1:]
    while len(Nodelist) > 0:
        shortest_dist_sqr = -1
        next_node = None
        for index, potential_dest in enumerate(Nodelist):
            dist_sqr = (shortest_path[-1][1] - potential_dest[1])**2 + (shortest_path[-1][2] - potential_dest[2])**2 #you don't keep the distances so there is no need to sqrt as if a > b then a**2 > b**2
            if shortest_dist_sqr < 0 or dist_sqr < shortest_dist_sqr:
                next_node = index
                shortest_dist_sqr = dist_sqr
        shortest_path.append(Nodelist[next_node])
        Nodelist[next_node] = Nodelist[-1]
        Nodelist = Nodelist[:-1]
    return shortest_path

推荐阅读