0

我想知道如何做 BOUND 因为我生成了所有可能的解决方案矩阵 tsp 但没有生成边界。问题是旅行推销员。是否有可能做到这一点？

public void bnb (int from, ArrayList followedRoute) {
    if (followedRoute.size() == distances.getMatrix().get(0).size()) {

        followedRoute.add(sourceCity);
        nodes++;

        // update the route's cost
        routeCost += distances.getCost(from, sourceCity);

        if (routeCost < optimumCost) {
            optimumCost = routeCost;
            optimumRoute = (ArrayList)followedRoute.clone();
            result += followedRoute.toString() + "// Cost: "+ routeCost + "\n";
            System.out.println(result);
        } 

        routeCost -= distances.getCost(from, sourceCity);

    }
    else {
        for (int to=0; to < distances.getMatrix().get(0).size(); to++){
            if (!followedRoute.contains(to)) {

                // update the route's cost
                routeCost += distances.getCost(from, to);


                if((routeCost < optimumCost) ) {
                    ArrayList increasedRoute = (ArrayList)followedRoute.clone();
                    increasedRoute.add(to);
                    nodes++;
                    bnb(to, increasedRoute);    
                } 


                routeCost -= distances.getCost(from, to);
            }
        }
    }        
}
4

1 回答 1

0

我很抱歉将其添加为答案，我想简单地将其添加为评论以将您推荐给另一个 SE 问题，但我没有足够的声誉来添加评论。

除了任何人之外，您可能无法为您提供计算边界的实现，但是对于理论，请参阅之前在 SE 上提出的类似问题。 TSP - 分支和绑定

上述问题的两个给出的答案都提供了在分支定界 (BAB) 上下文中对 TSP 进行彻底解释的链接，包括如何计算BAB 分支的下限。回想一下，您在 BAB 过程中的上限只是当前最佳现有解决方案（当前最佳路径），如之前在 BAB 树中或通过启发式方法找到的。

于 2015-12-05T21:05:25.290 回答