مشكلة التحسين

في الرياضيات والهندسة وعلوم الحاسوب والاقتصاد ، تُعتبر مشكلة التحسين مشكلة إيجاد الحل الأمثل من بين جميع الحلول الممكنة .

يمكن تقسيم مسائل التحسين إلى فئتين، اعتمادًا على ما إذا كانت المتغيرات متصلة أم منفصلة :

• تُعرف مشكلة التحسين ذات المتغيرات المنفصلة باسم التحسين المنفصل ، حيث يجب إيجاد كائن مثل عدد صحيح أو تبديل أو رسم بياني من مجموعة قابلة للعد .
• تُعرف المسألة التي تتضمن متغيرات متصلة باسم التحسين المستمر ، حيث يجب إيجاد القيمة المثلى من دالة متصلة . ويمكن أن تشمل هذه المسائل مسائل مقيدة ومسائل متعددة الأنماط.

في سياق مسائل التحسين، تشير مساحة البحث إلى مجموعة جميع النقاط أو الحلول الممكنة التي تُحقق قيود المسألة أو أهدافها. ^{[ 1 ]} تُمثل هذه النقاط الحلول الممكنة التي يُمكن تقييمها لإيجاد الحل الأمثل وفقًا لدالة الهدف. غالبًا ما تُحدد مساحة البحث بنطاق الدالة المراد تحسينها، والذي يشمل جميع المدخلات الصالحة التي تُلبي متطلبات المسألة. ^{[ 2 ]}

قد يختلف نطاق البحث اختلافًا كبيرًا في الحجم والتعقيد تبعًا للمسألة. فعلى سبيل المثال، في مسألة التحسين المستمر، قد يكون نطاق البحث مجالًا متعدد الأبعاد ذو قيم حقيقية محددًا بحدود أو قيود. أما في مسألة التحسين المتقطع، مثل التحسين التوافقي، فقد يتكون نطاق البحث من مجموعة محدودة من التباديل أو التوافيق أو التكوينات.

في بعض السياقات، قد يشير مصطلح " مساحة البحث" أيضًا إلى تحسين المجال نفسه، مثل تحديد المجموعة الأنسب من المتغيرات أو المعايير لتعريف المشكلة. يُعد فهم مساحة البحث والتنقل فيها بفعالية أمرًا بالغ الأهمية لتصميم خوارزميات فعّالة، إذ يؤثر ذلك بشكل مباشر على التعقيد الحسابي واحتمالية إيجاد الحل الأمثل.

الشكل القياسي لمسألة التحسين المستمر هو ^{[ 3 ]}$${\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\\&&&h_{j}(x)=0,\quad j=1,\dots ,p\end{aligned}}}$$ أين

• f  : ℝ ⁿ → ℝ هي دالة الهدف التي يجب تقليلها على المتجه x ذي n متغير،
• تُسمى القيود g _i ( x ) ≤ 0 قيودًا غير متباينة
• تُسمى القيود h _j ( x ) = 0 قيود المساواة ، و
• m ≥ 0 و p ≥ 0 .

إذا كانت m = p = 0 ، فإن المسألة تُعدّ مسألة تحسين غير مقيدة. وبحسب الاصطلاح، يُعرّف الشكل القياسي مسألة تصغير . ويمكن معالجة مسألة التعظيم بنفي دالة الهدف.

بصورة رسمية، تُعتبر مسألة التحسين التوافقي A رباعية ( I ، f ، m ، g ) ، حيث

• I عبارة عن مجموعة من الحالات؛
• بالنظر إلى مثال x ∈ I ، فإن f ( x ) هي مجموعة الحلول الممكنة؛
• بالنظر إلى مثال x وحل ممكن y لـ x ، فإن m ( x , y ) يشير إلى مقياس y ، وهو عادة ما يكون عددًا حقيقيًا موجبًا .
• g هي دالة الهدف، وهي إما قيمة دنيا أو قيمة عظمى .

الهدف إذن هو إيجاد حل أمثل لبعض الحالات x ، أي حل ممكن y مع $${\displaystyle m(x,y)=g\left\{m(x,y'):y'\in f(x)\right\}.}$$

لكل مسألة تحسين توافقي، توجد مسألة قرار مقابلة تسأل عما إذا كان هناك حل ممكن لمقياس معين m _{≥ 0.} على سبيل المثال، إذا كان لدينا رسم بياني G يحتوي على الرأسين u و v ، فقد تكون مسألة التحسين هي "إيجاد مسار من u إلى v يستخدم أقل عدد ممكن من الحواف". قد تكون إجابة هذه المسألة، على سبيل المثال، 4. أما مسألة القرار المقابلة فهي "هل يوجد مسار من u إلى v يستخدم 10 حواف أو أقل؟" ويمكن الإجابة على هذه المسألة ببساطة بـ "نعم" أو "لا".

في مجال خوارزميات التقريب ، تُصمَّم الخوارزميات لإيجاد حلول شبه مثالية للمسائل المعقدة. ولذلك، فإن صيغة القرار المعتادة تُعدّ تعريفًا غير كافٍ للمسألة، لأنها تُحدِّد فقط الحلول المقبولة. مع أنه يُمكننا طرح مسائل قرار مناسبة، إلا أن المسألة تُصنَّف بشكل طبيعي أكثر على أنها مسألة تحسين. ^{[ 4 ]}

• مشكلة العد (التعقيد) – نوع من أنواع المشاكل الحسابية 
• تحسين التصميم
• مبدأ إيكيلاند التبايني
• مشكلة الدوال – نوع من أنواع المسائل الحسابية 
• مشكلة القفاز – مشكلة تحسين في بحوث العمليات 
• بحوث العمليات – تخصص يتعلق بتطبيق الأساليب التحليلية المتقدمة 
• الاكتفاء – أسلوب استدلالي معرفي للبحث عن قرار مقبول – لا يلزم إيجاد الحل الأمثل، بل يكفي إيجاد حل "جيد بما فيه الكفاية". 
• مشكلة البحث – فئة من المشكلات الحسابية 
• البرمجة شبه اللانهائية

• "كيف يُحسّن تشكيل حركة البيانات عرض النطاق الترددي للشبكة" . IPC . 12 يوليو 2016. تم الاطلاع عليه بتاريخ 13 فبراير 2017 .