مشكلة NP كاملة ممكن؟

Question

أود فقط أن أحصل على شخص ما للتحقق مما إذا كانت المشكلة التالية هي NP-Complete أو إذا كان هناك حلا أفضل / أسهل له من فحص الجمع بين القوة الغاشمة البسيطة.

لدينا مشكلة من مشكلة تخصيص الموارد في برنامجنا، وسأشرح ذلك بمثال.

دعنا نقول أننا نحتاج إلى 4 أشخاص في العمل خلال اليوم التحول. هذا الرقم، وحقيقة أنه "تحول يوم" يتم تسجيله في قاعدة البيانات الخاصة بنا.

ومع ذلك، لا نطلب أي شخص فقط ملء هذه المواقع، هناك بعض المتطلبات التي يجب ملؤها من أجل تناسب الفاتورة.

من بين 4 سنوات، دعنا نقول 2 منهم يجب أن يكون ممرضة، و 1 منهم يجب أن يكونوا أطباء.

أحد الأطباء يجب أن يعمل أيضا كجزء من فريق معين.

لذلك لدينا هذه المجموعة من المعلومات:

يوم التحول: 4
1 طبيب
1 طبيب، تحتاج إلى العمل في الفريق أ
1 ممرضة

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

على سبيل المثال، دعنا نقول أننا اختيار جيمس وجون وأورسولا وماري للعمل، حيث جيمس وأورسولا أطباء، جون وماري ممرضات.

Ursula يعمل أيضا في الفريق A.

الآن، اعتمادا على النظام الذي نحاول تناسب الفاتورة، قد ينتهي بنا الأمر إلى استنتاج أن لدينا الأشخاص المناسبين، أم لا، ما لم نبدأ في تجربة مجموعات مختلفة.

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

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

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

هل هذا هو الحل الوحيد، هل يمكن لأي شخص أن يفكر في واحد أفضل؟

---

يحرر: بعض التوضيح.

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

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

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

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

هذا هو السبب في أنني أحب stackoverflow :)

Answer 1

ما لديك هناك مشكلة الارتياح القيد; ؛ علاقتهم إلى NP مثيرة للاهتمام، لأنها عادة NP ولكن في كثير من الأحيان لا np-complete، أي أنها تسقط إلى حلول زمنية متعددة الحدود.

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

Answer 2

انها تبدو وكأنها لديك مشكلة الارتياح القيد.

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

ماذا يحدث إذا لم يكن أحد يناسب المعايير؟

Answer 3

ما تصفه هو "مشكلة زميل الغرفة" هو موضح برفق في هذه الأطروحة.

تحمل معي، أنا أبحث عن روابط أفضل.

تعديل

هنا كثيفة أخرى إلى حد ما فرضية.

Answer 4

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

Answer 5

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

Answer 6

سأترك النظرية للآخرين، لأن ذكائي الرياضي ليس رائعا للغاية، ولكن قد تجد أداة مثل cassowary / cassowary.net أو nsolver مفيدة لتمثيل مشكلتك بشكل مصحي بمثابة مشكلة رضاء القيود ثم حل القيود.

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

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

Answer 7

يبدو لي مثل لديك مشاكل منفصلة ستكون أسهل بكثير لحلها:

- حدد طبيب واحد من فريق A - حدد طبيبا آخر من أي فريق - حدد ممرضين

لذلك لديك ثلاث مشاكل مستقلة.

أي توضيح، هل يجب أن يكون لديك طبيبين (واحد من الفريق المحدد) وممرضين، أو طبيب واحد من الفريق المحدد، وممرضان، وواحد آخر يمكن أن يكون إما طبيبة أو ممرضة؟

Answer 8

بعض الأسئلة:

1. هو الهدف لإرضاء القيود بالضبط, ، أو فقط تقريبا (ولكن قدر الإمكان)؟
2. هل يمكن أن يكون الشخص عضوا في العديد من الفرق؟
3. ما هي كل القيود الممكنة؟ (على سبيل المثال، هل يمكن أن نحتاج إلى طبيب عضو في عدة فرق؟)

إذا كنت ترغب في تلبية القيود بالضبط, ، ثم أود أن أطلب القيود بقلق بالضيق، أي أن تلك الأكثر صعوبة لتحقيقها (مثل الطبيب والفريق A في مثالك أعلاه) يجب التحقق منها أول!

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

Answer 9

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

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

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