طريقة سريعة للحصول على bitmask للتسليم إلى جميع الأجهزة

Question

لدي قائمة بالأجهزة وخلع القنوات التي يتم تشغيلها (يتم ترقيم القنوات 0..3). يمكن أن يكون هناك ما يصل إلى 256 جهاز.

فمثلا:

Device1: 1 0 0 1 (on channels 0, 3)
Device2: 0 1 1 0 (on channels 1, 2)
Device3: 1 1 0 0 (on channels 2, 3)

أحتاج إلى العثور على قناة من القنوات التي ستؤدي إلى استلام الرسالة من قبل جميع الأجهزة مع أقل من رسائل غير ضرورية ممكنة.

النتيجة الصحيحة bitmasks على سبيل المثال البيانات 1 0 1 0 (القناة 1 تقدم إلى الجهاز 2 والقناة 3 إلى الجهاز 1 و Device3) و 0 1 0 1 (تقدم القناة 0 إلى الجهاز 1 والقناة 2 إلى جهاز 2 و Device3) ، إما أن يكون أحدهما على ما يرام.

نتيجة bitmask 1 1 0 0 سيكون سيئًا لأن الجهاز 3 سيحصل على الرسالة مرتين.

Answer 1

نظرًا لأنه قد لا يكون هناك حل مثالي ولدينا فقط 16 إمكانيات للنتيجة ، فإنني سأستخدم فقط نهج القوة الغاشمة وأتكرر من خلال جميع الأقنعة الستة عشر الممكنة ، ومعرفة أي واحد (ق) هو/هو الأمثل (الحد الأدنى من الرسائل المتكررة ).

Answer 2

ألق نظرة على البحث عن البحث.

Answer 3

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

من الغريب أنه إذا كان لديك بالفعل 256 جهازًا ، فربما يتعين عليك إرسال جميع القنوات على أي حال.