زیربنای بهینه

در علم کامپیوتر، مسئله‌ای بهینه‌است که زیرمسئله‌های آن بهینه باشد. این ویژگی برای تعیین سودمندی در مسائل برنامه‌نویسی پویا و الگوریتم‌های حریصانه استفاده می‌شود. به‌طورمعمول، اگر بتوان اثبات کرد که زیر ساختارهای مسئله در هر گام بهینه‌است، از الگوریتم حریصانه برای حل مسئله با ساختار بهینه استفاده می‌شود(Cormen et al. pp. 381–2). در غیر این صورت از برنامه‌نویسی پویا و تداخل استفاده می‌شود. اگر الگوریتم‌های حریصانه مناسبی وجود نداشته باشد و مسائل در تداخل با شکست مواجه شوند، اغلب یک جستجوی طولانی اما آسان بهترین راه حل جایگزین است. در استفاده از برنامه‌نویسی پویا به بهینه‌سازی ریاضی، اصل بلمن ریچارد را از بهینگی است که این ایده، برای حل مسئله بهینه سازی پویاست، فرض کنید t مدت زمان شروع و T مدت زمان پایان است. به‌طور ضمنی برای حل زیر مسئله‌ها s را بین زمان شروع و پایان در نظر می‌گیریم. که این t<s<T نمونه‌ای از زیربنای بهینه است. اصل بهینگی برای استنتاج معادلات بلمن مورد استفاده قرار می‌گیرد. که نشان می‌دهد مقدار شروع مسئله با زمان t با شروع مسئله به زمان s وابسته است.

مثال

برای پیدا کردن کوتاهترین فاصله بین دو شهر با خودرو، همان‌طور که در شکل ۱ نشان داده شده‌است. این مثال، زیر بنای بهینه است که کوتاهترین مسیر از سیاتل به لس آنجلس پس از عبور از پورتلند و پس از آن ساکرامنتو، کوتاهترین مسیر از پورتلند به لس آنجلس باید از طریق ساکرامنتو عبور کند. در این مسئله تنیده شده‌است که چطور می‌توان از پورتلند به لس آنجلس رسید و همچنین چطور از سیاتل به لس آنجلس رسید. (خطوط مواج در نمودار، نشان دهنده راه حل‌های زیرمسئله هاست) مسئله پیدا کردن ارزانترین بلیط‌های هواپیمایی از بوئنوس آیرس به مسکو را در نظر بگیرید. حتی در صورتی که بلیط شامل توقف در میامی و به لندن باشد، نمی‌توان نتیجه گرفت که ارزان‌ترین قیمت بلیط از میامی به مسکو در لندن متوقف می‌شود، زیرا قیمت بلیط‌هایی که یک شرکت هواپیمایی به فروش می‌رساند برای یک سفر چند پروازه است در صورتی‌که حاصل جمع قیمت بلیط‌هایی که برای پرواز منحصربه‌فرد به فروش می‌رسد نیست.

تعریف

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

مسائل با استفاده از زیربنای بهینه

• مسئله بزرگترین زیر رشتهٔ مشترک
• مرتب‌سازی ادغام
• مرتب‌سازی سریع

مسائل بدون استفاده از زیربنای بهینه

• مسئله طولانی‌ترین مسیر
• حداقل هزینه عادلانه هواپیمایی. (با استفاده از Orbitz، ما می‌خواهیم به‌طور مکرر، ارزانترین پرواز از فرودگاه A به فرودگاه B که شامل یک اتصال به فرودگاه C است را پیدا کنیم اما ارزانترین پرواز از فرودگاه A به فرودگاه C شامل یک ارتباط از فرودگاه دیگر، D می‌باشد)