Wie kann ich diese Gleichung in Java implementieren?

Question

OK, ist dies eher eine Folgefrage: Wie optimale Wege berechnen für Verkäufer bitonische Tour reisen?

Vor allem für die bitonische Tour des Reiseproblems Ich habe folgende Rekursion:

(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 ist eine Tabelle mit früheren Ergebnissen. Meine Frage ist, mit einem Teil C: Unter der Annahme, l(k,i) und dist(pk,pj) definiert werden, wie würde ich Teil C in Java implementieren? Mein erster Gedanke war, dass ich über k von 1 iterieren das Mindestergebnis von i (l(k,i) + dist(pk,pj)) und zu speichern, aber ich glaube nicht, dass richtig ist.

Beispiel:

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

// min is the result

Das mag wie eine dumme Frage scheinen (und wahrscheinlich ist, dass ich stark bin Schlaf fehlt), aber ich hoffe, jemand helfen kann.

Answer 1

Eine offensichtliche Optimierung ist vorab Ihre dist(pk,pj) Werte vor der Schleife berechnen

zum Beispiel

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

Hinweis: Ich habe nicht eine ähnliche Optimierung für l tun (wie in Precompute einer Tabelle l), weil man festgestellt, dass es bereits eine vorberechnete Tabelle. Wenn nicht, dann würde ich die gleiche Optimierung durchführen:)

Aber wie der vorherige Kommentar des Java-Compiler angegeben könnte sehr gut für Sie, dass die Optimierung tun. Ich bin kein Experte, was Optimierungen die Java Compiler ausführt obwohl nehmen, so dass letzte Bemerkung mit einem Körnchen Salz:)

Schließlich gibt es spezielle Eigenschaften, die die l(k,i) Tabelle hat? Zum Beispiel einige Symmetrie l(i,k) = l(k,i) (ich bin nur raten hier, weil ich nicht viel wissen über das Problem so diesen Kommentar ignorieren, wenn es verrückt klingt). Wenn es irgendwelche besonderen Eigenschaften sind nach ihnen und wir konnten mit weiteren Optimierungen kommen.

Answer 2

Ich denke, Java-Compiler Ihre Schleife in seiner Art und Weise zu optimieren. Und es ist in Ordnung.

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;

}