بن التعبئة مع الكائنات المتداخلة

Question

لدي بعض الصناديق مع قدرات مختلفة وبعض الكائنات بحجم محدد.الهدف هو حزمة هذه الكائنات في الصناديق.حتى الآن هو مشابه لمشكلة بن التعبئة.لكن تطور هو أن كل كائن لديه تداخل جزئي مع آخر.لذلك في حين أن الكائن 1 و 2 قام بأحجام S1 و S2، عندما أضعها في نفس BIN، فإن مساحة مليئة أقل من S1 + S2.من المفترض أن أعرف أن هذه القيمة المتداخلة لكل زوج من الكائنات، هل هناك أي خوارزمية تقريبية مثل تلك الخاصة بالتعبئة الأصلية لحزم هذه المشكلة أيضا؟

Answer 1

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

هذه الطريقة مقدمة في مايكل سنديلار، راميش ك. سيتارامان، براشانت ي. Shenoy: خوارزميات تبادل الوكالة للآلات الافتراضية.سبا 2011: 367-378 .

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

Answer 2

الخوارزمية الوحيدة التي أعتقد أنها ستعمل العمل هي إجراءات تقليم لا تنسجم مع الصناديق واستخدام صندوق آخر.لا أقصد خوارزمية تناسب أولا ولكن الانتظار لفترة من الوقت ثم استخدام صناديق جديدة للعناصر.في الواقع، يمكنك استخدام صندوق آخر فقط؟إنه نهج عملي.أعني أنه يمكنك أن تنمو بن إلى اليسار أو إلى اليمين مثل في هذا المثال: http://codeincomplete.com/postssournico1/5/7/bin_packing/ .