کمک کنید

سلام به همگی :

من 2 تا برنامه ضرب زنجیره ای ماتریس ها و فروشنده دوره گر را باید پیاده سازی کنم ، اما در قسمت هایی از برنامم به مشکل برخوردم :

در ضرب زنجیره ای ماتریس ها :

من چطور می تونم برنامه این قسمت را بنویسم :

کد:

---

M[i][j] = minimum (M[i][k] + M[k +1 ][j] + d [ i – 1] * d [k] * d [j]);

---

که k ----> i <= k <= j-1

در فروشنده دوره گرد :

کد:

---

  D[i] [A] = minimum ( W [i] [j] + D [vj] [A – {vj}]);

---

که vj عضوی از A هست .

لطفا راهنمایی کنید ، من هر طور خواستم این دو تیکه را پیاده سازی کنم نتونستم . باید چه کار کنم 3تا حلقه for تعریف کنم یا while یا .....

فكر كنم اگر كدتون رو بذارين بهتر باشه

سلام :

استاد طراحی الگوریتم از ما خواسته که برنامه فروشنده دور گرد و ضرب زنجیره ای ماتریس ها را با هر زبانی بنویسیم و اجرا کنیم .

**************************
ضرب زنجیره ای ماتریس ها

هدف بسط الگوریتمی است که ترتیب بهینه را برای n ماتریس معین کند.

ترتیب بهینه فقط به ابعاد ماتریس ها بستگی دارد.

علاوه بر n ، این ابعاد تنها ورودی های الگوریتم هستند.

این الگوریتم حداقل به صورت نمایی است.

کد:

---

int minimult ( int n,

 const int d [],

 index P [][] )

 {

 index  i , j , k , diagonal;

 int M [1..n] [1..n];

 for ( i = 1 ; i ≤  n ; i ++)

 M [i] [i] = 0:

 for (diagonal = 1; diagonal ≤ n -1 ; diagonal ++)

 for ( i = 1 ; i ≤ n – diagonal ; i ++) {

 j = i + diagonal ;

 M[i][j] = minimum (M[i][k] + M[k +1 ][j] +

 d [ i – 1] * d [k] * d [j]);

 P [i][j] = a value of k that gave the minimum;

 }

 return M[1][n];

 }

---

***************************
فروشنده دورگرد
عمل اصلی: زمان در هر دو حلقه ی اول و آخر ، در مقایسه با زمان در حلقه میانی چشمگیر نیست، زیرا حلقه میانی حاوی سطوح گوناگون تودر تویی است . دستورات اجرا شده برای هر مقدار v j را می توان عمل اصلی در نظر گرفت.

اندازه ورودی : n ، تعداد رئوس موجود در گراف.

کد:

---

void tarvel ( int , n

 const number W[ ][ ] ,

 index P[ ] [ ] ,

 number & minlength)

 {

 index i , j , k ;

 number D[1..n][subset of V - { v1 } ] ;

 for ( i = 2 ; i ≤ n ; i ++)

 D[i] [Ø] = W [i] [1] ;

 for (k = 1 ; k ≤ n - 2 ; k ++)

 for (all subsets A Ç V – { v1 } containing k vertices)

 for (i such that i != 1 and vi is not inA){

  D[i] [A] = minimum ( W [i] [j] + D [j] [A – {vj}]);

 P [i] [A] = value of j that gave the minimum;

 D [1] [ V – { v1 } ] = minimum ( W [1] [j] +

 D [j] [ V – { v1 – v j } ] );

 P [1] [ V – { v1 } ] = value of j that gave the minimum;

 minlength = D [1] [ V – { v1 } ];

 }

---

البته این مطالبی که نوشتم در کتاب طراحی الگوریتم هم هست ولی مشکل اینجاست که من چطور پیاده سازی کنم . این تیکه هایی که نوشتم نمی دونم چطور بنویسم که اجرا بشه .

مشکلم در ضرب زنجیره ای ماتریس ها حل شد . لطفا فروشنده دوره گرد را کمکم کنید . ممنون میشم.

فقط بگید به جای نوشته های داخل حلقه for چه چیزی باید در داخل ( ) حلقه for بنویسم ؟

کد:

---

for (all subsets A Ç V – { v1 } containing k vertices)

 for (i such that i != 1 and vi is not inA){

  D[i] [A] = minimum ( W [i] [j] + D [j] [A – {vj}]);

---

هیچ کسی برنامه فروشنده دوره گردو نمی دونه !!!!!!

من فقط خواستم در حلقه for کمکم کنید ، از شما نخواستم که کل برنامه را برام بنویسید .

شايد اين دو منبع به دردتون بخوره

کد:

---

http://www.--------.com/forum/showthread.php?t=35583

---

کد:

---

http://www.barnamenevis.org/forum/showthread.php?p=218522

---

مرسی ولی :

آدرس اول که هیچ صفحه ای را باز نمی کنه !!!!!


آدرس دوم هم باید عضو بشم !!!!