以下陈述使我感到困惑：
最近邻规则相当有效，因为它最多查看每对点 (pi,pj) 两次：一次是在将 pi 添加到游览时，另一次在添加 pj 时。
它来自以下文本块（以蓝色突出显示）：
假设这对点是第 2 和第 3 点，(2,3) 那对点怎么看两次？当它添加第 2 个时，它将第 2 个设置为最接近第 1 个的未访问点，然后当它添加第 3 个时，它认为第 3 个最接近第 2 个。这是我能看到他们看着那对点的唯一一点。
有人可以解释吗？
问问题
182 次
2 回答
2
他们更从数学角度看待这一点 - 有一组点，每次将一个点添加到巡回赛中时，都会访问整个集以寻找最佳候选人。当一个点被添加到游览中时，该集合不会改变，这些点只是被标记为已访问。因此，每一对都被考虑两次。
如果有人真正实现了该算法，您可能会使用一组未访问的点并在每次迭代后更新该组。现在每一对只被访问一次，但代价是改变集合，这可能 - 取决于实现 - 比仅仅访问每对两次所花费的时间更多或更少。
于 2012-12-19T22:06:24.090 回答
1
解释说“最多两次”。
如果他们期望每对都被检查两次，那么“最多”这个词就不会出现。“最多两次”的反例是被检查三次或更多次的配对，而不是只检查一次的配对。
于 2012-12-19T23:45:55.620 回答