خوارزمية لمباراة شركاء المفضل في مجموعات من ثلاثة

Question

ما هو خوارزمية جيدة لحل هذه المشكلة؟

ولدي ثلاث مجموعات من الناس - مجموعة A، B مجموعة، ومجموعة C. هناك نفس العدد من الناس في كل مجموعة. أنها تمتلك كل قائمة من الناس في المجموعات الأخرى انهم على استعداد للعمل مع. أريد أن مجموعة كل هؤلاء الناس معا في مجموعات من 3 (واحد من A، B واحد من واحد من C) بحيث كل فرد في مجموعة يريد أن يعمل مع الآخرين في جماعتهم.

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

ونقطة أخيرة: الناس يتفقون على الذين يريدون العمل مع (إذا كان الشخص العاشر يريد العمل مع شخص ذ، ثم ذ يريد أيضا للعمل مع x). إذا كنت ويمكن أيضا أن تعطي-O كبيرا من وقت تشغيل الخوارزمية الخاصة بك، سيكون ذلك رائعا!

Answer 1

وهذا هو مثل مشكلة الزواج مستقرة، ولكن مع 3 أحزاب بدلا من اثنين.

وإلقاء نظرة على حلول فعالة لمشكلة السابق (مطابقة الرسم البياني ثنائية partite) وتكييفها وفقا لاحتياجاتك.

http://en.wikipedia.org/wiki/Stable_marriage_problem

واحد التكيف يمكن أن يكون لأول بناء العمل أزواج من مجموعة A و B فقط. ثم يجب أن يقترن عامل من مجموعة C كل هذه الأزواج. السماح للأزواج يفضلون فقط العمال خلال اتفاق بين أعضاء الزوج على (نظرا قوائمها). لاحظ أن هذا سوف تعطي إلا الأمثل المحلية.

والحل الأمثل لK-partite مطابقة هو NP-من الصعب العثور على:

http://www.math.tau.ac .il / ~ صفرا / PapersAndTalks / k-DM.ps

وانظر هذه الورقة عن حل غير الأمثل لهذه المشكلة ك partite مطابقة:

<وأ href = "http://books.google.com/books؟id=wqs31L1MF4IC&pg=PA309&lpg=PA309&dq=k-partite+matching&source=bl&ots=kgBuvi7ym_&sig=j3Y-nyo51y8qp0-HwToyUlkao4A&hl=de&sa=X&oi=book_result&resnum= 1 و ط = نتيجة "يختلط =" noreferrer "> http://books.google.com/books؟id=wqs31L1MF4IC&pg=PA309&lpg=PA309&dq=k-partite+matching&source=bl&ots=kgBuvi7ym_&sig=j3Y-nyo51y8qp0-HwToyUlkao4A&hl=de&sa=X&oi= book_result وresnum = 1 & ط = يؤدي

وأنا متأكد من أنك يمكن أن تجد الآخرين على جوجل نفسك الآن بعد أن تعرف المصطلحات للبحث عنها. أنا لا أعرف إذا كان هناك خوارزمية فعالة إعطاء الحل الأمثل لك = 3.

Answer 2

وهذا يختلف عن امتداد لمشكلة الزواج مستقرة، منذ ذلك الحين وأنا أفهم سؤال OP، والناس في كل مجموعة لا تملك قائمة مرتبة من الذين يريدون العمل مع على الأقل أكثر من. انها علاقة ثنائية (إن شاء / يست على استعداد).

ويمكن أن تصاغ هذه باعتبارها مشكلة البرمجة صحيح يمكن حلها بسرعة. أعطي الصيغة الرياضية للمشكلة أدناه؛ يمكنك استخدام حزمة مثل glpk أو AMPL / CPLEX لمعالجة البيانات.

وتحديد المصفوفات التالية:

وM1 = |A| x |B| المصفوفة، حيث

وM1(a,b) = 1 إذا كان (عضو معين من A) هو على استعداد للعمل مع ب (نظرا عضو B)، و 0 خلاف ذلك

ومصفوفة M2 = |A| x |C|، حيث M2(a,c) = 1 إذا كان (عضو معين من A) هو على استعداد للعمل مع ج (عضو معين من C)، و 0 خلاف ذلك

وM2 = |B| x |C| المصفوفة، حيث

وإذا M3(b,c) = 1 ب (نظرا عضو B) مستعدة للعمل مع ج (عضو معين من C)، و 0 خلاف ذلك

والآن تحديد مصفوفة جديدة سوف نستخدم لتعظيم دينا:

وX = |A| x |B| x |C| المصفوفة، حيث

وX(a,b,c) = 1 إذا جعلنا أ، ب، ج والعمل معا.

والآن، وتحديد لدينا دالة الهدف:

و// تعظيم عدد من المجموعات

وتعظيم Sum[(all a, all b, all c) X(a,b,c)]

وتخضع لقيود التالية:

// لضمان أن لا أحد يحصل على وضعها في مجموعتين

لجميع القيم من: Sum[(all j, k) X(a, j, k)] <= 1

لجميع قيم ب: Sum[(all i, k) X(i, b, k)] <= 1

لجميع قيم ج: Sum[(all i, j) X(i, j, c)] <= 1

// لضمان أن جميع المجموعات تتكون من الأفراد متوافق

لجميع أ، ب، ج: X(a,b,c) <= M1(a,b)/3 + M2(a,c)/3 + M3(b,c)/3

Answer 3

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

Answer 4

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

وبدلا من ذلك، أي ما يعادل القضاء أعلاه، تشكيل قائمة بجميع ثلاثيات الممكنة والعمل من ذلك بدلا من ذلك.

Answer 5

وأنا واجهت مشكلة مماثلة، ومجرد كتب السيناريو الذي الغاشمة القوات ذلك ... HTTP: // الهامور. owoga.com/

وكانت أفكاري الأولية: لمجموعة أكبر التي كانت كبيرة جدا إلى القوة الغاشمة، ونوع من الخوارزمية الجينية؟ جعل N مرات عشوائي مقايضة M. يسجل كل الترتيبات الجديدة من قبل بعض وظيفة '' السعادة '. اتخاذ أفضل قليل، وتولد، وتكرار.

لمجموعات صغيرة انتهى بي الأمر الحصول على نتائج أفضل من خلال حلقات على مجموعات قليلة، والعثور على "أفضل" مبادلة (واحد التي أنتجت أعلى الشامل '' السعادة 'ربح)، مما يجعل ذلك، ثم تكرار.