java - 我如何在 Java 中实现这个等式？

Question

好的，这更像是一个后续问题:How to compute optimal paths for traveling salesman bitonic tour?

首先，对于旅行商问题的双调旅行，我有以下递归关系:

(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 是以前结果的表格。我的问题是关于 C 部分:假设定义了 l(k,i) 和 dist(pk,pj)，我将如何在 Java 中实现 C 部分？我最初的想法是，我将 k 从 1 迭代到 i 并存储 (l(k,i) + dist(pk,pj))，但我认为这是不对的。

例如:

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

// min is the result

这似乎是一个愚蠢的问题(而且可能是，我严重缺乏 sleep )，但我希望有人能帮忙。

Answer 1

一个明显的优化是在循环之前预先计算您的 dist(pk,pj) 值

例如

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;
  }
}

请注意，我没有对 l 进行类似的优化(如预先计算 l 的表)，因为您声明它已经是一个预先计算的表。如果不是，那么我会执行相同的优化 :)

但正如前面的评论所述，Java 编译器可以很好地为您进行优化。我不是 Java 编译器执行哪些优化方面的专家，所以对最后的评论持保留态度 :)

最后，l(k,i) 表有什么特殊的属性吗？例如一些对称性 l(i,k) = l(k,i)(我只是在这里猜测，因为我对这个问题了解不多，所以如果它听起来很古怪，请忽略此评论)。如果有任何特殊属性发布它们，我们可以提出进一步的优化。