مشكلة نجم الخاتم

الموسوعة الحرة

مثال على شبكة مشكلة النجمة الحلقية

مسألة النجمة الحلقية ( RSP ) هي مسألة صعبة الحل (NP-hard ) [ 1 ] في مجال التحسين التوافقي . في الرسم البياني المختلط الموزون الكامل ، تهدف مسألة النجمة الحلقية إلى إيجاد رسم بياني فرعي للنجمة الحلقية بأقل تكلفة ، يتكون من دورة (جزء الحلقة) ومجموعة من الأقواس (جزء النجمة)، بحيث ينتمي كل عقدة فرعية من كل قوس إلى الدورة، بينما لا ينتمي كل عقدة أصلية من كل قوس إليها. عادةً ما تختلف تكاليف الأقواس عن تكاليف الدورة. يجب أن تحتوي الدورة على عقدة واحدة على الأقل تُسمى المستودع أو الجذر.

مسألة حل الأقواس الحلقية (RSP) هي تعميم لمسألة البائع المتجول . [ 1 ] عندما تكون تكاليف الأقواس لا نهائية وتحتوي الحلقة على جميع العقد، فإن مسألة حل الأقواس الحلقية تُختزل إلى مسألة البائع المتجول (TSP) . تظهر بعض تطبيقات مسألة حل الأقواس الحلقية في سياق الاتصالات السلكية واللاسلكية ، [ 2 ] والنقل، أو الخدمات اللوجستية .

التركيبات الدقيقة

تمت صياغة مسألة النجمة الحلقية (RSP) لأول مرة عام 1998. [ 2 ] وقُدِّم أول نموذج برمجة خطية مختلطة الأعداد الصحيحة (MILP) لحل هذه المسألة عام 2004، إلى جانب متباينات صحيحة تُحسِّن الصياغة. [ 1 ] ومنذ ذلك الحين، طُرحت عدة صيغ دقيقة لحل مسألة النجمة الحلقية، مثل نموذج البرمجة الخطية الصحيحة القائم على طبقات الرسم البياني [ 3 ] ونموذج السلاسل st. [ 4 ]

أنواع مختلفة من مسألة النجمة الحلقية

تمت دراسة العديد من المتغيرات لمسألة النجمة الحلقية منذ عام 2006.

  • مشكلة النجمة ذات الحلقة m ذات السعة (2006) [ 5 ] [ 6 ]
  • مشكلة النجمة الحلقية متعددة المستودعات (2010) [ 7 ] [ 8 ]
  • مشكلة النجوم غير المنفصلة ذات الحلقة m (2014) [ 9 ]
  • مشكلة النجوم الحلقية القابلة للبقاء (2024) [ 10 ] [ 11 ]

الأساليب الاستدلالية

تم تقديم أول طريقة استدلالية لحل مشكلة RSP، وهي البحث العام في الجوار المتغير، بهدف الحصول على حلول تقريبية بسرعة أكبر. [ 12 ] وفي عام 2013، تم تطوير خوارزمية تطورية لتقريب حل مشكلة RSP. وفي عام 2020، تفوقت طريقة استدلالية تعتمد على خوارزمية تحسين مستعمرات النمل [ 13 ] على طريقة الخوارزمية التطورية.

مراجع

  1. 1 2 3 لابي، مارتين؛ لابورت، جيلبرت؛ مارتن، إنماكولادا رودريغيز؛ غونزاليس ، خوان خوسيه سالازار (مايو 2004). “مشكلة النجم الدائري: تحليل متعدد السطوح والخوارزمية الدقيقة”. الشبكات . 43 (3): 177-189 . دوى : 10.1002/net.10114 . ISSN 0028-3045 . 
  2. 1 2 شو، جيفينغ؛ تشيو، ستيف واي؛ غلوفر، فريد (1999). "تحسين شبكة اتصالات خطية خاصة حلقية باستخدام البحث المحظور" . علوم الإدارة . 45 (3): 330-345 . doi : 10.1287/mnsc.45.3.330 . ISSN 0025-1909 . JSTOR 2634881 .  
  3. ↑ سيمونيتي، ل.؛ فروتا، ي.؛ دي سوزا، س.س. (سبتمبر 2011). "مسألة الحلقة النجمية: صياغة جديدة للبرمجة العددية الصحيحة وخوارزمية التفرع والقطع". الرياضيات التطبيقية المنفصلة . 159 (16): 1901-1914 . doi : 10.1016/j.dam.2011.01.015 .
  4. ↑ كداد-سيدوم، صفية؛ نغوين، فييت هونغ (يناير 2010). "خوارزمية دقيقة لحل مسألة النجمة الحلقية" . التحسين . 59 (1): 125-140 . doi : 10.1080/02331930903500332 . ISSN 0233-1934 . 
  5. ↑ بالداتشي، ر.؛ ديل أميكو، م.؛ غونزاليس، ج. سالازار (ديسمبر 2007). "مسألة النجمة ذات الحلقة m ذات السعة المحدودة" . بحوث العمليات . 55 (6): 1147-1162 . doi : 10.1287/opre.1070.0432 . hdl : 11380/610536 . ISSN 0030-364X . 
  6. ↑ ناجي-عزيمي، زهرة؛ سالاري، ماجد؛ توث، باولو (16 ديسمبر 2010). "إجراء استدلالي لمسألة النجمة ذات الحلقة m ذات السعة المحدودة" . المجلة الأوروبية لبحوث العمليات . 207 (3): 1227-1234 . doi : 10.1016/j.ejor.2010.06.030 . ISSN 0377-2217 . 
  7. ↑ بالداتشي، ر.؛ ديل أميكو، م. (16 مايو 2010). "خوارزميات استدلالية لمسألة الحلقة النجمية متعددة المستودعات" . المجلة الأوروبية لبحوث العمليات . 203 (1): 270-281 . doi : 10.1016/j.ejor.2009.07.026 . hdl : 11380/659439 . ISSN 0377-2217 . 
  8. ↑ سوندار، كارثيك؛ راثينام، سيفاكومار (1 مارس 2017). "مسألة النجمة الحلقية متعددة المستودعات: دراسة متعددة الأوجه وخوارزمية دقيقة" . مجلة التحسين العالمي . 67 (3): 527-551 . arXiv : 1407.5080 . doi : 10.1007/s10898-016-0431-7 . ISSN 1573-2916 . 
  9. ↑ فويلو، بيير؛ كويستيل، أوريليان (أبريل 2014). "طريقة التفرع والقطع لمسألة النجمة غير المنفصلة ذات الحلقة m" . مجلة RAIRO - بحوث العمليات . 48 (2): 167-188 . doi : 10.1051/ro/2014006 . ISSN 0399-0559 . 
  10. ^ خامفوسون، جوليان. كاستانيو، فابيان؛ روسي، أندريه؛ توبالين ، سونيا (مارس 2024). "نسخة قابلة للنجاة من مشكلة النجمة الحلقية" . الشبكات . 83 (2): 324-347 . دوى : 10.1002/net.22193 .
  11. ^ ترونج، تران ماي آنه؛ توبالين، سونيا؛ روسي ، أندريه (مارس 2024). "مشكلة النجم الدائري التي يمكن النجاة منها في ظل فشل المحورين" . المؤتمر السنوي الخامس والعشرون لشركة Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2024) . جامعة بيكاردي جول فيرنيس.
  12. ^ دياس، ثايس كريستين س. دي سوزا فيلهو، جيلبرتو ف.؛ ماكامبيرا، الشيخ م.؛ دوس أنجوس إف كابرال، لوسيديو؛ فامبا، مارسيا هيلينا سي. (2006). "إرشادي فعال لمشكلة النجم الدائري" . الخوارزميات التجريبية . ملاحظات محاضرة في علوم الكمبيوتر. المجلد. 4007. سبرينغر. ص 24 – 35. دوى : 10.1007 / 11764298_3 . رقم ISBN   978-3-540-34597-8.
  13. ↑ زانغ، شياونينغ؛ جيانغ، لي؛ دينغ، بين؛ فانغ، شيانغ (1 يونيو 2021). "خوارزمية نظام مستعمرة النمل الهجينة لحل مشكلة النجمة الحلقية" . الذكاء التطبيقي . 51 (6): 3789-3800 . doi : 10.1007/s10489-020-02072-w . ISSN 1573-7497 .