最近邻居启发式

Question

我正在教TSP使用教科书。 我对最近邻启发式和最小增加启发式之间的区别感到困惑。

正如我的教科书中所描述的那样，我将以下定义为每个。

最近的邻居启发式：在下一个点阅读，并将它添加到最近的点之后的当前游览中。 如果有多个点与其最接近，请在您发现的第一个这样的点之后插入它。

最小增幅启发：读出下一个点，而且它在 导致游览长度尽可能少的增加后点添加到当前游览。如果有多个点，请在发现第一个这样的点后插入它。

对于第二个启发式，最近的点不会给你总距离的最小增加吗？那么这两个启发式究竟有什么区别呢？

我将不胜感激你们的任何意见。

Answer 1

首先，对最近邻居的描述看起来并不标准。通常，所有的点都被认为是“读入”的，并且NN添加了最接近增长巡视结束的点。您正在使用的书似乎是在所有点都已知之前，通过将每个新点插入到正在增长的巡视中来构建巡视。

说部分游览是ABCDE和F是新的点。此版本的最近邻元素在P之后插入F，该点最小化d(P,F)。请注意，如果这是例如B然后游览费用增加了总和d(B,F) + d(F,C)。最近的邻居完全忽略了第二项。最小的增加启发式将其考虑在内。它力求最大限度地降低插入的总成本，而不仅仅是第一个任期。

这两种算法都以AB开头，其中A和B是前两个读数。他们可能会与C（第三点阅读）分歧。根据d(A,C)或d(B,C)是否较小，最近的邻居会将巡视延长至ABC或ACB。另一方面，所描述的最小增加启发式将看ACB或ABC，这取决于哪一个是最短的巡回（这相当于说明哪一个表示从巡回AB中增加最少）。

正如我前面所说，这是对最近邻的非标准描述，尽管它肯定是一个合理的启发式。此外，应该指出，最小增加启发式并不总是比这里描述的最近邻居更好。这是因为最小增加的启发式可能会因为在最终巡回中基本不相关的原因而放弃优点。如果AC是一个很好的优势，为什么绕过它只是因为CB是不利的优势，当CB是不太可能在最后一次巡回赛的优势？