algorithm - 旅行商 (TSP) : what is the Relation with number of vertices and length of the found route?

Question

我知道有很多算法(精确的或近似的)可以解决旅行商问题。

我想知道这些算法找到的顶点数(即访问的地方)与路径长度之间的关系。

直觉上，顶点的数量越少，路线越短。但是，谁能告诉我顶点数与至少一种现有旅行商算法找到的路径长度之间的数学关系？

提前致谢。

Answer 1

一般给出n节点，让成本集定义为 C = { c(i, j) = cost to traverse edge from node n(i) to n(j) : 0 ≤ i, j < n and i, j are integers} .

闭合电路路径总距离的天真边界将以 n*min(C) 为界及以上 n*max(C)其中 min(C)是遍历两个节点之间边的最小成本，max(C)是遍历两个节点之间边的最大成本。

如果寻找不在电路中的最短路径，则这变为 (n-1)*min(C)和 (n-1)*max(C)分别。

除此之外，还有多种方法可以获取 better upper bounds和 better lower bounds .