未綁定在TSP的這段代碼中？

我想知道我該怎麼做BOUND，因爲我生成所有可能的解決方案矩陣tsp但不是綁定。問題是旅行推銷員。是否有可能做到這一點？未綁定在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); 
      } 
     } 
    }   
}

來源

2015-12-02 Germán Méndez

我添加這作爲一個答案道歉，我想簡單地將其添加爲註釋向您推薦另一個SE的問題，但我不具備添加註釋足夠的聲譽。

除了任何人都可以爲您提供計算邊界的實現，但理論上，請參考之前在SE上提出的類似問題。 TSP - Branch and bound

兩個給定的問題的答案以上提供鏈接到在分支定界（BAB）的上下文中TSP的透徹的解釋，包括如何計算BAB分支下邊界。回想一下，在BAB過程中，您的上限只是當前最好的現行解決方案（當前最佳路徑），如以前在BAB樹中或通過啓發式方法發現的那樣。

來源

2015-12-05 21:05:25 dfri

未綁定在TSP的這段代碼中？

回答

相關問題