مسئله بهینه‌سازی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
قلی زادگان (بحث | مشارکت‌ها) بدون خلاصۀ ویرایش |
بدون خلاصۀ ویرایش |
||
خط ۱:
{{بهبود منبع}}
در [[ریاضیات]] و علوم کامپیوتر یک مسأله بهینه سازی، مسأله یافتن بهترین راه حل از میان همه راه حل های عملی می باشد. مسأله های بهینه سازی می تواند به دو دسته تقسیم شود که متغیرها پیوسته یا گسسته باشند. یک مسأله بهینه سازی با متغیرهای گسسته به عنوان یک مسأله بهینه سازی ترکیبی یا ترکیبیاتی شناخته می شوند. در یک مسأله بهینه سازی ترکیبی، ما به دنبال مجموعه ای از اشیاء از قبیل عدد صحیح، [[جایگشت]] و یا
==مسأله بهینه سازی پیوسته==
شکل استاندارد مسأله بهینه سازی (پیوسته) به صورت زیر است:
خط ۱۰:
\end{align}</math>
به طوری که:
* <math>f(x): \mathbb{R}^n \to \mathbb{R}</math> [[تابع]] مورد نظر ماست که می خواهیم بر روی <math>x</math> کمینه شود.
* <math>g_i(x) \leq 0</math> محدودیت نابرابری نامیده می شود و
* <math>h_i(x) = 0</math> محدودیت تساوی نامیده می شود.
خط ۱۸:
به طور رسمی یک بهینه سازی ترکیبی A یک چهارتایی <math>(I, f, m, g)</math> است به طوری که:
*<math>I</math> مجموعه نمونه هاست.
*برای یک نمونه <math>x \in I</math> داده شده، <math>f(x)</math> [[مجموعه]] راه حل های امکان پذیر است.
*برای یک مورد داده شده <math>x</math> و راه حل ممکن <math>y</math> برای <math>x</math>، <math>m(x, y)</math> اندازه <math>y</math> را مشخص می کند که معمولاً یک عدد حقیقی مثبت است.
*g هدف تابع است که یا برابر کمینه و یا بیشینه است.
خط ۲۵:
m(x, y) = g \{ m(x, y') \mid y' \in f(x) \} .
</math>
برای هر مسأله بهینه سازی ترکیبی، یک [[مسئله_تصمیم|مسأله تصمیم]] متناظر وجود دارد که می پرسد ببیند آیا یک راه حل ممکن برای مقدار خاص <math>m_0</math> وجود دارد یا نه. به عنوان مثال یک گراف <math>G</math> وجود دارد که شامل رئوس <math>u</math> و <math>v</math> یک مسأله بهینه سازی ممکن است «یافتن یک مسیر از <math>G</math> به <math>G</math> که از کمترین یال ها بگذرد» باشد. این مسأله ممکن است یک جواب مثلاً 4 داشته باشد. یک مسأله تصمیم متناظر این خواهد بود که «آیا یک مسیر از <math>G</math> به <math>G</math> با استفاده از ١٠ یال یا کمتر وجود دارد؟» این مسأله با یک «بله» یا «خیر» ساده جواب داده می شود.
در زمینه الگوریتم های تخمین، الگوریتم ها برای مسائل سخت برای یافتن راه حل های نزدیک بهینه طراحی می شوند. بنابراین یک نسخه معمول تصمیم، یک توصیف ناکافی از مسأله است زیرا فقط راه حل های قابل قبول را مشخص می کند. اگرچه می توانیم مسائل تصمیم مناسبی مطرح کنیم، این مسائل دیگر بیشتر به طور طبیعی، یک مسأله بهینه سازی می شوند.
=== مسأله بهینه سازی NP ===
یک مسأله بهینه سازی NP
*سایز هر راه حل ممکن <math>\scriptstyle y\in f(x)</math> به طور چند جمله ای محدود به سایز نمونه <math>x</math> داده شده است.
*زبان های <math>\scriptstyle \{\,x\,\mid\, x \in I \,\}</math> و <math>\scriptstyle \{\,(x,y)\, \mid\, y \in f(x) \,\}</math> می توانند در زمان چند جمله ای مشخص شوند و
خط ۳۴:
این دلالت بر این دارد که مسأله تصمیم متناظر، یک NP است. در علوم کامپیوتر، معمولاً مسائل بهینه سازی جالب توجه، ویژگی های بالا را دارند و بنابراین مسائل NPO هستند. یک مسأله به علاوه یک مسأله بهینه سازی نوع P یا PO خوانده می شود اگر الگوریتمی وجود داشته باشد که در زمان چندجمله ای راه حل بهینه را پیدا کند. معمولاً هنگام کار کردن با دسته NPO، مسائل بهینه سازی جالبی وجود دارد که نسخه های تصمیم، NP-سخت هستند. توجه داشته باشید که روابط سختی، همواره در تناسب با ساده سازی هستند. به علت ارتباط بین الگوریتم های تخمین و مسائل محاسباتی بهینه سازی، مسائل بهینه سازی با نسخه های تصمیم NP-تکمیل لزوماً NPO-تکمیل نامیده نمی شوند.
NPOPB یک دسته دیگر است؛ NPO با تابع هزینه محدود به چندجمله ای. مسائلی با این شرایط، ویژگی های مطلوب زیادی دارند.
== منابع ==▼
== جستارهای وابسته ==
*[[نظریه پیچیدگی محاسباتی]]
▲== منابع ==
* [http://en.wikipedia.org/w/index.php?title=Optimization_problem&oldid=468506162 ویکیپدیای انگلیسی مسأله بهینه سازی]
[[bn:সেরা সমাধান]]
| |||