الگوریتم فروشنده دوره گرد به روش پویا tsp ؟!

[Ramin-hst]

با سلام و روز بخیر

صرفا جهت اطلاع :
مسئله فروشنده دوره گرد TSP یکی از مسائل مهم در زمره تئوری پیچیدگی محاسباتی الگوریتم ها می باشد که در گروه NP-Hard قرار می گیرد
تعدادی شهر داریم و هزینه (مسافت) مسافرت به هر یک از آنها مشخص است به دنبال کم هزینه ترین مسیر هستیم بطوریکه از همه شهرها فقط یکبار عیور کنیم و مجددا به محل شروع بازگردیم
مرتبه زمانی این الگوریتم به طور مستقیم و محاسبه تک تک راه ها !n است ولی در روش پویا از مرتبهn^2*2^n و حافطه مورد نیاز از مرتبه n*2^n خواهد بود.

سوال؟
الگوریتم فروشنده دوره گرد به روش پویا چه طور حل میشه؟!!
یعنی به صورت تشریحی با استفاده از فرمول زیر

D[vi][a]=min(w[i][j]+D[vi][a-{vj}]) if a!=0 and vj E A

تو حل با این روش مقادیر A,vi چهطوری تعیین میشن؟؟
فردا امتحان طراحی الگوریتم دارم


موضوعات مشابه:

• ایجاد منوهای پویا

[NIIT]

سلام دوست محترم
نگاه کنین شما فرض کنین این مجموعه رو دارین:





این هم راه حلشه:

فقط عذر میخوام دیگه عجله ای از تصاویر عکس گرفتم زیاد کیفیت ندارن
انشالله که امتحانتون رو خوب میدین
بازم میبخشین
درپناه خدا

[Ramin-hst]

با تشکر زیاد :wubsmiley:

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

• (....)D[V1][V2,V3,V4,V5,V6]= MIN

مشکل من اینجاس اگه تعداد گره ها بیشتر از 4 باشه اول فرمول به این شکل هست یا نه؟

[Unicorn]

تو این راه حلی که بالا نوشتین 6 = [{$}][D[v<sub>4

حالا سوال من اینه که اگر مسیر فلش یال بر عکس بود بازم همون 6 میشد یا 0؟</sub>

[Ramin-hst]

تو این راه حلی که بالا نوشتین 6 = [{$}][D[v4

حالا سوال من اینه که اگر مسیر فلش یال بر عکس بود بازم همون 6 میشد یا 0؟

D[v4][$]=w[4][1]=6 if a=$ ; end

با توجه به رابطه بالا و ماتریس مجاورتی گراف اگه یالی از 1 به 4 نباشه جواب 0 میشه.

[Unicorn]

امتحان امروز چطور بود؟