مسئله بهینه‌سازی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
بدون خلاصۀ ویرایش |
بدون خلاصۀ ویرایش |
||
خط ۱:
در ریاضیات و علوم کامپیوتر یک مسأله بهینه سازی، مسأله یافتن بهترین راه حل از میان همه راه حل های عملی می باشد. مسأله های بهینه سازی می تواند به دو دسته تقسیم شود که متغیرها پیوسته یا گسسته باشند. یک مسأله بهینه سازی با متغیرهای گسسته به عنوان یک مسأله بهینه سازی ترکیبی یا ترکیبیاتی شناخته می شوند. در یک مسأله بهینه سازی ترکیبی، ما به دنبال مجموعه ای از اشیاء از قبیل عدد صحیح، جایگشت و یا گرافی می گردیم که تعداد اعضایش محدود (و یا به طور قابل شمارش نامحدود) باشند.
==مسأله بهینه سازی پیوسته==
شکل استاندارد مسأله بهینه سازی (پیوسته) به صورت زیر است:
خط ۲۸:
=== مسأله بهینه سازی NP ===
یک مسأله بهینه سازی NP (NPO) یک مسأله بهینه سازی ترکیبی است با شرایط اضافی زیر. توجه داشته باشید که چند جمله ای های اشاره شده در زیر، توابعی با سایز متناسب با ورودی های تابع هستند، نه مجموعه ای مطلق از نمونه ورودی ها.
*سایز هر راه حل ممکن <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> می توانند در زمان چند جمله ای مشخص شوند و
*m در زمان چندجمله ای قابل محاسبه است.
| |||