كيف يمكنني تنفيذ هذه المعادلة في جافا؟

Question

وموافق، وهذا هو أكثر من سؤال للمتابعة: <لأ href = "https://stackoverflow.com/questions/874982/how-to-compute-optimal-paths-for-traveling-salesman-bitonic- جولة "> كيفية حساب المسارات المثلى للسفر جولة بائع bitonic؟

وأولا وقبل كل شيء، لجولة 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)، كيف سيكون تنفيذ جزء 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;
  }
}

ملاحظة أنني لم أفعل التحسين مماثل للتر (كما هو الحال في precompute جدول ل) لأنك ذكرت أنه كان بالفعل طاولة precomputed. إذا لم يكن ثم أود أن تنفيذ نفس الأمثل:)

ولكن كما ذكر التعليق السابق ومترجم جافا يمكن أن تفعل جيدا أن الأمثل بالنسبة لك. أنا لست خبيرا في ما أمثل مترجم جافا يقوم على الرغم من ذلك تأخذ هذا التعليق الأخير مع حبة الملح:)

وأخيرا هل هناك أي خصائص خاصة أن الجدول l(k,i) قد؟ على سبيل المثال بعض l(i,k) = l(k,i) التماثل (أنا مجرد التخمين هنا لأنني لا أعرف الكثير عن هذه المشكلة حتى تجاهل هذا التعليق إذا كان يبدو أحمق). إذا كان هناك أي خصائص خاصة بنشرها، ونحن يمكن أن يأتي مع مزيد من التحسينات.

Answer 2

وأعتقد أن المترجم جافا تحسين حلقة الخاصة بك في طريقها. وعلى ما يرام.

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;

}