تحليل المنافسة (خوارزمية عبر الإنترنت)

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

بالنسبة للعديد من الخوارزميات، لا يعتمد الأداء على حجم المدخلات فحسب، بل على قيمها أيضًا. على سبيل المثال، تختلف صعوبة فرز مصفوفة من العناصر باختلاف الترتيب الأولي. تُحلل هذه الخوارزميات المعتمدة على البيانات في حالتي المتوسط والأسوأ. يُعد التحليل التنافسي طريقةً لتحليل أسوأ الحالات للخوارزميات الفورية والعشوائية ، والتي تعتمد عادةً على البيانات.

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

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

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

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

انظر أيضاً

مراجع

سليتور، د.؛ تارجان ، ر. (1985)، "الكفاءة المستهلكة لتحديث القوائم وقواعد التصفح"، اتصالات ACM ، 28 (2): 202-208 ، doi : 10.1145/2786.2793.
أسبنيس، جيمس (1998)، "التحليل التنافسي للخوارزميات الموزعة"، في فيات، أ .؛ ووجينجر، جي جي (محرران)، الخوارزميات عبر الإنترنت: أحدث ما توصل إليه العلم ، سلسلة محاضرات في علوم الحاسوب، المجلد 1442، الصفحات 118-146 ، doi : 10.1007/BFb0029567 ، ISBN 978-3-540-64917-5.
بورودين، أ .؛ اليانيف، ر. (1998)، الحوسبة عبر الإنترنت والتحليل التنافسي ، مطبعة جامعة كامبريدج، ISBN 0-521-56392-5.
أويربوخ، ب.؛ كوتن، س .؛ بيليج، د. (1992)، "جدولة الوظائف الموزعة التنافسية"، مؤتمر ACM STOC، فيكتوريا، كولومبيا البريطانية، كندا.