البنية التحتية الأمثل

Question

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

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

للتوضيح:

ينص تعريف CLRS للبنية التحتية المثالية على أن "المشكلة تظهر البنية التحتية المثالية إذا أي الحل الأمثل للمشكلة يحتوي في داخله على الحلول الأمثل للمشكلات الفرعية".

لماذا لا يكفي أن نقول إن "المشكلة تظهر البنية التحتية المثالية إذا بعض "الحل الأمثل للمشكلة يحتوي في داخله على الحلول الأمثل للمشاكل الفرعية"؟

Answer 1

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

اسمحوا أن تكون المشكلة و B تكون مشكلة الفرعية. هناك مشكلة فرعية واحدة فقط لأننا نستطيع الجمع بين المشاكل الفرعية المستقلة المتعددة في واحدة عبر منتج الديكور العلوي المعمم. يتكون الحد من وظيفتين: F، من مثيل إلى مثيل B، و H، من حل B إلى حل A. خاصية صحتها التي نحتاجها هي أنه لكل وظيفة G من كل مثيل B إلى محلول B-Solution الموافق (Oracle)، فإن التركيب H. ز. F هو وظيفة من كل حالة على حل الأمثل المقابلة. (إذا احتاج H إلى الوصول إلى المثال، فقم بتوسيع B بحيث تحتوي مثيلاتها على مثيل يجب نسخها حرفيا في حل B المقابل.)

لجعل وجهة نظرك، للحصول على مثيل معين ومحلول محسن، لا تحتاج إلى وجود أوراكل ز أن خط أنابيب H. ز. F تنتج هذا الحل من مثيل معين. (بمعنى آخر، H ضرور لا يلزم أن تكون سقفا.) من ناحية أخرى، يجب أن تكون H قادرة على التعامل مع كل محلول B الأمثل ممكن من G ل F.

استراتيجية مشتركة واحدة لضمان صحة H هي العثور على وظيفة "تحكي" ووظيفة K من حلول B-Solutions وطريقة "لصق" البنية التحتية، أي دليل على ذلك، بالنظر إلى حل X و B-Solution Y ليس أسوأ من K (X)، يوجد حل X 'ليس أسوأ من x بحيث k (x')= y. ثم H يمكن أن يتحسن على كل شيء في الصورة العكسية تحت ك من مدخلاتها. ليس من الضروري أن تنطبق الربط على جميع الحلول X، واحدة فقط واحدة مثالية.

Answer 2

في البرمجة الديناميكية، نقوم بتقسيم المشكلة إلى مشكلات فرعية أصغر، ونقوم ببعض المعالجة ونقدم إجابة لإجابة أكبر - تشبه إلى حد كبير نهج العودية (وليس من قبيل الصدفة).

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

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

فإذا علمنا أن بعض المشكلات الفرعية هي الحل الأمثل - فلن يكفي التأكد من أن استخدام هذه المشكلة الفرعية التي لدينا حل أمثل لها - هو بالفعل الذي نحتاجه للحصول على الحل الأمثل للمشكلة الأكبر.

---

قم بإلقاء نظرة على حقيبة الظهر على سبيل المثال، ودعنا نلقي نظرة على خطوة DP الخاصة بها:

f(x,i) = max(f(x-weight[i],i-1) +val[i], f(x,i-1))

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

إذا اخترنا f(x,i-1) في ال max() - ربما كان الاختيار الخاطئ.من خلال التأكد من أن لدينا الحل الأمثل لجميع المشاكل الفرعية، فإننا نتأكد من أن هذا لا يمكن أن يحدث.