ورود

View Full Version : حرفه ای: مسئله کوله پشتی و طراحی به وسیله اگوریتم های حریصانه (Graedy)


hjran abdpor
پنج شنبه 01 اردیبهشت 1390, 17:04 عصر
با سلام به دوستان ..............................................


میخواستم بدونم ایا با طراحی حریصانه می توان همیشه جواب عالی و بهینه برای مسئله کوله پشتی تعیین کرد؟

میشه با مثال برام توضیح بدین ؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟///
hamid_2010
چهارشنبه 08 آذر 1391, 15:06 عصر
با سلام به دوستان ..............................................


میخواستم بدونم ایا با طراحی حریصانه می توان همیشه جواب عالی و بهینه برای مسئله کوله پشتی تعیین کرد؟

میشه با مثال برام توضیح بدین ؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟///


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

شما باید از روش پوبا استفاده کنید
اوبالیت به بو
دوشنبه 13 آذر 1391, 10:36 صبح
درود

روش Gready همیشه پاسخ بهینه به شما نمی دهد.

مخصوصا در مساله کوله پشتی زیرا که روش حریصانه یک روش ناآگاهانه برای حل مسائل هستش زیرا هیچ آینده نگری در اون وجود نداره و تصمیمات فقط بر اساس زمان حال گرفته میشه. به عبارت دیگر راه حل حریصانه در مساله کوله پشتی هیچ وقت نمی تونه بررسی کنه که آیا قطعه جواهری که الان توسط دزد در کوله پشتی قرارداده شده بعدها سبب سود میشه یا زیان. مثلا فضای زیادی از کوله پشتی رو اشغال کرده در حالیکه قطعه جواهر دیگه ای می تونه با حجم کمتر سود بیشتری رو نسیب دزد کنه.

در کل روش حریصانه راه حل بهینه در برخی مواقع به ما نمی ده.