مشكلة لاعب الجولف الاجتماعي

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
📷 يحتوي على 16 صور
الموسوعة الحرة

في الرياضيات المتقطعة ، تُعد مسألة لاعب الجولف الاجتماعي ( SGP ) مسألة تصميم توافقي مستمدة من سؤال تم نشره في مجموعة أخبار usenet sci.op-research في مايو 1998. [ 1 ] المسألة هي كما يلي: 32 لاعب جولف يلعبون الجولف مرة واحدة في الأسبوع في مجموعات من 4. جدولة هؤلاء اللاعبين للعب لأطول فترة ممكنة دون أن يلعب أي لاعبين معًا في مجموعة واحدة أكثر من مرة.

وبشكل أعم، يمكن تعريف هذه المشكلة لأين=ز×s{\displaystyle n=g\times s}لاعبو الغولف الذين يلعبون فيز{\displaystyle g}مجموعات منs{\displaystyle s}لاعبو الغولف لـw{\displaystyle w}أسابيع. يتضمن الحل إما التحقق من وجود جدول زمني أو نفيه، وإذا كان هذا الجدول موجودًا، تحديد عدد الجداول الزمنية الفريدة وإنشائها.

التحديات

التباديل التي تؤدي إلى حلول متماثلة لمشكلة لاعب الغولف الاجتماعي.

تُعتبر مسألة SGP مشكلة صعبة الحل لسببين رئيسيين: [ 2 ]

أولاً، مساحة البحث الكبيرة الناتجة عن الطبيعة التوافقية والمتناظرة للغاية للمسألة. يوجد إجمالي(ن!)w{\displaystyle (n!)^{w}}الجداول الزمنية في مساحة البحث. لكل جدول زمني، الأسابيع(w!){\displaystyle (w!)}، مجموعات داخل كل أسبوع(ز!){\displaystyle (g!)}، اللاعبون داخل كل مجموعة(s!){\displaystyle (s!)}واللاعب الفردي(ن!){\displaystyle (n!)}يمكن تبديل جميعها. وهذا يؤدي إلى إجماليw!×ز!×s!×ن!{\displaystyle w!\times g!\times s!\times n!}التشاكلات هي جداول متطابقة من خلال أي من عمليات التناظر هذه. ونظرًا لتناظرها العالي، تُستخدم SGP عادةً كمعيار قياسي في كسر التناظر في برمجة القيود ( قيود كسر التناظر ).

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

الحلول

نظام SGP هو نظام شتاينر S(2,4,32) لأن 32 لاعب غولف يُقسّمون إلى مجموعات من 4 لاعبين، ويمكن تحديد المجموعة والأسبوع المخصصين لأي لاعبين بشكل فريد. بعد فترة وجيزة من طرح المشكلة عام 1998، تم التوصل إلى حل لمدة 9 أسابيع، وثبت استحالة وجود حل لمدة 11 أسبوعًا. في الحالة الأخيرة، تجدر الإشارة إلى أن كل لاعب يجب أن يلعب مع 3 لاعبين مختلفين كل أسبوع. بالنسبة لجدول زمني مدته 11 أسبوعًا، سيتم تجميع اللاعب مع ما مجموعه3×11=33{\displaystyle 3\times 11=33}لاعبون آخرون. بما أن عدد اللاعبين الآخرين في المجموعة لا يتجاوز 31 لاعبًا، فإن هذا غير ممكن. [ 3 ] من المعروف الآن أنه يمكن التوصل إلى حل لمدة 10 أسابيع من نتائج نشرها هاو شين عام 1996، ولكن لم يتم بناؤه بشكل صريح. [ 4 ] تم بناء أول حل صريح بشكل مستقل من قبل أليخاندرو أغوادو عام 2004 باستخدام طريقة مختلفة. [ 5 ] هذا هو الحل المعروض أدناه.

حل لمدة 10 أسابيع لمشكلة لاعب الجولف الاجتماعي (أغوادو - 2004)
المجموعة 1المجموعة الثانيةالمجموعة 3المجموعة الرابعةالمجموعة 5المجموعة 6المجموعة 7المجموعة 8
الأسبوع الأول٠، ١، ٢، ٣4، 5، 22، 236،7،20،218، 25، 26، 279، 10، 11، 2412، 13، 15، 3014، 28، 29، 3116، 17، 18، 19
الأسبوع الثاني0,4,8,281، 6، 18، 232،7،17،223، 5، 26، 319، 13، 14، 2710، 15، 19، 2111، 25، 29، 3012، 16، 20، 24
الأسبوع الثالث0، 11، 14، 211،7،10،282، 15، 20، 253، 13، 22، 244،9،18،315، 16، 27، 306، 8، 19، 2912، 17، 23، 26
الأسبوع الرابع0,18,24,271، 9، 19، 262، 8، 11، 163، 10، 17، 254،7،12،295، 6، 14، 1513، 20، 23، 2821، 22، 30، 31
الأسبوع الخامس0,6,13,261، 4، 11، 152،9،21،283، 8، 14، 235، 12، 18، 257، 19، 24، 3010، 16، 22، 2917، 20، 27، 31
الأسبوع السادس0,7,25,311، 5، 24، 292، 12، 14، 193، 18، 28، 304، 6، 10، 278، 13، 17، 219، 15، 16، 2311، 20، 22، 26
الأسبوع السابع0,5,19,201، 14، 22، 252، 23، 27، 293، 4، 16، 216، 9، 17، 307، 11، 13، 188، 10، 12، 3115، 24، 26، 28
الأسبوع الثامن0،15،17،291، 13، 16، 312، 4، 26، 303، 6، 11، 125، 7، 8، 910، 14، 18، 2019، 22، 27، 2821، 23، 24، 25
الأسبوع التاسع0,9,12,221، 8، 20، 302، 5، 10، 133،7،15،274، 14، 17، 246، 16، 25، 2811، 19، 23، 3118، 21، 26، 29
الأسبوع العاشر0، 10، 23، 301، 12، 21، 272، 6، 24، 313، 9، 20، 294، 13، 19، 255، 11، 17، 287، 14، 16، 268، 15، 18، 22

هناك العديد من الأساليب لحل مشكلة SGP، وهي تقنيات نظرية التصميم ، [ 6 ] [ 7 ] صيغ SAT ( مشكلة الإرضاء الافتراضي )، والأساليب القائمة على القيود ، [ 8 ] والأساليب الميتاهوريستية ، ونهج الجذر.

يصنف أسلوب الجذر لاعبي الغولف إلى مجموعات بناءً على مجموع الأرقام في الأساسك{\displaystyle k}[ 9 ] يمكن إعادة تعريف المتغيرات في الحالة العامة لـ SGP على النحو التالي :ن=sك{\displaystyle n=s^{k}}لاعبو الغولف الذين يلعبون فيز=sك-1{\displaystyle g=s^{k-1}}مجموعات منs{\displaystyle s}لاعبو الغولف لأي عددك{\displaystyle k}الحد الأقصى لعدد الأسابيع التي يمكن لهؤلاء اللاعبين لعبها دون إعادة تجميع أي لاعبين اثنين هو(sك-1)/(s-1){\displaystyle (s^{k}-1)/(s-1)}.

التطبيقات

يُشجع العمل الجماعي في الفصول الدراسية لأنه يعزز التعلم النشط وتنمية مهارات التفكير النقدي والتواصل. وقد استُخدم برنامج SGP لتوزيع الطلاب على مجموعات في مقررات الكيمياء الجامعية [ 9 ] وغرف الاجتماعات الفرعية في برامج الاجتماعات عبر الإنترنت [ 10 ] لزيادة تفاعل الطلاب وتواصلهم الاجتماعي إلى أقصى حد.

وقد تم استخدام برنامج SGP أيضًا كنموذج لدراسة جدولة البطولات. [ 11 ]

انظر أيضاً

مراجع

  1. ↑ هارفي، وارويك. "المشكلة 010: مشكلة لاعبي الغولف الاجتماعيين" . www.csplib.org . تم الاطلاع عليه بتاريخ 6 سبتمبر 2021 .
  2. ↑ ليو، كي؛ لوفلر، سفين؛ هوفستيدت، بيترا (2019). "إعادة النظر في مشكلة لاعب الغولف الاجتماعي". في: فان دن هيريك، ياب؛ روشا، آنا باولا؛ ستيلز، لوك (محررون). الوكلاء والذكاء الاصطناعي: المؤتمر الدولي الحادي عشر، ICAART 2019، براغ، جمهورية التشيك، 19-21 فبراير 2019، أوراق مختارة منقحة . دار نشر سبرينغر الدولية. الصفحات 72-99 . doi : 10.1007/978-3-030-37494-5_5 . ISBN  978-3-030-37494-5.
  3. ↑ تريسكا، ماركوس. "مشكلة لاعب الجولف الاجتماعي" . www.metallevel.at .
  4. ↑ شين، هاو (1996). "وجود تصاميم قابلة للقسمة على مجموعات قابلة للحل بحجم كتلة أربعة وحجم مجموعة اثنين أو ثلاثة". مجلة جامعة شنغهاي جياوتونغ . 1 (1): 68-70 . MR 1454271 . 
  5. ↑ أغوادو، أليخاندرو. "حلٌّ لمشكلة لاعب الغولف الاجتماعي في 10 أيام" (ملف PDF) . ألغاز رياضية . تم الاطلاع عليه بتاريخ 9 سبتمبر 2021 .
  6. ↑ لاردو، فريدريك؛ مونفروي، إريك (2015). "نمذجة مشكلة لاعب الغولف الاجتماعي في SAT بشكل تعبيري" . وقائع علوم الحاسوب . 51 : 336-345 . doi : 10.1016/j.procs.2015.05.252 .
  7. ↑ تريسكا، ماركوس؛ موسليو، نيسرت (أبريل 2012). "صياغة محسّنة لمسألة SAT لمشكلة لاعب الغولف الاجتماعي". حوليات بحوث العمليات . 194 (1): 427-438 . doi : 10.1007/s10479-010-0702-5 .
  8. ↑ ليو، كي؛ لوفلر، سفين؛ هوفستيدت، بيترا (2019). "حل مشكلات لاعبي الغولف الاجتماعيين باستخدام البرمجة المقيدة في التسلسل والتوازي". في: روشا، آنا؛ ستيلز، لوك؛ فان دن هيريك، ياب (محررون). وقائع المؤتمر الدولي الحادي عشر حول الوكلاء والذكاء الاصطناعي . منشورات العلوم والتكنولوجيا. ص 29-39 . doi : 10.5220/0007252300290039 . ISBN  978-989-758-350-6.
  9. ليمبانوبارب ، تاويثام؛ داتا، سوبانانت؛ تاورنبارشا، بياثيدا؛ تشينسوكسيرم، كريدتين (2021). " ACAD -Feedback: إطار عمل إلكتروني لتكليف الطلاب، وجمع وتحليل وتوزيع ملاحظاتهم الذاتية، وملاحظات الأقران، وملاحظات المدربين، وملاحظات المجموعات" . مجلة التعليم الكيميائي . 98 (9): 3038-3044 . doi : 10.1021/acs.jchemed.1c00424 .
  10. ↑ ميلر، أليس؛ بار، ماثيو؛ كافانا، ويليام؛ فالكوف، إيفايلو؛ بيرتشيس، هيلين سي (2021). "جداول تخصيص مجموعات التقسيم ومشكلة لاعب الغولف الاجتماعي مع أحجام المجموعات المتجاورة" . التناظر . 13 (13). doi : 10.3390/sym13010013 .
  11. ↑ لامبرز، رويل؛ روثويزن، لوران؛ سبيكسما، فريتس سي آر (2021). "مشكلة لاعب الغولف الاجتماعي المتنقل: حالة دوري الأمم للكرة الطائرة". في ستوكي، بيتر جيه (محرر). تكامل البرمجة المقيدة والذكاء الاصطناعي وبحوث العمليات: المؤتمر الدولي الثامن عشر، CPAIOR 2021، فيينا، النمسا، 5-8 يوليو 2021، وقائع المؤتمر . سبرينغر. ص 149-162 . doi : 10.1007/978-3-030-78230-6_10 . ISBN  978-3-030-78230-6.