genetic-algorithm - 旅行推销员 - 近似在线软件？

Question

你们中的任何人都知道一种解决方案，即使是针对旅行推销员问题的平庸解决方案。我有 3 个人打算访问 31 个目的地……我不知道该怎么办？

谢谢大家 -

格言

Answer 1

有几个选项，包括：最近邻、Christofides和Lin–Kernighan。

如果这些都失败了，您可以随时使用专家的代码（学术研究人员免费）。

Answer 2

我想你可以通过选择一个任意点开始（如果没有指定起点）来尝试一种贪婪的方法，然后在每一步中你都会到达离当前点最近的点。假设可以在恒定时间内计算点之间的距离，那么您可以在 O(n^2) 时间内找到一条路径。

为了澄清，下面的伪代码应该会有所帮助（我有一段时间没有写这种东西了，所以我希望这足够清楚）

Name: GreedyPath(C, p)
Input: C - a non-empty collection of points to visit
       p - a starting point in C
Output: S - a sequence of points covering C
Algorithm:
  Remove p from C
  If C is empty
    Return the sequence containing only p
  Else
    Let p1 be the closest point to p in C
    Let S = GreedyPath(C, p1)
    Append p to the start of S
    Return S

显然，耗时的部分是p每次都找到最近的点，但是对于n点，这应该只需要n(n-1)/2计算距离（除非我弄错了）。