如何在Java中實現這個公式？

OK，這更是一個後續問題：How to compute optimal paths for traveling salesman bitonic tour?如何在Java中實現這個公式？

首先，針對旅行商問題的雙調之旅，我有以下遞推關係：

(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)和，我將如何在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

這似乎是一個愚蠢的問題（也可能是，我嚴重缺乏睡眠），但我希望有人可以幫忙。

來源

2009-05-17 Mr. Shickadance

一個明顯的優化是預先循環

例如之前計算你值

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

注意我沒做●一個類似的優化（如升預先計算表）因爲你說它已經是預先計算好的表格。如果不是那麼我會執行相同的優化:)

但正如先前的評論指出，Java編譯器可以很好地爲你做這種優化。我不是Java編譯器執行什麼優化的專家，所以請在最後一條評論中加上一點鹽:)

最後是否存在l(k,i)表有哪些特殊屬性？例如一些對稱l(i,k) = l(k,i)（我只是在這裏猜測，因爲我不太瞭解這個問題，所以忽略這個評論，如果它聽起來很古怪）。如果有任何特殊屬性發布，我們可以進一步優化。

來源

2009-05-17 22:03:43 hhafez

1用於拉動外循環的DIST計算。 Java編譯器將無法爲自己做到這一點，除非它能證明dist函數不能改變。由於dist大概在數組中查找距離（這是可變的），我不認爲目前的編譯器能夠證明這一點。 – mikera 2012-03-05 01:29:14

我認爲Java編譯器會優化你的循環。沒關係。

來源

2009-05-17 21:37:20 Imaskar

(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-17 22:21:47

如何在Java中實現這個公式？

回答

相關問題