optimization - 在分支定界算法的早期确定无希望的分支

Question

我必须设计一个分支定界算法，每次都解决笛卡尔平面上图形的最优路径。我已经得到提示，在运行时早期识别无望的分支将复合成一个运行“快一百倍”的程序。我的想法是假设连接到开始/结束节点的最短边将是巡回赛中的第一条或最后一条边，但薄菱形图证明并非如此。有没有人对如何消除这些无望的分支或谈论这个的参考有想法？

基本上，有没有比仅按字典顺序更好地分支到解决方案子集的更好方法，例如。第一个分支包含和排除边缘 ab，第二个分支包含和排除分支 ac

Answer 1

最近邻是一种简单的算法。分支定界只是一个优化循环，此外您还需要一个子问题求解器。我认为最近邻也是一种分支定界算法。相反，我会研究单纯形算法。这是一种线性规划算法。也是解决tsp的切割平面算法。

Answer 2

所以在你的分支定界算法的某个地方，你查看可能去的地方，然后以某种方式跟踪它们以便以后做。

为了提高效率，您可以做几件事：

1. 写一个更好的绑定计算器。换句话说，想出一个更准确地确定界限的算法。这将减少花在糟糕路径上的时间。
2. 与其使用堆栈来跟踪要做的事情，不如使用队列。不要使用队列，而是使用按边界排序的优先级队列（堆），例如，看起来最好的东西放在堆的顶部，看起来不好的东西放在底部。