javascript - 异步旅行推销员子旅行的本地搜索启发式

Question

假设我想最小化一系列城市之间的旅行距离:

开始游览:S-1-2-3-4-5-E

最佳路线:S-5-1-2-3-4-E

游览必须从 S 开始，必须在 E 结束，但可以按任意顺序访问中间的城市。在我的用例中，S 和 E 之间的城市数将在 1 到 35 之间。

我目前使用的启发式是重复的两次选择(以伪 javascript 显示):

minStopSequence = ['S', 1, 2, 3, 4, 5, 'E'];
changed = true;
while (changed === true) {
  changed = false;
  for (i = 1; i < minStopSequence.length - 2; i++) {
    for (j = i + 1; j < minStopSequence.length - 1; j++) {
      newStopSequence = reverseTheMiddleSection(minStopSequence, i, j);
      newSegmentDur = getDuration(newStopSequence);
      if (newSegmentDur < minSegmentDur) {
        minSegmentDur = newSegmentDur;
        minStopSequence = newStopSequence;
        changed = true;
      }
    }
  }
}

这通常无法找到最佳解决方案(例如，它不会在上面的示例中找到最佳游览)。我尝试通过移位来增加它(对于每个索引，对于每个长度，将该段移动到末尾)，但这样做会导致 2 个问题:

1. 我重复了一些旅行的可能性(低效)
2. 我仍然没有达到最优，即使是 5 个城市的小行程也是如此

我已经看到 lin-kernighan-helsgaun 算法实现了大小 < 50 的最优性，并且“精确”变体适用于异步图(http://www.researchgate.net/profile/Daniel_Karapetyan/publication/227414913_Lin-Kernighan_heuristic_adaptations_for_the_generalized_traveling_salesman_problem/links/02e7e527676733456d000000.pdf 第 11 页)，但我不确定如何使其适应我的用例。

如果可以使用这种启发式算法，你能帮我弄清楚如何实现它吗？如果不是，什么是最合适的启发式方法，它可以为最小的问题(例如 n < 15)返回最佳结果，而为较大的问题返回接近最佳的结果？

Answer 1

可以最优解决15个城市问题的最简单算法是指数时间动态规划:https://class.coursera.org/algo2-002/lecture/181 .以此为起点，您可以通过将其应用于 15 个城市的子旅游来进行大社区本地搜索。