مشكلة اللقاء

📅 آخر تحديث: ٢٨ يوليو ٢٠٢٦
✍️ نُشر في: ٢٨ يوليو ٢٠٢٦
الموسوعة الحرة

معضلة اللقاء هي معضلة منطقية، وعادة ما تُصاغ على النحو التالي:

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

إذا اختار كلاهما الانتظار، فلن يلتقيا أبدًا. أما إذا اختار كلاهما المشي، فهناك احتمالات لقائهما واحتمالات أخرى لعدم لقائهما. وإذا اختار أحدهما الانتظار والآخر المشي، فهناك يقين نظري بأنهما سيلتقيان في النهاية؛ ولكن عمليًا، قد يستغرق الأمر وقتًا طويلًا جدًا لضمان ذلك. إذن، السؤال المطروح هو: ما الاستراتيجيات التي ينبغي عليهما اتباعها لزيادة احتمالية لقائهما إلى أقصى حد؟

تُعرف أمثلة هذا النوع من المسائل بمسائل الالتقاء . وقد طُرحت هذه المسائل لأول مرة بشكل غير رسمي من قِبل ستيف ألبيرن عام 1976، [ 1 ] ثم قام بصياغة النسخة المستمرة منها عام 1995. [ 2 ] وقد أدى ذلك إلى العديد من الأبحاث الحديثة في مجال البحث عن الالتقاء. [ 3 ] حتى مسألة الالتقاء المتناظرة التي تُلعب في n موقعًا منفصلاً (والتي تُسمى أحيانًا مسألة الالتقاء في مقهى موزارت ) [ 4 ] تبين أنها بالغة الصعوبة، وفي عام 1990، افترض ريتشارد ويبر وإيدي أندرسون الاستراتيجية المثلى. [ 5 ] وفي عام 2012 ، أثبت ريتشارد ويبر صحة هذا الافتراض عندما n = 3. [ 6 ] وكانت هذه أول مسألة بحث عن الالتقاء متناظرة غير تافهة يتم حلها بالكامل. للمسألة المقابلة للالتقاء غير المتماثل حل أمثل بسيط: يبقى أحد اللاعبين في مكانه بينما يزور اللاعب الآخر تبديلاً عشوائياً للمواقع.

إلى جانب كونها مشاكل ذات أهمية نظرية، تشمل مشاكل الالتقاء مشاكل واقعية ذات تطبيقات في مجالات التزامن ، وتصميم أنظمة التشغيل ، وبحوث العمليات ، وحتى تخطيط عمليات البحث والإنقاذ .

مشكلة الالتقاء الحتمي

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

انظر أيضاً

مراجع

  1. ^ ستيف ألبيرن (1976)، ألعاب الغميضة ، ندوة، معهد فور هوهير ستوديان، فيينا، 26 يوليو.
  2. ↑ ألبيرن، ستيف (1995)، "مشكلة البحث عن نقطة الالتقاء"، مجلة SIAM للتحكم والتحسين ، 33 (3): 673-683 ، doi : 10.1137/S0363012993249195 ، MR 1327232 
  3. ↑ ألبيرن، ستيف ؛ غال، شموئيل (2003)، نظرية ألعاب البحث والالتقاء ، السلسلة الدولية في بحوث العمليات وعلوم الإدارة، المجلد 55، بوسطن، ماساتشوستس: دار نشر كلوير الأكاديمية، ISBN  0-7923-7468-1MR 2005053​ .
  4. ↑ ألبيرن، ستيف (2011)، "ألعاب البحث عن نقطة الالتقاء"، في كوكران، جيمس ج. (محرر)، موسوعة وايلي لبحوث العمليات وعلوم الإدارة ، وايلي، doi : 10.1002/9780470400531.eorms0720.
  5. ↑ أندرسون، إي جيه؛ ويبر، آر آر (1990)، "مشكلة الالتقاء في المواقع المنفصلة" ، مجلة الاحتمالات التطبيقية ، 27 (4): 839-851 ، doi : 10.2307/3214827 ، JSTOR 3214827 ، MR 1077533 ، S2CID 122587972   .
  6. ↑ ويبر، ريتشارد (2012)، "البحث الأمثل عن نقطة التقاء متناظرة في ثلاثة مواقع" (ملف PDF) ، رياضيات بحوث العمليات ، 37 (1): 111-122 ، doi : 10.1287/moor.1110.0528 ، MR 2891149 .
  7. ↑ تا-شما، أمنون؛ زويك، أوري (أبريل 2014). "اللقاءات الحتمية، والبحث عن الكنوز، وتسلسلات الاستكشاف الشاملة بقوة". معاملات ACM في الخوارزميات . 10 (3). 12. doi : 10.1145/2601068 . S2CID 10718957 .