我想知道是否有一种有用的Java实现可以用于TSP的分支定界算法，或者一般情况下包括TSP的BnB的OR框架。
感谢您的帮助！
马可
4个回答
2
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问题，因为涉及的搜索空间非常庞大；您可能会通过模拟退火等近似技术取得更好的效果。
- Rafe
0
OptaPlanner（开源，Java）具有分支和界实现。请参阅有关BaB的文档部分。算法的实现始于此类, 但这很难理解。
它还有一个TSP示例：虽然默认情况下未配置为BaB，但通过像这样调整tspSolverConfig.xml即可轻松完成：
<solver>
...
<exhaustiveSearch>
<exhaustiveSearchType>BRANCH_AND_BOUND</exhaustiveSearchType>
</exhaustiveSearch>
</solver>
有额外的可选参数来控制节点排序、节点探索方式等。
- Geoffrey De Smet
0
尽管我们都知道"Java和Javascript很像，就像汽车和地毯很像"，但我建议看一下SimplexJS，它是一个用Javascript编写的简单线性和MIP求解器。因为它很小（不到400行），所以可以轻松地转换成Java。该项目的作者还有一个很好的例子用整数规划解决TSP问题。
- vitaut
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接