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

خوارزمية فورية
في علم الحاسوب، الخوارزمية الفورية (online algorithm) هي التي تقوم بمعالجة المدخلات (أو البيانات) عن طريق إدراجها عنصر تلو الأخر بطريقة تسلسلية، أي أن ترتيب المدخلات يكون على حسب ظهورها بشكل فوري إلى الخوارزمية، دون أن تكون جميع المدخلات متاحة منذ البداية.
على النقيض من ذلك، يتم إعطاء الخوارزمية الغير فورية مدخلات المشكلة بأكملها من البداية، وعلى الخوارزمية أن تجد الحل المناسب للمشكلة الكاملة. في أبحاث العمليات، يسمى المجال الذي يتم فيه دراسة وتطوير الخوارزميات الفورية بالتحسين الفوري (أو الأمثلية الفورية).
لنأخذ على سبيل المقارنة خوارزميتين الترتيب بالإنتقاء والإدراج: الترتيب بالانتقاء يوجد العنصر الأقل قيمة من الباقي الغير المصنف ويضعه في أول القائمة، هذا الأمر يتطلب الوصول إلى جميع العناصر بأكملها؛ مما يجعل هذه الخوارزمية غير فورية. من ناحية أخرى، الترتيب بالإدراج يأخذ بعين الاعتبار عنصر واحد فقط في كل تكرار. وفي كل تكرار، الخوارزمية تزيل عنصرًا واحدًا من البيانات المتاحة وتجد الموقع الذي ينتمي إليه ضمن القائمة المصنفة. وبذلك الخوارزمية تنتج حلاً جزئيًا دون النظر إلى العناصر المستقبلية في كل تكرار، مما يجعل هذه الخوارزمية فورية.
لاحظ أن الترتيب بالإدراج يعطي النتيجة المثلى، أي قائمة عناصر مرتبة بشكل صحيح تماماً. ولكن بالنسبة للعديد من المسائل الرياضية، لا يمكن أن تجاري الخوارزميات الفورية أداء الخوارزميات الغير فورية. إذا كانت النسبة بين أداء الخوارزمية الفورية ونظيرتها الغير الفورية (المثلى) محدودة بثابت، فإن الخوارزمية الفورية تعتبر تنافسية.
ليس لكل خوارمية غير فورية نظير فعال (تنافسي) فوري.
تعريف
نظرًا لأنها لا ترى العناصر بالكامل، تضطر الخوارزمية الفورية إلى اتخاذ قرارات قد لا تنتهي فيما بعد إلى الحل الأمثل، وتركز دراسة الخوارزميات الفورية على جودة صنع القرار الممكن في هذا الصدد. يقوم التحليل التنافسي بإضفاء الطابع الرسمي على هذه الفكرة من خلال مقارنة الأداء النسبي لخوارزمية الفورية والغير فورية لنفس المشكلة. على وجه التحديد، يتم تعريف النسبة التنافسية للخوارزمية على أنها النسبة الأسوأ من حيث التكلفة للخوارزمية الفورية مقسومة على التكلفة المثلى، على جميع المدخلات الممكنة. النسبة التنافسية لمشكلة فورية هي أفضل نسبة تنافسية تحققها خوارزمية فورية. حدسياً، توفر النسبة التنافسية مقياسًا لجودة الحلول التي تنتجها هذه الخوارزمية، بينما تشير النسبة التنافسية للمشكلة إلى أهمية معرفة المستقبل لهذه المشكلة.
تفسيرات أخرى
خوارزمية الدفق (بالإنجليزية: streaming algorithm): تركز على مقدار الذاكرة اللازمة لتمثيل المدخلات السابقة بدقة؛
خوارزمية ديناميكية (بالإنجليزية: dynamic algorithms) تركز على التعقيد الوقتي في الحصول على حلول للمشاكل الفورية.
أمثلة
بعض الخوارزميات على الإنترنت :
ترتيب بالإدراج
بيرسيبترون
أخذ عينات الخزان
خوارزمية جشعة
نموذج الخصم
أنظمة المهام المترية
خوارزمية الاحتمالات
خوارزمية استبدال الصفحة
خوارزميات لحساب التباين
خوارزمية Ukkonen
مشاكل فورية
كمثال، مشكلة المسافر الكندي هي مشكلة فورية. الهدف هنا هو تقليل تكلفة الوصول إلى رأس (vertex) في رسم بياني موزون حيث تكون بعض الاضلاع غير موثوقة ومن الممكن ان يتم إزالتها من الرسم البياني. ومع ذلك، يتبين للمسافر ان ضلع (فاشل) قد ازيل فقط عندما يصل المسافر إلى إحدى رؤوس هذا الضلع. أسوأ حالة لهذه المشكلة هي ببساطة أن جميع الاضلاع غير الموثوق بها تفشل وتختزل المشكلة إلى مسألة أقصر مسار المعتادة. يمكن إجراء تحليل للمشكلة بمساعدة التحليل التنافسي. بالنسبة لطريقة التحليل هذه، تعرف الخوارزمية غير الفورية مسبقًا أي الاضلاع ستفشل والهدف هو تقليل النسبة بين أداء الخوارزميات الفورية والغير فورية. هذه المشكلة تعتبر PSPACE-complete.
هناك العديد من المشاكل الرسمية التي تحتوي على أكثر من خوارزمية فورية كحل:
مشكلة خادم K
مشكلة جدولة محل العمل
مشكلة تحديث القائمة
مشكلة قطاع الطرق
مشكلة سكرتير
ألعاب البحث
مشكلة تأجير التزلج
مشكلة البحث الخطي
مشكلة اختيار المحفظة
انظر أيضا
بوابة:خوارزميات
خوارزمية ديناميكية
خوارزمية الجري
واجهة برمجة تطبيقات بسيطة لـ XML
الحوسبة في الوقت الحقيقي
خوارزمية متسلسلة
التعلم الآلي الفوري/التعلم الغير الفوري
المراجع
روابط خارجية
ببليوغرافيا الأوراق على الخوارزميات الفورية
خوارزميات