title: How can I optimize my java implementation of Held-Karp algorithm to shorten the running time?
body: <p>I use Java implemented Held-Karp<a href="https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm" rel="nofollow">TSP algorithm</a> algo to solve a 25 cities TSP problem.
  The program passes with 4 cities. </p>
  
  <p>When it runs with 25 cities it won't stop for several hours. I use jVisualVM to see what's the hotspot, after some optimization now it shows
  98% of time is in real computing instead in Map.contains or Map.get.</p>
  
  <p>So I'd like to have your advice,  and here is the code:</p>
  
  <pre><code>    private void solve() throws Exception {
          long beginTime = System.currentTimeMillis();
          int counter = 0;
  
          List&lt;BitSetEndPointID&gt; previousCosts;
          List&lt;BitSetEndPointID&gt; currentCosts;
          //maximum number of elements is c(n,[n/2])
          //To calculate m-set's costs just need to keep (m-1)set's costs
          List&lt;BitSetEndPointID&gt; lastKeys = new ArrayList&lt;BitSetEndPointID&gt;();
          int m;
          if (totalNodes &lt; 10) {
              //for test data, generate them on the fly
              SetUtil3.generateMSet(totalNodes);
          }
          //m=1
          BitSet beginSet = new BitSet();
          beginSet.set(0);
          previousCosts = new ArrayList&lt;BitSetEndPointID&gt;(1);
          BitSetEndPointID beginner = new BitSetEndPointID(beginSet, 0);
          beginner.setCost(0f);
          previousCosts.add(beginner);
  
          //for m=2 to totalNodes
          for (m = 2; m &lt;= totalNodes; m++) {// sum(m=2..n 's C(n,m)*(m-1)(m-1)) ==&gt; O(n^2 * 2^n)
              //pick m elements from total nodes, the element id is the index of nodeCoordinates
              // the first node is always present
  
              BitSet[] msets;
              if (totalNodes &lt; 10) {
                  msets = SetUtil3.msets[m - 1];
              } else {
                  //for real data set, will read from serialized file
                  msets = SetUtil3.getMsets(totalNodes, m-1);
              }
              currentCosts = new ArrayList&lt;BitSetEndPointID&gt;(msets.length);
              //System.out.println(m + " sets' size: " + msets.size());
              for (BitSet mset : msets) { //C(n,m) mset
                  int[] candidates = allSetBits(mset, m);
                  //mset is a BitSet which makes sure begin point 0 comes first
                  //so end point candidate begins with 1. candidate[0] is always begin point 0
                  for (int i = 1; i &lt; candidates.length; i++) { // m-1 bits are set
                      //set the new last point as j, j must not be the same as begin point 0
                      int j = candidates[i];
                      //middleNodes = mset -{j}
                      BitSet middleNodes = (BitSet) mset.clone();
                      middleNodes.clear(j);
                      //loop through all possible points which are second to the last
                      //and get min(A[S-{j},k] + k-&gt;j), k!=j
                      float min = Float.MAX_VALUE;
                      int k;
                      for (int ki = 0; ki &lt; candidates.length; ki++) {// m-1 calculation
                          k = candidates[ki];
                          if (k == j) continue;
                          float middleCost = 0;
                          BitSetEndPointID key = new BitSetEndPointID(middleNodes, k);
                          int index = previousCosts.indexOf(key);
                          if (index != -1) {
                              //System.out.println("get value from  map in m " + m + " y key " + middleNodes);
                              middleCost = previousCosts.get(index).getCost();
                          } else if (k == 0 &amp;&amp; !middleNodes.equals(beginSet)) {
                              continue;
                          } else {
                              System.out.println("middleCost not found!");
                              continue;
  //                            System.exit(-1);
                          }
  
  
                          float lastCost = distances[k][j];
                          float cost = middleCost + lastCost;
                          if (cost &lt; min) {
                              min = cost;
                          }
  
                          counter++;
                          if (counter % 500000 == 0) {
                              try {
                                  Thread.currentThread().sleep(100);
                              } catch (InterruptedException iex) {
                                  System.out.println("Who dares interrupt my precious sleep?!");
                              }
                          }
                      }
                      //set the costs for chosen mset and last point j
                      BitSetEndPointID key = new BitSetEndPointID(mset, j);
                      key.setCost(min);
                      currentCosts.add(key);
  
  //                    System.out.println("===========================================&gt;mset " + mset + " and end at " +
  //                            j + " 's min cost: " + min);
  //                    if (m == totalNodes) {
  //                        lastKeys.add(key);
  //                    }
                  }
              }
              previousCosts = currentCosts;
              System.out.println("...");
          }
  
          calcLastStop(lastKeys, previousCosts);
          System.out.println(" cost " + (System.currentTimeMillis() - beginTime) / 60000 + " minutes.");
      }
  
  
      private void calcLastStop(List&lt;BitSetEndPointID&gt; lastKeys, List&lt;BitSetEndPointID&gt;  costs) {
          //last step, calculate the min(A[S={1..n},k] +k-&gt;1)
          float finalMinimum = Float.MAX_VALUE;
          for (BitSetEndPointID key : costs) {
              float middleCost = key.getCost();
              Integer endPoint = key.lastPointID;
              float lastCost = distances[endPoint][0];
              float cost = middleCost + lastCost;
              if (cost &lt; finalMinimum) {
                  finalMinimum = cost;
              }
          }
          System.out.println("final result: " + finalMinimum);
      }
  </code></pre>