Java 에서이 방정식을 어떻게 구현할 수 있습니까?

Question

자, 이것은 후속 질문입니다. 여행사 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에서 Part 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

이것은 어리석은 질문처럼 보일 수 있습니다 (아마도 나는 수면이 심각하지 않을 것입니다). 그러나 나는 누군가가 도울 수 있기를 바라고 있습니다.

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) (문제에 대해 많이 알지 못하기 때문에 여기서 추측하고 있습니다. 그래서이 의견이 엉뚱한 것처럼 들리면 무시하십시오). 특수 속성이 게시되면 추가 최적화를 제시 할 수 있습니다.

Answer 2

Java 컴파일러가 루프를 최적화 할 것이라고 생각합니다. 그리고 괜찮습니다.

Answer 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 ))

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;

}