3

好的，这更像是一个后续问题：如何计算旅行商双调旅行的最佳路径？

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

(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我最初的想法是我从1to迭代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

这似乎是一个愚蠢的问题（可能是，我严重缺乏睡眠），但我希望有人能帮忙。

4

3 回答 3

2

一个明显的优化是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)（我只是在这里猜测，因为我对这个问题了解不多，所以如果这听起来很古怪，请忽略此评论）。如果有任何特殊属性发布它们，我们可以提出进一步的优化。

于 2009-05-17T22:03:43.883 回答
1

我认为 Java 编译器会以它的方式优化你的循环。没关系。

于 2009-05-17T21:37:20.407 回答
0 
(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 ))

import system.math

unsigned long i;

unsigned long j;

if ((i==j-1)&& (j>2))

{

unsigned long k=1;

unsigned long result;

while (k<i)

{

  result = l(k; i) + dist(pk; pj )

  min = minus(min, result);

  k++;

}

return min;

}
于 2009-05-17T22:21:47.630 回答