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

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

مثال

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

تعریف

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

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

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

منابع
  1. Introduction to Algorithms, 2nd ed., (Cormen, Leiserson, Rivest, and Stein) 2001, p. 327. ISBN 0-262-03293-7.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.