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

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

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

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

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