مسئله بهینه‌سازی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
صفحه‌ای جدید حاوی 'در ریاضیات و علوم کامپیوتر یک مسأله بهینه سازی، مسأله یافتن بهترین راه حل از م...' ایجاد کرد برچسب: مطالب زیاد ویکی‌سازی نشده وارده‌شده است.(AF) |
بدون خلاصۀ ویرایش |
||
خط ۳۱:
*زبان های <math>\scriptstyle \{\,x\,\mid\, x \in I \,\}</math> و <math>\scriptstyle \{\,(x,y)\, \mid\, y \in f(x) \,\}</math> می توانند در زمان چند جمله ای مشخص شوند و
*m در زمان چندجمله ای قابل محاسبه است.
این دلالت بر این دارد که مسأله تصمیم متناظر، یک NP است. در علوم کامپیوتر، معمولاً مسائل بهینه سازی جالب توجه، ویژگی های بالا را دارند و بنابراین مسائل NPO هستند. یک مسأله به علاوه یک مسأله بهینه سازی نوع P یا PO خوانده می شود اگر الگوریتمی وجود داشته باشد که در زمان چندجمله ای راه حل بهینه را پیدا کند. معمولاً هنگام کار کردن با دسته NPO، مسائل بهینه سازی جالبی وجود دارد که نسخه های تصمیم، NP-سخت هستند. توجه داشته باشید که روابط سختی، همواره در تناسب با ساده سازی هستند. به علت ارتباط بین الگوریتم های تخمین و مسائل محاسباتی بهینه سازی، مسائل بهینه سازی با نسخه های تصمیم NP-تکمیل لزوماً NPO-تکمیل نامیده نمی شوند.
NPOPB یک دسته دیگر است؛ NPO با تابع هزینه محدود به چندجمله ای. مسائلی با این شرایط، ویژگی های مطلوب زیادی دارند.
== منابع ==
ویکی پدیای انگیسی
== جستارهای وابسته ==
[[نظریه پیچیدگی محاسباتی]]
[[bn:সেরা সমাধান]]
[[cs:Optimalizační problém]]
[[de:Optimierungsproblem]]
[[sr:Оптимизациони проблем]]
[[sv:Optimeringsproblem]]
[[uk:Задача оптимізації]]
[[zh:最佳化問題]]
[[en:Optimization_problem]]
| |||