مشكلة التنازل مع التكاليف

Question

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

تريد المشكلة منا أن نعرف ما إذا كان NP-hard أو متعدد الحدود ، إذا أثبتت NP-Hard كمل NP ، وإلا فإن الخوارزمية.

المشكلة هي على النحو التالى:

منتج موجود من وحدات N. هناك شركتان يمكنهما إنشاء كل وحدة ، مع بعض التكلفة (C_IJ ، I: رقم الوحدة ، J: رقم الشركة). إذا تم تصميم الوحدات النمطية A و B بواسطة شركات مختلفة ، فسيكون لديهم أيضًا تكلفة إضافية ، (P_AB). لا يجب أن تكون الوحدات A و B متتالية ، وتنطبق نفس التكلفة الإضافية على A و C أيضًا. كما هو متوقع ، تريد المشكلة منا أن نجد تعيين الوحدات النمطية للشركات بحيث تكون التكلفة الإجمالية الحد الأدنى.

أيه أفكار ؟

Answer 1

يمكن تقليله إلى مشكلة قطع دقيقة ، والتي يمكن العثور عليها بواسطة أي خوارزمية تدفق ماكس. إذن ما هي الشبكة؟ ستكون الوحدات النمطية هي قرارات الرسم البياني الخاص بنا وأيضًا نضيف مصدرين جديدتين ومغسلة. من المصدر نضيف حافة إلى كل وحدة I مع سعة CI1. وبالمثل من كل وحدة نضيف حافة لتغرق مع السعة CI2. وأيضًا لأي وحدات I و J نضيف Edge مع السعة PIJ (الموجهة إلى الرسم البياني وبالتالي سيكون هناك حوافان (IJ) و (JI)). من السهل أن نرى أن قيمة القطع الدقيقة هي حل المشكلة (الوحدات النمطية في جزء من القطع مع المصدر تعيين للشركة الثانية والوحدات النمطية للشركة الأولى)