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

برای هر مسأله بهینه سازی ترکیبی، یک [[مسئله تصمیم|مسأله تصمیم]] متناظر وجود دارد که می پرسد ببیند آیا یک راه حل ممکن برای مقدار خاص <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> با استفاده از ۱۰ یال یا کمتر وجود دارد؟» این مسأله با یک «بله» یا «خیر» ساده جواب داده می شود.

[[رده:مسئله‌هایمسأله‌های محاسباتی]]