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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو


در علم کامپیوتر، مساله‌ای بهینه‌است که زیرمساله‌های آن بهینه باشد. این ویژگی برای تعیین سودمندی در مسائل برنامه نویسی پویا و الگوریتم‌های حریصانه استفاده می‌شود.[۱] به طورمعمول، اگر بتوان اثبات کرد که زیر ساختارهای مساله در هر گام بهینه‌است، از الگوریتم حریصانه برای حل مساله با ساختار بهینه استفاده می‌شود(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.