分支定界执行情况的TSP在Java中 [英] Branch And Bound Implementation for TSP in Java

问题描述

我不知道是否有一个有用的Java实现一个分支定界算法的TSP或一般的A或框架，其中包括一个泡泡堂为TSP的。

I wonder if there is a useful Java implementation of a Branch And Bound algorithm for the TSP or in general a OR framework which includes a BnB for TSP.

感谢您的帮助！

马可

推荐答案

泡泡堂通常与交互的的完全的子问题求解：

BnB typically interacts with a complete sub-problem solver:

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 更新，并继续搜索，从那里离开，寻找一个仍更好的解决方案。这是pretty的容易实现。

That is, your sub-problem search will backtrack whenever the cost of any partial solution it is exploring exceeds the bound set by best_cost_soln_so_far. If the sub-problem search does find a better solution, best_cost_soln_so_far is updated, and the search continues from where it left off, looking for a still better solution. It's pretty easy to implement.

这是说，我很怀疑要解决使用，因为涉及到巨大的搜索空间的完整的搜索大量的TSP;你可能会做近似的技术更好，比如模拟退火。

That said, I doubt very much that you want to tackle large TSPs using complete search because of the huge search spaces involved; you may do better with approximate techniques such as simulated annealing.

这篇关于分支定界执行情况的TSP在Java中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！