خوارزمية لأداة التخطيط

Question

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

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

تحرير: نسيت أن أذكر، أن جميع المحادثات تأخذ نفس الوقت من الوقت.

شكرا!

Answer 1

أعتقد أنه من السهل جدا.

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

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

Answer 2

نهج واحد Woule DBE لتحديد المشكلة في لغة قيد التعريفية ثم السماح لها بحل المشكلة لك. آخر مرة قمت بها، لقد استخدمت كسوف, ، وهي لغة صغيرة ذات قسوة حيث تحدد مساحة المشكلات الخاصة بك عن طريق القيود، ثم تتيح لها العثور على قيم مسموح بها تلبي القيود.

على سبيل المثال، أعتقد أن لديك فئتين من القيود:

1. قد يكون لدى المعلم مؤتمر واحد فقط في وقت واحد
2. يجب أن يكون لدى جميع الطلاب في نفس الأسرة فتحات متتالية

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

Answer 3

هذه الأنواع تشعر وكأنها نوع من مشكلة "خوارزمية الظهر". تحتاج إلى تجميع أفراد الأسرة معا ثم ملء فتحات بشكل مناسب.

إذا كنت من Google "خوارزمية على ظهره"، فسترى ما يكفي من عمليات الكتابة لجعل رأسك تدور وأيضا بعض الحلول المرفيفة جيدة.

Answer 4

أعتقد أنه إذا كان يمكن تخفيض كل حديث إلى "الأنشطة" حيث يكون لكل نشاط وقت بداية ووقت النهاية، يمكنك استخدام خوارزمية اختيار النشاط التي تمت دراستها في علوم الكمبيوتر. يعتمد على نهج جشع ويمكن حله في O (ن) (حيث n هو عدد الأنشطة). يمكنك العثور على مزيد من المعلومات هنا. وبعد أنا متأكد من أنك ستحتاج إلى القيام بمعالجة مسبقة هنا لتكون قادرة على تقليل إصدار الأخ / الأخت كأنشطة من نفس النوع.