我目前正在研究旅行商问题,并且想知道是否有人能够简单地解释持有的karp下限.我一直在看很多论文,我很难理解它.如果有人可以简单地解释它会很棒.
我也知道有一种计算不包括起始顶点的顶点的最小生成树然后从起始顶点添加两个最小边的方法.
我有一个图表,顶点有大量的边n(n-1)/2.如果我有16个verticies 16^2 + 120 是376和120 * log2(16)是480.所以这里V^2更快？我的计算是否正确,如果它们是什么时候顶点的大小会达到E log v更快的点？