NP-اكتمال البرنامج الخطي عدد صحيح

Question

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

لدينا $ i \ ldots j $ المتاجر و $ i \ ldots n $ الأماكن المحتملةبناء مستودع جديد.تكاليف بناء مستودع جديد هي $ c_j $ .بين كل متجر ومستودع هو طريق التكلفة $ d_ {i، j} $ .يحتاج كل متجر إلى توصيله لمستودع واحد على الأقل.

مشكلة القرار هي: هل هناك مجموعة من المستودعات والمسارات بحيث يكون المبلغ أصغر من رقم معين $ K $ .

Answer 1

هذا هو الكلاسيكية مشكلة موقع المنشأة . تشير مقالة Wikipedia إلى أن صلابة NP يمكن إثباتها عن طريق التخفيض من Set Cover .

---

منذ أن أعلن Asker الآن أنه قد وجد حلا عن طريق تقليل قمة الرأس ، سأذهب إلى الأمام والكشف عن التخفيض من Set Cover :

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

يتم استخدام قيمة $ K $ لتحويل مشكلة التحسين (تقليل مجموعات / التكلفة) في مشكلة في القرار (هل هناك حل بدون أكثر من $ K $ مجموعات / التكلفة؟). سيكون $ k $ من مثيل الغلاف المحدد سيكون هو نفسه $ K $ في مشكلة المرفق مثيل إذا سمح لك بتعيين القيم "الصغيرة بشكل تعسفي" إلى 0 - وإلا فقد تضطر إلى إعاقة القيمة من قبل بعض المبلغ، ولكن أقل من 1 طالما كنت تختار الأوزان "الصغيرة بشكل تعسفي" لتكون صغيرة بما فيه الكفاية. تحتاج فقط إلى إجمالي كلفة لكل تكلفة "صغيرة بشكل تعسفي" أقل من 1، وكل تكلفة "كبيرة تعسفية" أكبر من مجموع تكاليف جميع المستودعات وجميع الطرق "الصغيرة التعسفية".

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