خوارزمية الإنترنت

في علم الحاسوب ، تُعرَّف الخوارزمية المتصلة بالإنترنت ^{[ 1 ]} بأنها خوارزمية تعالج مدخلاتها جزءًا جزءًا بشكل تسلسلي، أي بالترتيب الذي تُغذى به الخوارزمية ، دون الحاجة إلى توفر المدخلات كاملةً منذ البداية. في المقابل، تُزوَّد الخوارزمية غير المتصلة بالإنترنت ببيانات المسألة كاملةً منذ البداية، ويُطلب منها إخراج إجابة تحل المسألة المطروحة.

في بحوث العمليات ، يُطلق على المجال الذي يتم فيه تطوير الخوارزميات عبر الإنترنت اسم التحسين عبر الإنترنت .

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

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

ليس لكل خوارزمية غير متصلة بالإنترنت نظير فعال متصل بالإنترنت .

في نظرية القواعد، ترتبط هذه القواعد بقواعد الخط المستقيم .

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

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

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

• مشكلة خادم k
• مشكلة جدولة ورش العمل
• مشكلة في تحديث القائمة
• مشكلة قطاع الطرق
• مشاكل السكرتيرة
• ألعاب البحث
• مشكلة تأجير معدات التزلج
• مشكلة البحث الخطي
• مشكلة اختيار المحفظة ^{[ 2 ]}
• مشكلة الترحيل
• أنظمة المهام المترية
• المطابقة الثنائية عبر الإنترنت

• نموذج الخصم
• خوارزمية ديناميكية
• عدم المساواة بين الأنبياء
• الحوسبة في الوقت الحقيقي
• خوارزمية البث
• خوارزمية تسلسلية
• التعلم الآلي عبر الإنترنت / التعلم غير المتصل بالإنترنت

• بورودين، أ .؛ اليانيف، ر. (1998). الحوسبة عبر الإنترنت والتحليل التنافسي . مطبعة جامعة كامبريدج. ISBN 0-521-56392-5.

• قائمة مراجع الأبحاث المتعلقة بالخوارزميات عبر الإنترنت