خوارزمية في أي وقت

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

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

يمكن تسمية الخوارزمية التي تعمل في أي وقت أيضًا باسم "الخوارزمية القابلة للمقاطعة". وهي تختلف عن خوارزميات العقود، التي يجب أن تحدد وقتًا مسبقًا؛ ففي الخوارزمية التي تعمل في أي وقت، يمكن للعملية ببساطة أن تعلن أنها ستنتهي. ^{[ 1 ]}

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

ما يُميز خوارزميات "التشغيل في أي وقت" هو قدرتها على إرجاع العديد من النتائج المُحتملة لأي مُدخل مُعطى. ^{[ 2 ]} تستخدم خوارزمية "التشغيل في أي وقت" العديد من معايير الجودة المُحددة جيدًا لمراقبة التقدم في حل المشكلات وموارد الحوسبة الموزعة . ^{[ 2 ]} تستمر في البحث عن أفضل إجابة مُمكنة ضمن الوقت المُتاح لها. ^{[ 5 ]} قد لا تعمل حتى الاكتمال، وقد تُحسّن الإجابة إذا سُمح لها بالعمل لفترة أطول. ^{[ 6 ]} غالبًا ما تُستخدم هذه الخوارزمية في مسائل مجموعات القرارات الكبيرة. ^{[ 7 ]} لن تُقدم هذه الخوارزمية معلومات مُفيدة بشكل عام ما لم يُسمح لها بالانتهاء. ^{[ 8 ]} على الرغم من أن هذا قد يبدو مُشابهًا للبرمجة الديناميكية ، إلا أن الفرق يكمن في أنها تُضبط بدقة من خلال تعديلات عشوائية، بدلًا من التعديلات التسلسلية.

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

عندما يتعين على صاحب القرار اتخاذ إجراء، لا بد من وجود قدر من الغموض. كما لا بد من وجود فكرة ما حول كيفية حل هذا الغموض. ويجب أن تكون هذه الفكرة قابلة للترجمة إلى مخطط حالة-فعل. ^{[ 7 ]}

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

• اليقين: حيث تحدد احتمالية الصحة الجودة ^{[ 1 ]}
• الدقة: حيث يحدد هامش الخطأ الجودة ^{[ 1 ]}
• التحديد: حيث تحدد كمية التفاصيل الجودة ^{[ 1 ]}

السلوك الأولي: بينما تبدأ بعض الخوارزميات بتخمينات فورية، فإن البعض الآخر يتبع نهجًا أكثر حسابًا ويحتاج إلى فترة بدء تشغيل قبل القيام بأي تخمينات. ^{[ 9 ]}

• اتجاه النمو: كيف تختلف جودة "مخرجات" البرنامج أو نتيجته كدالة لمقدار الوقت ("وقت التشغيل") ^{[ 9 ]}
• معدل النمو: مقدار الزيادة مع كل خطوة. هل يتغير باستمرار، كما هو الحال في فرز الفقاعات ، أم يتغير بشكل غير متوقع؟
• شرط النهاية: مقدار وقت التشغيل المطلوب ^{[ 9 ]}