どのように私はJavaでこの式を実装することができますか？

Question

はOK、これはフォローアップの質問の詳細です：<のhref = "https://stackoverflow.com/questions/874982/how-to-compute-optimal-paths-for-traveling-salesman-bitonic-ツアー ">セールスマンバイトニックツアーを旅行するための最適なパスを計算するには？の

まず、巡回セールスマン問題のバイトニックツアーのために、私は、次の再発関係を持っています：

(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

これは愚かな質問のように見えるかもしれません（おそらくですが、私は深刻な睡眠を欠いています）が、私は、誰かが助けることができる期待しています。

Answer 1

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

あなたはそれが既に事前に計算表であると述べたので、私は（リットルの事前計算表のように）リットルに対して同様の最適化をしませんでした注意してください。それがなかった場合、私は同じ最適化を実行します：）

しかし、以前のコメントは、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;

}