التحسين التوافقي

الموسوعة الحرة
الشجرة الممتدة الدنيا للرسم البياني المستوي الموزون . يُعد إيجاد الشجرة الممتدة الدنيا مشكلة شائعة تتضمن التحسين التوافقي.

يُعدّ التحسين التوافقي فرعًا من فروع التحسين الرياضي ، ويتمثل في إيجاد الحل الأمثل من بين مجموعة محدودة من الحلول الممكنة، [ 1 ] حيث تكون مجموعة الحلول الممكنة منفصلة أو يمكن اختزالها إلى مجموعة منفصلة. ومن الأمثلة الشائعة على مسائل التحسين التوافقي: مسألة البائع المتجول (TSP)، ومسألة الشجرة الممتدة الدنيا (MST)، ومسألة حقيبة الظهر . في العديد من هذه المسائل، كما في المسائل المذكورة سابقًا، لا يُمكن إجراء بحث شامل ، لذا يجب اللجوء إلى خوارزميات متخصصة تستبعد بسرعة أجزاءً كبيرة من فضاء البحث، أو إلى خوارزميات تقريبية .

يرتبط التحسين التوافقي ببحوث العمليات ، ونظرية الخوارزميات ، ونظرية التعقيد الحسابي . وله تطبيقات مهمة في العديد من المجالات، بما في ذلك الذكاء الاصطناعي ، والتعلم الآلي ، ونظرية المزادات ، وهندسة البرمجيات ، والدوائر المتكاملة واسعة النطاق، والرياضيات التطبيقية ، وعلوم الحاسوب النظرية .

التطبيقات

تشمل التطبيقات الأساسية للتحسين التوافقي، على سبيل المثال لا الحصر:

طُرق

يوجد كمٌّ كبير من المؤلفات حول خوارزميات الوقت متعدد الحدود لفئات خاصة من مسائل التحسين المتقطع. ويُوحَّد جزء كبير منها بنظرية البرمجة الخطية . ومن أمثلة مسائل التحسين التوافقي التي يغطيها هذا الإطار: أقصر المسارات وأشجار أقصر المسارات ، والتدفقات والدورات ، والأشجار الممتدة ، والمطابقة ، ومسائل الماترويد .

بالنسبة لمسائل التحسين المنفصلة الكاملة من نوع NP ، تتضمن الأدبيات البحثية الحالية المواضيع التالية:

يمكن النظر إلى مسائل التحسين التوافقي على أنها بحث عن أفضل عنصر من مجموعة من العناصر المنفصلة؛ لذا، من حيث المبدأ، يمكن استخدام أي نوع من خوارزميات البحث أو الخوارزميات فوق الحدسية لحلها. تشمل الأساليب واسعة الانتشار: التفرع والتقييد (خوارزمية دقيقة يمكن إيقافها في أي وقت لتكون بمثابة خوارزمية حدسية)، والتفرع والقطع (تستخدم التحسين الخطي لتوليد الحدود)، والبرمجة الديناميكية (بناء حل تكراري مع نافذة بحث محدودة)، والبحث المحظور (خوارزمية تبديل من النوع الجشع). مع ذلك، لا تضمن خوارزميات البحث العامة إيجاد الحل الأمثل أولًا، كما لا تضمن سرعة تنفيذها (في وقت متعدد الحدود). بما أن بعض مسائل التحسين المنفصلة هي مسائل NP-كاملة ، مثل مسألة البائع المتجول (مسألة القرار)، [ 6 ] فإن هذا متوقع ما لم تكن P=NP .

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

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

مشكلة تحسين NP

مسألة التحسين من نوع NP (NPO) هي مسألة تحسين توافقي مع الشروط الإضافية التالية. [ 8 ] تجدر الإشارة إلى أن كثيرات الحدود المشار إليها أدناه هي دوال لحجم مدخلات الدوال المعنية، وليس لحجم مجموعة ضمنية من حالات الإدخال.

  • حجم كل حل ممكنy∈و(x){\displaystyle y\in f(x)}، أينو(x){\displaystyle f(x)}يشير إلى مجموعة الحلول الممكنة للمثالx{\displaystyle x}، محدود متعدد الحدود بالنسبة لحجم الحالة المعطاةx{\displaystyle x}،
  • لغات الحالات الصالحة{x|x∈أنا}{\displaystyle \{\,x\,\mid \,x\in I\,\}}ومن أزواج الحالات والحلول الصالحة{(x،y)|y∈و(x)}{\displaystyle \{\,(x,y)\,\mid \,y\in f(x)\,\}}يمكن التعرف عليها في وقت متعدد الحدود ، و
  • الإجراءم(x،y){\displaystyle m(x,y)}من حلy{\displaystyle y}مشكلةx{\displaystyle x}قابلة للحساب في وقت متعدد الحدود .

هذا يعني أن مسألة القرار المقابلة تقع ضمن فئة NP . في علوم الحاسوب، عادةً ما تتمتع مسائل التحسين المهمة بالخصائص المذكورة أعلاه، وبالتالي تُصنف ضمن مسائل NPO. تُسمى المسألة أيضًا مسألة تحسين من النوع P (PO) إذا وُجدت خوارزمية تجد الحلول المثلى في وقت متعدد الحدود. غالبًا، عند التعامل مع فئة NPO، يكون الاهتمام منصبًا على مسائل التحسين التي تكون فيها صيغ القرار من فئة NP-كاملة . تجدر الإشارة إلى أن علاقات الصعوبة ترتبط دائمًا باختزال ما. نظرًا للارتباط بين خوارزميات التقريب ومسائل التحسين الحسابي، يُفضل في هذا المجال الاختزالات التي تحافظ على التقريب في جانب ما على اختزالات تورينج وكارب المعتادة . مثال على هذا الاختزال هو اختزال L. لهذا السبب، لا تُسمى مسائل التحسين ذات صيغ القرار من فئة NP-كاملة بالضرورة مسائل NPO-كاملة. [ 9 ]

تنقسم NPO إلى الفئات الفرعية التالية وفقًا لإمكانية تقريبها: [ 8 ]

  • NPO(I) : يساوي FPTAS . يحتوي على مسألة حقيبة الظهر .
  • NPO(II) : يساوي PTAS . يحتوي على مشكلة جدولة Makespan .
  • NPO(III) : فئة مسائل NPO التي تمتلك خوارزميات ذات وقت متعدد الحدود، والتي تحسب الحلول بتكلفة لا تتجاوز c ضعف التكلفة المثلى (لمسائل التصغير) أو بتكلفة لا تقل عن1/ج{\displaystyle 1/c}من التكلفة المثلى (لمسائل التعظيم). في كتاب هرومكوفيتش " خوارزميات للمسائل الصعبة" ، تُستثنى من هذه الفئة جميع مسائل NPO(II) باستثناء حالة P=NP. [ 8 ] بدون الاستثناء، تُساوي APX. تتضمن MAX-SAT و TSP المتري .
  • NPO(IV) : فئة مسائل NPO التي تستخدم خوارزميات ذات زمن متعدد الحدود لتقريب الحل الأمثل بنسبة متعددة الحدود في لوغاريتم حجم المدخلات. في كتاب هرومكوفيتش، تُستثنى جميع مسائل NPO(III) من هذه الفئة ما لم تكن P=NP. تتضمن هذه الفئة مسألة تغطية المجموعة .
  • NPO(V) : فئة مسائل NPO ذات الخوارزميات متعددة الحدود التي تقارب الحل الأمثل بنسبة محدودة بدالة ما على n. في كتاب هرومكوفيتش، تُستثنى جميع مسائل NPO(IV) من هذه الفئة ما لم تكن P=NP. تتضمن هذه الفئة مسألة البائع المتجول (TSP) ومسألة الزمرة .

تُسمى مسألة NPO محدودة متعددة الحدود (PB) إذا، لكل حالةx{\displaystyle x}ولكل حلy∈و(x){\displaystyle y\in f(x)}، الإجراءم(x،y){\displaystyle m(x,y)}وهي محدودة بدالة متعددة الحدود من حجمx{\displaystyle x}. فئة NPOPB هي فئة مسائل NPO التي تكون محدودة متعددة الحدود.

مشاكل محددة

جولة مثالية لبائع متجول عبر أكبر 15 مدينة في ألمانيا . وهي أقصر جولة من بين 43,589,145,600 جولة ممكنة [ 10 ] تزور كل مدينة مرة واحدة فقط.

انظر أيضاً

ملحوظات

  1. ↑ Schrijver 2003 ، ص. 1 . 
  2. ↑ سبيحي، عبد القادر؛ إيغليس، ريتشارد و. (2007). "التحسين التوافقي واللوجستيات الخضراء" ( ملف PDF) . 4OR . 5 (2): 99-116 . doi : 10.1007/s10288-007-0047-3 . S2CID 207070217. مؤرشف (ملف PDF) من الأصل بتاريخ 26-12-2019 . تم الاطلاع عليه بتاريخ 26-12-2019 . 
  3. ↑ إسكندربور، ماجد؛ ديجا، بيير؛ ميمتشيك، جو؛ بيتون، أوليفييه (2015). "تصميم شبكة سلسلة التوريد المستدامة: مراجعة موجهة نحو التحسين" (ملف PDF) . أوميغا . 54 : 11-32 . doi : 10.1016/j.omega.2015.01.006 . مؤرشف (ملف PDF) من الأصل بتاريخ 26-12-2019 . تم الاطلاع عليه بتاريخ 26-12-2019 .
  4. ↑ هوبي، أليكس؛ فوغلر، دانيال؛ سيبولد، مارتن ب.؛ إبيغبو، أنوزي؛ سيتغاست، راندولف ر.؛ سار، مارتن أ. (2018). "تقدير معدلات تدفق السوائل عبر شبكات الكسور باستخدام التحسين التوافقي" . التقدم في موارد المياه . 122 : 85-97 . arXiv : 1801.08321 . Bibcode : 2018AdWR..122...85H . doi : 10.1016/j.advwatres.2018.10.002 . S2CID 119476042. مؤرشف من الأصل في 21 أغسطس 2020. تم الاسترجاع في 16 سبتمبر 2020 . 
  5. ↑ كوك 2016 .
  6. ↑ "تقريب مسألة البائع المتجول" (ملف PDF) . مؤرشف (ملف PDF) من الأصل بتاريخ 1 مارس 2022. تم الاطلاع عليه بتاريخ 17 فبراير 2022 .
  7. ↑ أوسييلو، جورجيو؛ وآخرون (2003)، التعقيد والتقريب ( طبعة منقحة)، سبرينغر، ISBN   978-3-540-65431-5
  8. 1 2 3 هرومكوفيتش، يوراي (2002)، خوارزميات للمسائل الصعبة ، نصوص في علوم الحاسوب النظرية ( الطبعة الثانية)، سبرينغر، ISBN  978-3-540-44134-2
  9. ↑ كان، فيجو (1992)، حول إمكانية تقريب مسائل التحسين الكاملة من فئة NP ، المعهد الملكي للتكنولوجيا، السويد، ISBN 91-7170-082-X
  10. ↑ خذ مدينة واحدة، وخذ جميع الترتيبات الممكنة للمدن الـ 14 الأخرى. ثم اقسم على اثنين لأنه لا يهم ترتيبها الزمني: 14!/2 = 43,589,145,600.

مراجع

  • لولر، يوجين (2001). التحسين التوافقي: الشبكات والمصفوفات . دوفر. ISBN 0-486-41453-1.
  • باباديميتريو، كريستوس هـ.؛ ستيغليتز، كينيث (يوليو 1998). التحسين التوافقي  : الخوارزميات والتعقيد . دوفر. ISBN 0-486-40258-4.
  • سيركسما، جيرارد ؛ غوش، ديبتيش (2010). الشبكات في العمل: تمارين نصية وحاسوبية في تحسين الشبكات . سبرينغر. ISBN 978-1-4419-5512-8.
  • جيرارد سيركسما؛ يوري زوولز (2015). التحسين الخطي والأعداد الصحيحة: النظرية والتطبيق . الصحافة اتفاقية حقوق الطفل. رقم ISBN 978-1-498-71016-9.