لقاء في الوسط
Meet-in-the-middle - وسيلة للتحسين الحلول ، والتي تتمثل في تقسيم المشكلة الأصلية إلى نصفين ، وحل كل منهما على حدة ، ثم الحصول على حل للمشكلة الأصلية من خلال الجمع بين حلول النصفين.
وفقًا لذلك ، من المنطقي استخدام لقاء في الوسط في حالة استيفاء شرطين.
1) الوقت اللازم لحل نصف المشكلة أقل بشكل مقارب من الوقت لحل المشكلة برمتها.
2) من خلال حل نصف المشاكل ، يمكن للمرء الحصول على حلول للمشكلة الأصلية بأكملها ، وفي نفس الوقت ، أسرع بشكل مقارب من مجرد حل المشكلة برمتها.
نبسب ؛
مثال
لنفترض أن هناك أربع مصفوفات من الأعداد الصحيحة A و B و C و D . من الضروري تحديد رقم واحد بالضبط من كل مصفوفة بحيث يكون مجموع هذه الأرقام مساويًا للصفر. & nbsp؛ يمكنك استخدام حل ساذج ، وهو ببساطة تعداد جميع الخيارات الممكنة. سيعمل هذا مع O (n 4 ) .
ومع ذلك ، يمكننا استخدام Meet-in-the-middle .
لاحظ أن a + b + c + d = 0 يعادل (a + b) = - (c + d) .
دعنا نقسم المهمة إلى نصفين ، أي في النصف الأول سنستخدم فقط المصفوفات A و B ، وفي النصف الثاني فقط C و D .
دعنا نكرر جميع خيارات (a + b) الممكنة في النصف الأول ونخزن جميع القيم في جدول تجزئة ( unordered_map ، HashMap أو ما شابه). يعمل هذا في O (n 2 ) .
الآن سوف نكرر جميع الخيارات الممكنة (c + d) في النصف الثاني. عند التفكير في خيار معين ، سوف نتحقق مما إذا كانت هناك قيمة في جدول التجزئة مرتبطة بالمجموع الحالي للعلامة المعاكسة (ثم وجدنا مقلدين يصل مجموعهما إلى الصفر). يعمل هذا الجزء أيضًا في O (n 2 ) .
ليس لدينا هنا مرحلة منفصلة " دمج الإجابات " ؛ في أحدهما ، قمنا بهذا أثناء حل كل نصفين. معظم المهام سيكون لها وضع مماثل.
انتهى بنا المطاف بحل في O (n 2 ) باستخدام meet-in-the-middle .
من الجدير بالذكر أن Meet-in-the-middle يُستخدم غالبًا عند تحسين الحلول الأسية ، مما يؤثر بشكل كبير على وقت التشغيل.