How can I implement this equation in Java?

Question

OK, this is more of a follow-up question: How to compute optimal paths for traveling salesman bitonic tour?

First of all, for the bitonic tour of the traveling salesman problem I have the following recurrence relation:

(a) When i = 1 and j = 2, l(i; j) = dist(pi; pj )
(b) When i < j - 1; l(i; j) = l(i; j - 1) + dist(pj-1; pj)
(c) When i = j - 1 and j > 2, min 1<=k<i (l(k; i) + dist(pk; pj ))

l is a table of previous results. My question is with part C: Assuming l(k,i) and dist(pk,pj) are defined, how would I implement part C in Java? My initial thought was that I iterate over k from 1 to i and store the minimum result of (l(k,i) + dist(pk,pj)), but I don't think that is right.

for example:

for (int k = 1; k < i; ++k) {
  tmp = l(k,i) + dist(pk,pj);
  if (tmp < min) {
    min = tmp;
  }
}

// min is the result

This may seem like a stupid question (and probably is, I am severely lacking sleep), but I am hoping someone can help out.

Answer 1

One obvious optimization is to pre compute your dist(pk,pj) values before the loop

for example

dist_pk_pj = dist(pk,pj);

/* then do as you did before */
for (int k = 1; k < i; ++k) {
  tmp = l(k,i) + dist_pk_pj;
  if (tmp < min) {
    min = tmp;
  }
}

Note I didn't do a similar optimization for l (as in precompute a table of l) because you stated that it was already a precomputed table. If it wasn't then I would perform the same optimization :)

But as the previous comment stated the Java compiler could very well do that optimization for you. I'm no expert on what optimizations the Java Compiler performs though so take that last comment with a grain of salt :)

Finally are there any special properties that the l(k,i) table has? For example some symmetry l(i,k) = l(k,i) (I am just guessing here because I don't know much about the problem so Ignore this comment if it sounds wacky). If there are any special properties post them and we could come up with further optimizations.

Answer 2

I think Java compiler will optimize your loop in its way. And it is ok.