algorithm - 与随机路由相比，普通 TSP 算法的效率如何？

Question

前几天我只是在看一些 TSP 算法，想知道与随机路线相比，一个普通的 TSP 算法(如 Christofides 的算法)在 1000 个点上的效率如何。

如果我知道答案，或者更好的是，知道计算答案的方法，这将大大简化我自己算法的测试。

有没有人可以帮我解决这个问题？

编辑:点的 x 和 y 坐标必须是整数，并且它们被放置在 1000*1000 区域中。

Answer 1

给你一个粗略的想象:1000点的往返(TSP)的解空间，即可能的路线数是999! (假设不对称行进距离)。比较一下，50!是一个有63位数字的数字。由于它是组合问题，因此解决方案空间会随着位置数量的增加而迅速爆炸。因此，如果您生成一条随机路线，则达到最佳解决方案的概率为 1/999!。因此，在 1000 个案例中，我猜 Christophides 产生比随机方法更好的解决方案的概率是 1。为了给你一个具体的问题答案，与 Christophides 相比，你的随机方法效率非常低。