مسئله بهینه‌سازی: تفاوت میان نسخه‌ها

 

== مسئله بهینه‌سازی پیوسته ==

 

== مسئله بهینه‌سازی ترکیبی ==

* <math>I</math> مجموعه نمونه هاست.

* برای یک نمونه <math>x \in I</math> داده شده، <math>f(x)</math> [[مجموعه (ریاضی)|مجموعه]] راه حل‌های امکان‌پذیر است.

</math>

برای هر مسئله بهینه‌سازی ترکیبی، یک [[مسئله تصمیم]] متناظر وجود دارد که می‌پرسد ببیند آیا یک راه حل ممکن برای مقدار خاص <math>m_0</math> وجود دارد یا نه. به عنوان مثال یک گراف <math>G</math> وجود دارد که شامل رئوس <math>u</math> و <math>v</math> یک مسئله بهینه‌سازی ممکن است «یافتن یک مسیر از <math>G</math> به <math>G</math> که از کمترین یال‌ها بگذرد» باشد. این مسئله ممکن است یک جواب مثلاً ۴ داشته باشد. یک مسئله تصمیم متناظر این خواهد بود که «آیا یک مسیر از <math>G</math> به <math>G</math> با استفاده از ۱۰ یال یا کمتر وجود دارد؟» این مسئله با یک «بله» یا «خیر» ساده جواب داده می‌شود.

 

=== مسئله بهینه‌سازی NP ===

* زبان‌های <math>\scriptstyle \{\,x\,\mid\, x \in I \,\}</math> و <math>\scriptstyle \{\,(x,y)\, \mid\, y \in f(x) \,\}</math> می‌توانند در زمان چندجمله‌ای مشخص شوند و

* m در زمان چندجمله‌ای قابل محاسبه است.