الرئيسيةعريقبحث

الخوارزمية الفورية

☰ جدول المحتويات

في علم الحاسوب، الخوارزمية الفورية (online algorithm[1]) هي التي تقوم بمعالجة المدخلات (أو البيانات) عن طريق إدراجها عنصر تلو الأخر بطريقة تسلسلية، أي أن ترتيب المدخلات يكون على حسب ظهورها بشكل فوري إلى الخوارزمية، دون أن تكون جميع المدخلات متاحة منذ البداية.

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

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

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

ليس لكل خوارمية غير فورية نظير فعال (تنافسي) فوري.

تعريف

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

تفسيرات أخرى

أمثلة

بعض الخوارزميات على الإنترنت :

مشاكل فورية

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

هناك العديد من المشاكل الرسمية التي تحتوي على أكثر من خوارزمية فورية كحل:

  • مشكلة خادم K
  • مشكلة جدولة محل العمل
  • مشكلة تحديث القائمة
  • مشكلة قطاع الطرق
  • مشكلة سكرتير
  • ألعاب البحث
  • مشكلة تأجير التزلج
  • مشكلة البحث الخطي
  • مشكلة اختيار المحفظة [2]

مقالات ذات صلة

المراجع

  1. Karp, Richard M. (1992). "On-line algorithms versus off-line algorithms: How much is it worth to know the future?" ( كتاب إلكتروني PDF ). IFIP Congress (1). 12: 416–429. مؤرشف من الأصل ( كتاب إلكتروني PDF ) في 5 مارس 201617 أغسطس 2015.
  2. Dochow, Robert (2016). Online Algorithms for the Portfolio Selection Problem. Springer Gabler. مؤرشف من الأصل في 4 مايو 2020.

روابط خارجية

موسوعات ذات صلة :