نمایش نتایج: از شماره 1 تا 6 از مجموع 6
Like Tree2نفر پسندیدند
  • 2 ارسال توسط NIIT

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

  1. #1
    مدیر بازنشسته
    تاریخ عضویت
    2011 October
    محل سکونت
    قائم شهر
    ارسال ها
    189
    تشکر
    308
    تشکر شده 525 بار در 195 پست
    نوشته های وبلاگ
    5


    آيا اين پست براي شما سودمند بود؟ بله | خیر

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

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

    صرفا جهت اطلاع :
    مسئله فروشنده دوره گرد 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 چهطوری تعیین میشن؟؟
    فردا امتحان طراحی الگوریتم دارم



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

  2. #2
    مدیر بازنشسته
    تاریخ عضویت
    2011 June
    محل سکونت
    گرگان
    ارسال ها
    1,170
    تشکر
    62
    تشکر شده 1,587 بار در 809 پست
    نوشته های وبلاگ
    49


    آيا اين پست براي شما سودمند بود؟ بله | خیر
    سلام دوست محترم
    نگاه کنین شما فرض کنین این مجموعه رو دارین:





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

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

    ویرایش توسط NIIT : 8th June 2012 در ساعت 02:43 PM
    Hossein و Ramin-hst این را میپسندند
    آرامش محصول تفکر نیست! آرامش هنر نیندیشیدن به انبوه مسائلیست که ارزش فکر کردن ندارد...

  3. #3
    مدیر بازنشسته
    تاریخ عضویت
    2011 October
    محل سکونت
    قائم شهر
    ارسال ها
    189
    تشکر
    308
    تشکر شده 525 بار در 195 پست
    نوشته های وبلاگ
    5


    آيا اين پست براي شما سودمند بود؟ بله | خیر
    با تشکر زیاد :wubsmiley:

    فقط یه نکته اگه 6 تا گره داشته باشم و بخوایم از این روش استفاد یعنی باید اینجوری حل کرد
    • (....)D[V1][V2,V3,V4,V5,V6]= MIN
    مشکل من اینجاس اگه تعداد گره ها بیشتر از 4 باشه اول فرمول به این شکل هست یا نه؟


  4. #4
    عضو تازه وارد
    تاریخ عضویت
    2011 September
    ارسال ها
    6
    تشکر
    28
    تشکر شده 11 بار در 6 پست


    آيا اين پست براي شما سودمند بود؟ بله | خیر
    تو این راه حلی که بالا نوشتین 6 = [{$}][D[v4

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


  5. #5
    مدیر بازنشسته
    تاریخ عضویت
    2011 October
    محل سکونت
    قائم شهر
    ارسال ها
    189
    تشکر
    308
    تشکر شده 525 بار در 195 پست
    نوشته های وبلاگ
    5


    آيا اين پست براي شما سودمند بود؟ بله | خیر
    نقل قول نوشته اصلی توسط Unicorn نمایش پست ها
    تو این راه حلی که بالا نوشتین 6 = [{$}][D[v4

    حالا سوال من اینه که اگر مسیر فلش یال بر عکس بود بازم همون 6 میشد یا 0؟
    D[v4][$]=w[4][1]=6 if a=$ ; end
    با توجه به رابطه بالا و ماتریس مجاورتی گراف اگه یالی از 1 به 4 نباشه جواب 0 میشه.


  6. #6
    عضو تازه وارد
    تاریخ عضویت
    2011 September
    ارسال ها
    6
    تشکر
    28
    تشکر شده 11 بار در 6 پست


    آيا اين پست براي شما سودمند بود؟ بله | خیر
    امتحان امروز چطور بود؟


 

 

کاربران برچسب خورده در این موضوع

علاقه مندی ها (Bookmarks)

علاقه مندی ها (Bookmarks)

مجوز های ارسال و ویرایش

  • شما نمیتوانید موضوع جدیدی ارسال کنید
  • شما امکان ارسال پاسخ را ندارید
  • شما نمیتوانید فایل پیوست کنید.
  • شما نمیتوانید پست های خود را ویرایش کنید
  •  


Powered by vBulletin
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
Content Relevant URLs by vBSEO 3.6.0
Persian Language By Ustmb.ir
این انجمن کاملا مستقل بوده و هیچ ارتباطی با دانشگاه علوم و فنون مازندران و مسئولان آن ندارد..این انجمن و تمامی محتوای تولید شده در آن توسط دانشجویان فعلی و فارغ التحصیل ادوار گذشته این دانشگاه برای استفاده دانشجویان جدید این دانشگاه و جامعه دانشگاهی کشور فراهم شده است.لطفا برای اطلاعات بیشتر در رابطه با ماهیت انجمن با مدیریت انجمن ارتباط برقرار کنید
ساعت 04:31 AM بر حسب GMT +4 می باشد.