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

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

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

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

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

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

تعريف

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

تفسيرات أخرى

خوارزمية الدفق (بالانجليزية: streaming algorithm): هجرز على مقدار الذاكرة اللازمة لتمثيل المدخلات السابقة بدقة؛
خوارزمية ديناميكية (بالانجليزية: dynamic algorithms) هجرز على التعقيد الوقتي في الحصول على حلول للمشاكل الفورية.

أمثلة

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

ترتيب بالإدراج
بيرسيبترون
أخذ عينات الخزان
خوارزمية جشعة
نموذج الخصم
أنظمة المهام المترية
خوارزمية الاحتمالات
خوارزمية استبدال الصفحة
خوارزميات لحساب التباين
خوارزمية Ukkonen

مشاكل فورية

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

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

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

انظر أيضا

بوابة:خوارزميات
خوارزمية ديناميكية
خوارزمية الجري
قابلة برمجة تطبيقات بسيطة لـ XML
الحوسبة في الوقت الحقيقي
خوارزمية متسلسلة
التفهم الآلي الفوري/التفهم الغير الفوري

المراجع

↑ 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) فيخمسة مارس 2016. اطلع عليه بتاريخ 17 أغسطس 2015.
^ Dochow, Robert (2016). . Springer Gabler. مؤرشف من الأصل في أربعة مايو2020.