بلی جواب بهینه میده
===
مثال دیگری که می‌توان عنوان کرد مسأ لهٔ زمان بندی چندین فعالیت در حال رقابت است که نیاز به استقادهٔ منحصر به فرد از یک منبع مشترک با هدف انتخاب مجموعه‌ای با ماکزیمم اندازه از فعالیت هایی که متقابلا با یکدیگر سازگارند، دارند.


فرض کنید یک مجموعهٔ 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+۱ است.

==
اینم منبع:

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.