الأنماط في البرمجة الديناميكية - 2

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

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

دعنا نحصل على dp [l] [r] - الإجابة المثلى لشريحة فرعية ذات مؤشرات من l إلى r. تعتمد إعادة حساب الديناميكيات بشكل كبير على المهمة ، ولكن هناك الأفكار العامة التالية:

1) انظر إلى العناصر المتطرفة l و r. إذا كانت تتطابق أو تكمل بطريقة أخرى ، فعلى الأرجح سيكون من الممكن تحديث قيمة dp [l] [r] عبر dp [l + 1] [r-1]. وإلا عبر dp [l] [r-1] أو dp [l + 1 [r].

2) يحدث غالبًا أن المقطع [l ؛ r] لا يمكن تمثيله من خلال بناء واحد. ثم من الضروري النظر في جميع الأقسام المحتملة من هذا الجزء الفرعي إلى جزأين ، أي التكرار على العنصر k من l إلى r-1 وإعادة حساب dp [l] [r] حتى dp [l] [k] و dp [ ك + 1] [ص]. في الأجزاء الفرعية الأصغر ، تم تصنيف هذه الأقسام أيضًا ، وبالتالي ، في الواقع ، يتم أخذ خيارات تقسيم الجزء الفرعي [l ؛ r] ليس فقط إلى جزأين ، ولكن إلى أي عدد منهم.
نبسب ؛

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

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

ستكون المعلمة الرئيسية عبارة عن قناع بت ، والذي سيُظهر العناصر التي تم تضمينها بالفعل في التقليب ، والتي لم يتم تضمينها. غالبًا ما يكون مطلوبًا أيضًا معلمة ثانية تشير إلى العنصر الذي تم تضمينه مؤخرًا.

غالبًا ما يمكن رؤية التباديل في سياق المسارات في الرسوم البيانية. وبناءً على ذلك ، دعونا ننظر في مثال كلاسيكي - مشكلة مسار هاميلتوني.
مسار هاميلتوني هو مسار بسيط يمر عبر كل رأس من الرسم البياني مرة واحدة بالضبط. يمكن تمثيله ببساطة على أنه تبديل للطول n ، حيث n هو عدد الرؤوس. سيشير الترتيب ضمن هذا التبديل إلى الترتيب الذي يتم فيه اجتياز الرؤوس في هذا المسار.

من أجل التحقق من وجود مسار هاميلتوني في الرسم البياني ، فلنبدأ ديناميكيات dp [القناع] [الأخير] - هل هناك مسار بسيط تجاوز الرؤوس المميزة بأخرى في القناع النقطي للقناع وانتهى به الأمر عند القمة الأخيرة.
ستكون القيم الأولية هي dp [2 ⁱ ] [i] = صحيح ، والباقي خطأ ، مما يعني أن هناك دائمًا مسارًا فارغًا يبدأ من أي من القمم.
بالحصول على القيمة صحيحة في dp [القناع] [الأخير] ، سنقوم بإجراء انتقالات للأمام ، بمعنى "توسيع المسار". وهذا يعني أننا سنبحث عن عدد القمم التي تم تمييزها بصفر في القناع (لم نقم بزيارتها بعد في الطريق) وفي نفس الوقت توجد حافة من الأخير إلى هذا الرأس (يجب أن يكون المسار يتم تمديده بواسطة حافة موجودة). وهذا يعني أننا نقوم بعمل dp [mask | 2 ^k ] [k] = true if dp [mask] [last] = true AND Mask & amp؛ 2 ^k = 0 (لم تتم زيارة الرأس k بعد) وهناك حافة أخيرة - & gt؛ ك.
في النهاية ، يوجد مسار هاميلتوني إذا كانت هناك قيمة حقيقية في dp لمعلمات كل قناع البت وأي قمة أخيرة.