تخصيص العديد من الطلاب إلى العديد من المدارس بناء على السعة

Question

قل لدي مجموعة من التعليمات (الإحداثيات). لدي أيضا مجموعة من الإحداثيات الوسطى من الأحياء (ن).

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

giveacodicetagpre.

أعرف عدد المواقع المتوفرة في كل مدرسة، والتنسيق يجري:

giveacodicetagpre.

هدفي هو مطابقة أكبر عدد ممكن من الطلاب في المدرسة داخل دائرة نصف قطرها معينة. من الممكن (من المحتمل للغاية) أنه في حساباتي، سيكون بعض الطلاب أقل من المدرسة.

ما أريد: تحديد الحي الذي لديه أطفال أقل من المدرسة وعدد.

خطتي الحالية:

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

كمثال:

• قل أنك تحصل على الطلب التالي:

  النظام= [(الأحياء_2، School_7، المسافة 1)، (الحياء_5، School_2، المسافة 2)، (حي_2، School_2، المسافة 3)، (حي_2، School_3، المسافة 4) ...]

ثم، School_7 يستقبل الأطفال من الحي_2. لا يمكن اتخاذ جميع الأطفال من أحياء_2 في School_7.

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

بعد ذلك، لا يزال الجوار_2 لديه طلاب إرسال، وحاول ذلك إرسالها إلى المدرسة_2. المدرسة الابتدائية والثانوية، لا توجد مشكلة، يتم إرسالها الآن. لكن المدرسة المتوسطة ممتلئة.

ثم ننتقل إلى الاقتران التالي، ويحصل School_3 على طلاب المدارس المتوسطة المتبقية من الأحياء_2. لاحظ أنه إذا كان المسافة 4 أعلى من دائرة نصف قطرها الحد، فقد تم تصنيف طلاب المدارس المتوسطة على أنها أقل في المدرسة، حيث لا تتوفر أي أزواج أخرى.

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

1) هل خوارزمية صحيحة؟

2) ما هو اسم هذه المشكلة بالضبط؟ لقد صادفت العديد من مشاكل تخصيص النقاط المتعددة، أو "التحقق من صحة" جزء من مشكلة موقع المنشأة، ولكن ليس هذا البديل بالذات لسبب ما (مهارات البحث المسؤولة المحتملة)

3) كيف يمكنني جعل هذا الكفاءة، أم أنها معقولة جدا بهذه الطريقة؟ (الكفاءة ليست مصدر قلقي الأساسي، ولكن الإصلاحات السهلة هي موضع ترحيب)

4) هل لدي خيارات أخرى إلى جانب الفرز عن بعد؟ من الناحية الفنية، في حالتي، لا يهم المسافة الكثير لإعطاء الأولوية، فهو أكثر نشاطا عشوائيا (أو يجب أن أقول عرضا) على سبيل المثال وقت التطبيق المستلم (بيانات غير معروفة). لذا فإن طريقتي ستظهر تخصيصا محرجا بنسبة 100٪ لمنطقة قريبة جدا من المدرسة AMD بمجموعة من الأطفال أقل من المدرسة في أحياء فارير، ولكن هذا قد لا يكون (ليس) صحيحا في الحياة الحقيقية.

Answer 1

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

في حالتك، يمكنك حلها باستخدام أقصى تدفق .سوف اتركها من التفاصيل.