(ابتدا از مدیریت محترم به دلیل اینکه سوالم رو بد جا پرسیده بودم عذر می خوام)
آیا الگوریتم حریصانه برای مسئله انتخاب فعالیت ها جواب بهینه می دهد یا خیر؟
در کتاب مقسمی در تمرین ها نوشته که در کتاب آقای قلی زاده اثبات شده که جواب بهینه می دهد، اما هم در تست های کتاب الگوریتم مقسمی و هم یکی از اساتید مثال نقضی آوردند که جواب بهینه را نمی دهد؟
لطفا با دلیل راهنمایی کنید.
و سوال دوم اینکه درباره فلوید می گن که در گراف با وزن منفی بدون دور منفی درست کار می کند و قدرت تشخیص دور منفی را هم دارد، درباره الگوریتم Bell man Ford نیز همین را نوشته اند آیا درسته یعنی این موضوع اشتباه است که بلمن فورد در گراف با دور منفی درست کار می کند و همان هایی که برای فلوید گفته اند برای بلمن فورد هم صادق است؟ در این صورت که دیگر بلمن فورد و فلوید فرقی نمی کنند؟!
ممنون و سپاسگزارم
ممنون از پاسخ تون لطفا درباره بهینه بودن انتخاب فعالیت ها به روش حریص هم جواب بدید
الگوریتم های حریص الگوریتم های سریعی هستند و دیباگ کردن آنها کار آسانی است.
اما مشکل آنها این است که در بعضی مواقع جواب بهینه نمیدهند .
نحوه ی عمل
در این الگوریتم ها ما ابتدا داده ها را مرتب می کنیم و به تر تیب از آنها استفاده میکنیم در اینجا مسله را با یک مثال برایتان روشن می کنم
مثال یک کارخانه ی لبنیات در هر روز به مقداری شیر احتیاج دارد که آن را از گاوداری های منطقه خریداری می کند در این سوال هدف این است که شما حالتی را پیدا کنید که کارخانه کمترین پول را بپردازد
مثلا 20 لیتر شیر لازم داریم و 4 گاوداری هست که به ترتیب:
1- 10 لیتر شیر دارد و لیتری 20 $
2- 5 لیتر شیر دارد لیتری 2 $
3- 30 لیتر شیر دارد لیتری 15 $
4- 10 لیتر شیر دارد لیتری 10 $
جواب
ما باید ابتدا آنها را بر حسب مقدار پول مرتب کنیم سپس هر چه می توانیم از گاوداری اول شیر بخریم وسپس از دومی و به همین ترتیب ادامه می دهیم تا شیر مورد نیاز خریداری شود. در این مسله (185=5*2+10*10+5*15)
در این سوال الگوریتم گریدی درست کار می کند ولی در سوال بعدی نه.
فرض کنید که می خداهیم با تعدادی سکه {1و5و10و25و50} هزینه ی یک لباس{77} (چه ارزون از کجا خریدی؟) را بپردازیم
اول سکه ها را مرتب میکنیم سپس هر چه می توانیم از سکه ی اول (بزرگترین سکه) می پردازیم سپس از سکه ی بعدی و همین طور ادامه می دهیم.
حال فرص کنید سکه ها ی ما مال یک کشور تازه تاسیس است «ناکجا » {1و5و8و10} و می خداهیم یک لباس ارزون! بخریم {13} برتامه ی ما جواب {10و1و1و1} را چاپ می کند در حالی که جواب بهینه ی {8و5} نیز موجود است.
اگر یک الگوریتم گریدی(فارسی را پاس بداریم) حریص وجود داشت از آن استفاده کنید ولی حواستان با شد که جواب بهینه بدهد.
==
منبع »:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
ممنون از پاسخ تون ولی من بیشتر تاکیدم روی این هست که می خوام ببینم در مسئله انتخاب فعالیتها یا همان سخنران ها آیا حریص همیشه یک راه حل بهینه می دهد یا خیر؟، مثلا در سایر مسائلی که در فصل حریص بحث می شود مثل هافمن نیپولیتان اثبات می کند که حریص یک راه حل بهینه می دهد، اما برای مسئله سخنرانها(انتخاب فعالیت ها) صحبتی نشده.
بلی جواب بهینه میده
===
مثال دیگری که می‌توان عنوان کرد مسأ لهٔ زمان بندی چندین فعالیت در حال رقابت است که نیاز به استقادهٔ منحصر به فرد از یک منبع مشترک با هدف انتخاب مجموعه‌ای با ماکزیمم اندازه از فعالیت هایی که متقابلا با یکدیگر سازگارند، دارند.
فرض کنید یک مجموعهٔ s={a۱،a۲،….an} از n فعالیت پیشنهادی داریم که می خواهند از یک منبع استفاده نمایند، مانند یک تالار سخنرانی که در یک زمان می‌تواند تنها مورد استفادهٔ یک فعالیت قرار گیرد. هر فعالیت ai دارای زمان شروع si و زمان خاتمهٔ fi است به طوری که ۰≤si
F۰≤f۱≤f۲≤…≤fn≤fn+۱ ادعا می کنیم که sij=ᴓ هرگاه i≥j باشد. فرض کنید یک فعالیت ak€sij برای i≥j وجود دارد به طوری که ai بعد از aj در ترتیب مرتب قرار دارد. پس خواهیم داشت fi≤sk
اکنون فرض کنید جواب Aij برای sij شامل فعالیت ak می‌باشد.پس جواب‌های Aik برای sik و Akjبرای skj که در این جواب بهینه برای sij استفاده می‌شوند نیز باید بهینه باشند. بحث برش – و – الصاق معمول در این مورد بکار می‌رود. اگر یک جواب Áik برای sik می‌داشتیم که شامل فعالیت‌های بیشتری از Aik می‌بود، می‌توانستیم Aik را از داخل Aij برش داده و به داخل Áik الصاق نماییم، بنابراین یک جواب دیگر برای Sij با تعداد فعالیت‌های بیشتری از Aij تولید می‌شود. از آنجا که فرض کردیم Aij یک جواب بهینه است، به یک تناقض رسیده ایم. به طور مشابه اگر جواب Ákj برای skj را با فعالیت‌های بیشتر از Akj می‌داشتیم، می‌توانستیم Akj را با Ákj جایگزین کنیم تا یک جواب با فعالیت‌های بیشتری از Aij تولید نماییم.
اکنون از زیر ساختار بههینه خود استفاده کرده تا نشان دهیم که می‌توانیم یک جواب بهینه برای مسئله از روی جواب‌های بهینه زیر مسائل بسازیم. مشاهده کردم که هر جواب برای یک زیر مسئله غیر تهی sij شامل فعالیت ak است و آنکه هر جواب بهنه در درون خود شامل جواب‌های بهینه نمونه زیر مسئله‌های sik و skj می‌باشد. بنابراین، می‌توانیم یک زیر مجموعه با ماکزیمم اندازه از فعالیت‌های متقابلاً سازگار درSijبسازیم. با تقسیم مسئله به دو زیرمسئله (یافتن زیر مجموعه‌های با ماکزیمم اندازه از فعالیت‌های متقابلا سازگار در sikو skj) و پیداکردن زیرمجموعه‌های با ماکزیمم اندازه Aik و Akjاز فعالیت‌های متقابلا سازگار برای این زیر مسائل وسپس تشکیل زیر مجموعه Aij با ماکزیمم اندازه شامل فعالیت‌های متقابلا سازگار بصورت Aik υ {ak } υ Akj=Aij یک جواب بهینه برای کل مسئله یک جواب برای S۰،n+۱ است.
==
اینم منبع:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.