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

标签 algorithm math optimization graph-theory combinatorics

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

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

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

提前致谢。

最佳答案

一般给出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 boundsbetter lower bounds .

关于algorithm - 旅行商 (TSP) : what is the Relation with number of vertices and length of the found route?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30175106/

相关文章:

algorithm - 这段代码的时间复杂度是多少loglogn?

algorithm - 多变量的复杂性

python - 使用特定经度和纬度计算距离时的值域误差

java - 一组子集中的数字总和

optimization - SVM和神经网络中的成本函数优化有何不同

algorithm - 如何在网格上画一个圆?

c++ - 从数组中提取子序列

sql - 为什么不是数学或其他语言的sql中的null * 0 = null

c++ - 如何使用gsl在C++上实现左矩阵除法

javascript - html DOM 节点限制