الخوارزمية المجرية وعوامل متعددة

Question

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

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

• بعض الناس لا يمكنهم القيام إلا في الصباح، والبعض الآخر لا يمكنهم القيام إلا في فترة ما بعد الظهر؛
• يمكن لبعض الأشخاص الذهاب إلى أيام الاثنين والخميس فقط، بينما لا يستطيع أشخاص آخرون الذهاب في أغسطس أو ديسمبر؛
• يمكن لبعض الأشخاص الذهاب مرة واحدة فقط في الشهر، ويمكن لأشخاص آخرين الذهاب 4 مرات (وحتى الأشخاص الآخرين يتم منحهم "الأولوية" في هذه الإجراءات لأنهم أكثر خبرة ويمكنهم القيام بها 10 مرات في الشهر).

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

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

التكرار الأول

         | August 1st 2009
Person A | 1000
Person B | 500 *

التكرار الثاني

         | August 8th 2009
Person A | 1000 *
Person B | 1000 

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

ما رأيك وكيف ستفعل ذلك؟

Answer 1

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

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

قد يكون بعض المتطوعين لديك قادرين على القيام بأكثر من فتحة واحدة؛ويمكن تصميم ذلك من خلال تكرار تلك القمة المتطوعة عدة مرات.

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

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