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

我想知道对于TSP，是否存在有用的Java实现的Branch And Bound算法，或者一般来说，是一个OR框架，其中包括针对TSP的BnB。

谢谢你的帮助!

马可

最佳答案

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，因为涉及的搜索空间很大；您可以采用近似技术(例如模拟退火)来做得更好。