مرجع
آخر الزيارات

مشكلة الإقران المتكافئ

879 كلمة•0 مشاهدة•🗒️ منذ 15 يوماً
باختصار: يهدف الإقران الأمثل إلي المزاوجة بين عناصر متساوية العدد منتمية لفصيلتين. في هذه المقالة 10 أقسام: «نتاج الخوارزمية»، «أعد لطالما تواجد رجل ج غير مرتبطين{» و«مثال» وغيرها.
المحتويات
  1. نتاج الخوارزمية
  2. أعد لطالما تواجد رجل ج غير مرتبطين{
  3. مثال
  4. ط: ج، س، د
  5. يتم المقارنة للعدد الكلي للرجال والنساء
  6. تكون تلك الزيجات مستقرة
  7. حل المشكلة
  8. http://kuznets.fas.harvard.edu/~aroth/alroth.html#NRMP
  9. تطبيقات مشابهة
  10. دالة الإقران الأمثل{
مشكلة الإقران المتكافئ

على سبيل التعريف، يهدف الإقران الأمثل إلي المزاوجة بين عناصر متساوية العدد منتمية لفصيلتين. يقوم كل عنصر س منتمي للنوع الأول بسرد العناصر المنتمية للنوع الثانى كلها بأفضلية اقترانه بها، وفي النهاية يتكون الزوجان (س، ص). يعد هذا الاقتران هو الأمثل في أي من الحالتين التاليتين:1- ألا يفضل العنصر س عنصراً آخر من النوعية الأخرى أكثر ممن اقترن به.2- ألا يفضل ص عنصرا آخر من النوعية الأولى عن هذا الذي اقترن به. ونتناول فيما يلي مزيدًا من التفاصيل.

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

نتاج الخوارزمية

هذه الخوارزمية تضمن كلٍ من:

أعد لطالما تواجد رجل ج غير مرتبطين{

  • م: المرأة ذات أعلى أفضلية بالنسبة ل«ج» ولم يتقدم لها بعد
  • إذا لم تكن المرأة م مرتبطة، يرتبط (م، ج) بشكل مؤقت
  • ّإذا كانت المرأة م مرتبطة ب«د»:
  • إذا فضّلت المرأة م الرجل ج عن د، يرتبط (م، ج) ويصبح الرجل د غير مرتبط
  • إذا لم تُفَضِّل المرأة م الرجل ج عن د، يظل (م، د) مرتبطين}
  • }

مثال

  • أ = {ج، د، س}، وب = {و، ز، ط}
  • يُعرف كل فرد ترتيب أفضلية كل الأفراد من القائمة بالنسبة له:
  • ج: و، ز، ط
  • د: ز، و، ط
  • س: و، ط، ز
  • و: س، ج، د
  • ز: ج، س، د

ط: ج، س، د

  • أول تكرار: يرتبط كلٍ من (س، و) و (د، ز) وترفض «و» «ج»
  • ثانى تكرار: يرتبط (ج، ز) ويصبح «د» غير مرتبط مرة ثانية
  • ثالث تكرار: يتقدم «د» ل «و» ولكنها تظل مع «س» حيث أنه أكثر من «د» أفضلية
  • رابع تكرار: يرتبط (د، ط)

يتم المقارنة للعدد الكلي للرجال والنساء

كذلك، حيث انه في النهاية، لا يتبقى فرد دون اقتران، حيث أن الرجل سيكون قد تقدم لكل النساء في حالة الضرورة (تم رفضه من ن-1 من النساء أو بعدما اقترن بامرأة فضلت آخر عليه)

تكون تلك الزيجات مستقرة

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

وفي السياق ذاته، و هذا ينفى احتمالية تفضيل أي منهما للآخر بعد الارتباط بآخرين.

الخوارزمية

وفي السياق ذاته، بفرض أنه يوجد فردين في المجموعة: مريم وعلىّ كلٍ منهما مرتبط بشخص ما. تضمن طريقة جيل-شابلى أنه بانتهاء الدورات، لن يفضل علىّ مريم أو تفضل مريم علىّ عن قرنائهم الحاليين.

حل المشكلة

علاوةً على ذلك، و تعد هعملية الإقران تلك من العمليات معقدة حسابياً حيث انها تتكون من عدد من العمليات قد يصل إلى مربع عدد الرجال/النساء، وبذا برمز O الكبير تكون العملية O(ن^2)

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

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

http://kuznets.fas.harvard.edu/~aroth/alroth.html#NRMP

  • http://www.dcs.gla.ac.uk/research/algorithms/stable/EGSapplet/EGS.html
  • Gale–Shapley JavaScript Demonstration
  • SMP Lecture Notes

تطبيقات مشابهة

Interactive Flash Demonstration of SMP

روابط خارجية

وفي هذا السياق، مشكلة قرناء السكن: تشبه مشكلة الإقران الأمثل لكنها تختلف عنها حيث يقبع كل الأفراد في فصيلة واحدة بدلا من تكوُّن فصيلتين متساويين في العدد.

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

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

دالة الإقران الأمثل{

من جهة ثانية، تُعَرَّف القائمتان أ تضم جميع الرجال، وب تضم جميع النساء كغير مرتبطين

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.