与蛮力或任何其他算法相比,单纯形法解决 ts 问题的速度有多快?
最佳答案
您不能用“纯”LP 问题(具有连续变量)对 TS 问题建模。您可以使用整数规划公式,这将在研究树的每个节点上使用单纯形法(分支定界法或分支切割法)。它适用于小问题,但速度很慢,因为问题很难:例如,每条边有一个二进制变量,您需要大量约束来模拟路径是一个循环这一事实。
蛮力是棘手的(问题是指数级的),除非你有一个非常的小问题,否则不要尝试它。使用 MIP 公式,即使是小问题。
对于大问题,你应该使用某种启发式方法(我认为模拟退火在这个问题上会给出很好的结果),或者如果你想要一个精确的解决方案,你的问题的“智能”建模(例如列生成)。
关于linear-programming - 单纯形法求解 tsp 的速度有多快?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13721057/