با ظهور برنامه ریزی خطی، این روش ها برای مسائلی از جمله تخصیص، حداکثر جریان و حمل و نقل به کار گرفته شد. در عصر مدرن، بهینه‌سازی ترکیبی برای مطالعه الگوریتم‌ها مفید است، با ارتباط ویژه با هوش مصنوعی، یادگیری ماشین، و تحقیقات عملیات.
بهینه سازی ترکیبی برای چه استفاده می شود؟
بهینه‌سازی ترکیبی فرآیند جستجوی ماکزیمم (یا حداقل) یک تابع هدف F است که دامنه آن یک فضای پیکربندی گسسته اما بزرگ است (بر خلاف یک N بعدی). فضای پیوسته).
چرا بهینه سازی ترکیبی سخت است؟
مشکل از این واقعیت ناشی می شود که بر خلاف برنامه ریزی خطی، ناحیه امکان پذیر مسئله ترکیبی یک مجموعه محدب نیست.بنابراین، در عوض، باید شبکه‌ای از نقاط امکان‌پذیر، یا در مورد عدد صحیح مختلط، مجموعه‌ای از نیم‌خط‌ها یا پاره‌های خط متمایز را برای یافتن راه‌حل بهینه جستجو کنیم.
مسئله بهینه سازی ترکیبی چیست؟
بهینه سازی ترکیبی مبحثی است که شامل یافتن یک شی بهینه از مجموعه محدودی از اشیاء است … در حوزه مسائل بهینه سازی که در آن مجموعه ای از راه حل های امکان پذیر است عمل می کند. گسسته است یا می توان آن را به گسسته تقلیل داد و در آن هدف یافتن بهترین راه حل است.
آیا بهینه سازی ترکیبی NP سخت است؟
وقتی ثابت شد که یک نسخه تصمیم‌گیری از یک مسئله بهینه‌سازی ترکیبی متعلق به کلاس مسائل NP-complete است، آنگاه نسخه بهینه‌سازی NP-hard است… مسئله بهینه‌سازی، به عنوان مثال، یافتن حداقل تعداد (حداقل k) چند ضلعی های ستاره ای شکل که اتحاد آنها برابر با یک چندضلعی ساده معین است، NP-hard است.
