java - Java中TSP的分支定界实现

Question

我想知道是否有用于 TSP 的分支定界算法的有用 Java 实现，或者通常包含用于 TSP 的 BnB 的 OR 框架。

谢谢你的帮助！

马可

Answer 1

BnB 通常与完整的子问题求解器交互：

best_cost_soln_so_far = +inf
while (better_cost_soln = search_for_soln_cheaper_than(best_cost_soln_so_far))
{
    best_cost_soln_so_far = better_cost_soln
    backtrack_into_search
}

也就是说，只要它正在探索的任何部分解决方案的成本超过设置的界限，您的子问题搜索就会回溯best_cost_soln_so_far。如果子问题搜索确实找到了更好的解决方案，best_cost_soln_so_far则更新，并且搜索从它停止的地方继续，寻找更好的解决方案。这很容易实现。

也就是说，我非常怀疑您是否想使用完整搜索来处理大型 TSP，因为涉及到巨大的搜索空间；您可以使用模拟退火等近似技术做得更好。

Answer 2

我找到了这个pdf。它非常有用，并且有详细的示例和 Java 实现分支和绑定 TSP 这是文件链接

Answer 3

虽然我们都知道“Java 和 Javascript 很相似，就像 Car 和 Carpet 很相似”，但我还是建议您查看SimplexJS，它是一个用 Javascript 编写的简单线性和 MIP 求解器。由于它很小（少于 400 个 LOC），它可以很容易地翻译成 Java。该项目的作者还有一个用整数规划求解 TSP的好例子。

Answer 4

OptaPlanner（开源，Java）有一个分支定界实现。具体参见有关 BaB 的文档部分。算法的实现是从这个类开始的，但是这很难遵循。

它还有一个 TSP 示例：虽然默认情况下没有配置 BaB，但这样做很简单，通过如下调整tspSolverConfig.xml：

<solver>
  ...
  <exhaustiveSearch>
    <exhaustiveSearchType>BRANCH_AND_BOUND</exhaustiveSearchType>
  </exhaustiveSearch>
</solver>

还有额外的可选参数来控制节点排序、节点探索方式等。