هل هذه المشكلة np-hard؟

Question

أحاول التوصل إلى خوارزمية معقولة لهذه المشكلة:

دعنا نقول أن لديك مجموعة من الكرات. كل كرة لها لون واحد على الأقل ، ولكن يمكن أيضًا أن تكون متعددة الألوان. كل كرة لديها أيضا رقم عليها. هناك أيضًا مجموعة من الصناديق التي هي كل لون واحد فقط. الهدف هو زيادة مجموع الأرقام على الكرات في الصناديق ، والقواعد الوحيدة هي:

• من أجل وضع كرة في صندوق ، يجب أن يكون لها على الأقل لون المربع عليها
• يمكنك وضع كرة واحدة فقط في كل صندوق.

على سبيل المثال ، يمكنك وضع كرة زرقاء وخضراء في صندوق أزرق أو صندوق أخضر ، ولكن ليس في صندوق أحمر.

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

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

---

تحرير - إليك مثال بسيط:

كرات:

• 1 كرة حمراء - 5 نقاط
• 1 كرة زرقاء - 3 نقاط
• 1 كرة خضراء/حمراء - 2 نقطة
• 1 الكرة الخضراء/الزرقاء - 4 نقاط
• 1 كرة حمراء/زرقاء - نقطة واحدة

مربعات:

• 1 أحمر
• 1 الأزرق
• 1 أخضر

حل مثالي:

• الكرة الحمراء في صندوق أحمر
• الكرة الزرقاء في الصندوق الأزرق

• الكرة الخضراء/الزرقاء في صندوق أخضر

  القيمة الإجمالية: 12 نقطة (5 + 3 + 4)

Answer 1

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

يمكن حل خوارزمية المهمة في وقت O (n^3) ، حيث يكون n هنا الحد الأقصى لعدد الكرات أو الصناديق ، باستخدام ملف الخوارزمية المجرية. (راجع للشغل ، يجب أن أجعل إخلاء المسئولية الذي أذكره فقط الخوارزمية المجرية لأنها النتيجة النظرية التي أكون على دراية بها ويفترض أنها تجيب على السؤال في عنوان ما إذا كانت المشكلة الأصلية هي np-hard. ليس لدي أي فكرة سواء كانت أفضل خوارزمية لاستخدامها في الممارسة العملية.)

Answer 2

هل جربت Alg الجشع؟ فرز النقاط/القيمة والمكان في المربع إن أمكن. إذا كان هناك أي استثناءات ، فأنا في عداد المفقودين أن أراها.