algorithm - 我一直在阅读算法设计手册，但这个陈述让我感到困惑，我不确定它说的是真的

Question

下面的语句让我感到困惑:

The nearest-neighbor rule is reasonably efficient, for it looks at each pair of points (pi,pj) at most twice: once when adding pi to the tour, the other when adding pj.

它来自以下文本 block (以蓝色突出显示):

假设这对点是第 2 个和第 3 个点，(2,3) 这对点如何被看两次？当它添加第二个时，它会将第二个设置为离第一个最近的未访问点，然后当它添加第三个时，它会将第三个视为最接近第二个的点。这是我唯一能看到他们在看那个点对的点。

谁能解释一下？

Answer 1

他们更从数学角度看待这一点 - 有一组点，每次将一个点添加到巡回中时，都会访问整个集合以寻找最佳候选点。当一个点被添加到游览中时，集合不会改变，这些点只是被标记为已访问。因此每对都被考虑两次。

如果有人真正实现了该算法，您可能会使用一组未访问的点并在每次迭代后更新这组数据。现在每一对只被访问一次，但代价是改变集合，这可能 - 根据实现 - 比只访问每对两次花费更多或更少的时间。