Get best of the week

كتاب "الخوارزمية المثالية. الخوارزميات الجشعة والبرمجة الديناميكية »

صورةمرحبا ، هابروجيتلي! في الكتاب الجديد ، يتحدث Tim Rafgarden عن الخوارزميات الجشعة (مشكلة التخطيط ، والحد الأدنى من الأشجار الممتدة ، والتكتل ، ورموز هوفمان) والبرمجة الديناميكية (مشكلة حقيبة الظهر ، محاذاة التسلسل ، أقصر المسارات ، أشجار البحث المثلى). يقدم هذا المنشور مقتطفًا بعنوان "تطوير خوارزمية جشعة."

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

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

13.3.1. حالتين خاصتين


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

(1) , ?
(2) , ?
) ;
) ;
) ;
) ;
( . 13.3.3.)

13.3.2.


بشكل عام ، قد يكون للعمل أوزان مختلفة وأطوال مختلفة. كلما كانت قاعدتان أساسيتان - لتفضيل العمل الأقصر والعمل بأوزان أعلى - محظوظين لبعض الوظائف التي تتزامن ، فنحن نعرف أيهما نخطط أولاً (أقصر مع الأوزان الأعلى). ولكن ماذا لو أعطت هاتان القاعدتان نصيحة متضاربة؟ ماذا يجب أن نفعل مع عمل واحد قصير الوزن وخفيف الوزن؟

ما هي أبسط خوارزمية الجشع التي ستعمل كما ينبغي؟ يحتوي كل عمل على معلمتين ، ويجب أن تنظر الخوارزمية إلى كليهما. سيكون الخيار الأفضل هو تطوير صيغة تجمع طول ووزن كل عمل في علامة واحدة (مساهمة) ، بحيث يتم ضمان عمل التخطيط من أعلى إلى أدنى علامة لتقليل كمية تواريخ الانتهاء المرجحة. إذا وجدت مثل هذه الصيغة ، فعندئذٍ من حالتنا المعينة ، يستتبع ذلك أنه يجب أن يكون لها خاصيتان: (1) ترك الطول ثابتًا ، يجب أن يزيد بوزن العمل ؛ (ii) ترك الوزن ثابتًا ، يجب أن ينقص من طول العمل (تذكر أنه كلما كانت العلامة أعلى ، كان ذلك أفضل). اقضِ دقيقة في العصف الذهني للعديد من الصيغ التي تحتوي على هاتين الخاصيتين.

صورة

ربما تكون أبسط وظيفة ، والتي تزيد في الوزن وتنقص في الطول ، هي الفرق بينهما:
الاقتراح رقم 1 لعلامة العمل. صورة

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

الاقتراح رقم 2 صورة

لتمييز العمل. تؤدي هاتان الوظيفتان لحساب العلامة إلى خوارزميتين جشعين مختلفين.
GREEDYDIFF GREED DIFFERENCE

خطة العمل بترتيب تنازلي صورة
(كسر تزامن القيم بشكل تعسفي).
GREEDYRATIO

صورة
( ).

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

صورة

العمل الأول له نسبة أكبر صورةولكن فرق أكبر (–2 مقابل –1). وهكذا ، GreedyDiffتخطط الخوارزمية للعمل الثاني أولاً ، بينما GreedyRatioتخطط الخوارزمية عكس ذلك.
تمرين 13.3

ما هو مجموع تواريخ الانتهاء المرجحة في جداول استخلاصه من قبل GreedyDiffو الخوارزميات، على التوالي GreedyRatio؟

أ) 22 و 23
ب) 23 و 22
ج) 17 و 17
د) 17 و 11
(للحصول على حل وتفسير ، انظر القسم 13.3.3.)

لقد تقدمنا ​​إلى الأمام من خلال استبعاد الخوارزمية GreedyDiffمن مزيد من النظر. ومع ذلك ، فإن نتيجة التمرين 13.3 لا تؤدي مباشرة إلى حقيقة أن الخوارزمية GreedyRatioستكون دائمًا مثالية. بقدر ما نعلم ، هناك حالات أخرى عندما تنتج هذه الخوارزمية جدولًا غير مثالي. يجب أن تكون دائمًا متشككًا في خوارزمية لا يرافقها دليل على صحتها ، حتى لو كانت هذه الخوارزمية تفعل الشيء الصحيح في العديد من حالات الاختبار ومتشككة للغاية في الخوارزميات الجشعة.

في حالتنا ، خوارزمية GreedyRatio، في الواقع ، مضمونة لتقليل كمية تواريخ الانتهاء المرجحة.

نظرية 13.1 (صحة الخوارزمية GreedyRatio) . لكل مجموعة من أوزان العمل الإيجابيةصورةوأطوال الوظائف الإيجابية ، تعرض صورةالخوارزمية GreedyRatioجدولًا بأصغر عدد ممكن من تواريخ الانتهاء المرجحة.

هذا البيان المنطقي ليس واضحًا ، ولا يجب أن تثق به دون تلقي أدلة. وفقًا للموضوع الثالث للنموذج الجشع (القسم 13.1.2) ، يتناول هذا الدليل القسم التالي بأكمله.
, . .

. — , ( ). — , , , . «» ( ) , .

الموضوع المتبقي من نموذج الجشع هو بساطة تحليل وقت التشغيل (القسم 13.1.2). هنا بالطبع. تقوم خوارزمية GreedyRatio بفرز الوظائف حسب العلاقة فقط ، والتي تستغرق وقت O (n log n) ، حيث n هو عدد الوظائف في الإدخال (انظر الحاشية 1 في الصفحة 24).

13.3.3. حلول التمرين 13.2-13.3


حل التمرين 13.2

الإجابة الصحيحة هي: (أ) . أولاً ، افترض أن جميع الوظائف n لها نفس الطول ، على سبيل المثال 1. ثم كل جدول زمني له نفس مجموعة المواعيد النهائية - {1 ، 2 ، 3 ، ... ، n} - والسؤال الوحيد هو نوع الوظيفة التي تحصل عليها تاريخ الانتهاء وما هو الموعد النهائي. إن معاني الكلمات الخاصة بأوزان العمل تعني بالتأكيد أن العمل مع زيادة الوزن يجب أن يحصل على أوقات إنجاز أقصر ، وهذا صحيح. على سبيل المثال ، لا ترغب في التخطيط للعمل بوزن يبلغ الثلث (مع الموعد النهائي 3) والعمل بوزن 20 خامس (مع الموعد النهائي 5) ؛ سيكون من الأفضل تغيير موضع هذين العملين ، مما يقلل من مجموع المواعيد النهائية المرجحة بمقدار 20 (كما ترى بنفسك).

الحالة الثانية ، حيث يكون لجميع الأعمال نفس الوزن ، أرق قليلاً. هنا تريد إعطاء الأفضلية للعمل الأقصر. على سبيل المثال ، ضع في اعتبارك وظيفتين من وزن الوحدة بطول 1 و 2. إذا كنت تخطط لأول مرة عمل أقصر ، فستكون المواعيد النهائية للإكمال 1 و 3 بمجموع 4. في الترتيب العكسي ، ستكون المواعيد النهائية 2 و 3 مع أسوأ النتائج 5. بشكل عام ، المخطط يساهم العمل أولاً في وقت الانتهاء من جميع الأعمال ، حيث يجب أن ينتظر كل العمل حتى الانتهاء من العمل الأول. كل الأشياء متساوية ، التخطيط لأقصر عمل أولاً يقلل من هذا التأثير السلبي. تساهم المهمة الثانية في جميع تواريخ الانتهاء باستثناء المهمة الأولى ، لذا يجب جدولة ثاني أقصر مهمة في اليوم التالي ، إلخ.

التمرين 13.3 الحل

الجواب الصحيح هو ب). GreedyDiffتخطط الخوارزمية لوظيفة ثانية أولاً. الموعد النهائي لإكمال هذا العمل هو صورةالموعد النهائي لإكمال عمل آخر هو صورةمجموع المواعيد النهائية المرجحة للانتهاء ثم

صورة

GreedyRatioتخطط الخوارزمية للعمل الأول أولاً ، مما يؤدي إلى المواعيد النهائية صورة
ومجموع المواعيد النهائية المرجحة يساوي

صورة

نظرًا لأن الخوارزمية GreedyDiffتفشل في حساب الجدول الأمثل لهذا المثال ، فهي ليست صحيحة دائمًا.

»يمكن العثور على مزيد من المعلومات حول الكتاب على موقع الناشر على الويب
» المحتويات
» مقتطفات

لخصم 25٪ على Khabrozhiteley على القسيمة - الخوارزميات

عند دفع النسخة الورقية من الكتاب ، يتم إرسال كتاب إلكتروني عبر البريد الإلكتروني.

More articles:


All Articles