الأمثل للخوارزمية الجشع

Question

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

على سبيل المثال لديك مجموعة من الأرقام $ \ mathcal {m}={1،2،3،4 \} $ وتريد تصميمخوارزمية للحصول على الحد الأدنى لعدد الأعداد الصحيحة المطلوبة للحصول على مجموع 5. في هذه الحالة، $ 1،4 $ "span class=" حاوية الرياضيات "> 2 دولار3 $ يمكن أن تنتج 5 وكلاهما حلول مثالية لأن الحد الأدنى المطلوب هو اثنين.

كيفية إثبات الفتحة في الخوارزمية؟

حاولت من خلال التناقض افتراض أن هناك الحل الأمثل $ p ^ * $ وخلع الخوارزمية لا تنتج الحل الأمثل $ p $ حتى $ p \ neq p ^ * $ .لكنني لا أعرف كيفية مواصلة الحجة.

Answer 1

هذا هو تغيير مشكلة تغيير .بالنسبة لبعض المجموعات من الطوائف (مثل صلاحيات بعض الأساس $ B $ ، العملات المعدنية الأمريكية، أو تقريبا جميع أنظمة العملات المعدنية في العالم) تعطي الخوارزمية الجشع الحد الأدنى من عددعملات معدنية.القضية العامة هي NP-Complete، وهو الحل العملي يتطلب البرمجة الديناميكية (انظر مقالة Wikipedia التي أحببتها).هناك خوارزمية زمنية متعددة الحدود للتحقق مما إذا كانت مجموعة معينة من الطوائف تجعل الخوارزمية الجشعة الأمثل أم لا، راجع

Answer 2

إذا كانت الخوارزمية الجشعة ليست دائما الأمثل، فستكون مثالا كافيا دليلا كافيا على هذا.

في هذه الحالة، تأخذ $ \ mathcal {m}={1،2،4،5،6 \} $ .ثم للحصول على مجموع $ 9 $ تنتج الخوارزمية الجشع 6 دولارات + 2 + 1 $ ولكن هذا ليس الأمثللأن $ 5 + 4 $ لديه أقل من Summands.

Answer 3

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

دع تعيين $ S $ يكون الحل الأمثل لبعض المشاكل ويعطي خوارزمية الجشع لدينا مجموعة $ p $ < / span>. إذا كان كلا $ P $ و $ S $ هي نفسها يتم بعد ذلك. افترض أن كلا $ p $ و $ S $ مختلفة، في هذه الحالة سوف تكون الخوارزمية الجشع اختيار العنصر في الخطوة الوسيطة (الحل المحلي) الذي هو أقل الأمثل مما أدى إلى $ p $ بدلا من مجموعة الأمثل $ S $ < / span>. ولكن وفقا للخوارزمية الجشع، نختار دائما الحل الأمثل المحلي. وبالتالي، يتم إثبات الحجة بواسطة دليل على التناقض.