最近邻启发式

Question

我正在用课本自学TSP。我对最近邻启发式和最小增量启发式之间的区别感到困惑。

正如我在教科书中所描述的，我有以下对每一项的定义。

最近邻启发式：在下一个点读取，并将其添加到最近点之后的当前浏览中。如果有一个以上的点，它是最近的，插入它后的第一个这样的点，你发现。

最小增长启发式：在下一个点读取，并将其添加到当前的旅游点之后，从而使旅游长度增加的可能性最小。如果有多个点，将其插入到您发现的第一个这样的点之后。

对于第二种启发式，最接近的点不是给出了总距离最小的增长吗？那么，这两种启发式方法到底有什么区别呢？

如果你们能提供任何意见，我将不胜感激。

Answer 1

首先，最近邻的描述似乎是不标准的。通常，所有的点都被认为是“读入”，而NN添加的点是最接近增长结束的点。你正在使用的书似乎是在知道所有的点之前，通过将每一个新的点插入到正在增长的旅游中来构建旅游。

假设部分巡演是ABCDE，而F是新的点。最近邻的这个版本在点F之后插入P，这使d(P,F)最小化。注意，如果这是B，那么旅游成本就会增加d(B,F) + d(F,C)之和。最近邻完全忽略了第二个项。最小的增长启发式考虑到了它。它力求尽量减少插入的总费用，而不仅仅是第一个任期。

这两种算法都将从AB开始，其中A和B是读取的前两点。他们可能会与C产生分歧(第三点读)。最近的邻居将巡演扩展到ABC或ACB，这取决于d(A,C)还是d(B,C)更小。另一方面，所描述的最小增长启发式将查看ACB或ABC，这取决于哪个是最短的旅行(这相当于说哪一个代表了AB中增长最少的一个)。

正如我前面说过的，这是最近邻的一个非标准描述，尽管它肯定是一个合理的启发。此外，应该注意的是，最小增长启发式并不总是优于最近的邻居，如这里所描述的。这是因为最小的增加启发式可能会放弃好的边，因为根本上是不相关的原因，在最后的巡演。如果AC是一个很好的优势，为什么要绕开它，因为CB是一个坏的优势，而CB不太可能成为最终的优势？