我必须设计一种分支定界算法，该算法每次都可以解决笛卡尔平面上图的最优绕行问题。我得到的提示是，在运行时更早地识别无望的分支将使程序运行速度提高“一百倍”。我有一个假设，即连接到起点/终点的最短边将是巡视中的第一条或最后一条边，但是薄的菱形图证明了相反的情况。有没有人有关于如何消除这些绝望的分支的想法或关于此的参考？
基本上，有一种更好的方法可以分支到解决方案的子集，而不仅仅是字典编排。第一分支包括和不包括边a-b，第二分支包括和不包括边a-c
最佳答案
因此，在分支定界算法中的某个位置，您要查看可能要去的地方，然后以某种方式跟踪它们以后要做的事情。
为了提高效率，您可以做一些事情：
编写一个更好的绑定计算器。换句话说，提出一种算法，可以更准确地确定边界。这将减少在原来很差的路径上花费的时间。
与其使用堆栈来跟踪要做的事情，不如使用队列。而不是使用队列，而是使用按边界排序的优先级队列（堆），例如看起来最好的东西放在堆的顶部，看起来不好的东西放在堆的底部。
关于optimization - 在分支定界算法中尽早确定无望的分支，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13675655/