الگوریتم در هر زمان

در علم کامپیوتر، الگوریتم در هر زمان (انگلیسی: anytime algorithm)، الگوریتمی است که یک راه حل معتبر برای یک مشکل را به ما می‌دهد. حتی اگر الگوریتم قبل از اینکه به پایان برسد متوقف شود. انتظار می‌رود هرچه الگوریتم پیش تر می‌رود راه حل‌های بهتر و بهتری پیدا کند.

اکثر الگوریتم‌ها اجرا می‌شوند تا کامل شوند: آنها پس از انجام مقدار ثابتی از محاسبات، یک پاسخ واحد را ارائه می‌دهند. با این حال، در برخی موارد، ممکن است کاربر بخواهد قبل از اتمام الگوریتم، آن را خاتمه دهد. برای مثال، مقدار محاسبات مورد نیاز ممکن است قابل توجه باشد، و منابع محاسباتی ممکن است نیاز به تخصیص مجدد داشته باشند. اکثر الگوریتم‌ها یا اجرا می‌شوند تا به پایان برسند یا هیچ اطلاعات مفیدی برای حل ارائه نمی‌دهند. با این وجود، الگوریتم‌های هر زمان قادر به بدست آوردن پاسخ‌های جزئی هستند، که کیفیت آن‌ها به مقدار محاسباتی که قادر به انجام آن هستند، بستگی دارد. پاسخ ایجاد شده توسط الگوریتم‌های هر زمان تخمینی نزدیک به پاسخ صحیح است.

 نام‌ها 
الگوریتم همیشه در هر زمان را همچنین می‌توان «الگوریتم قطع» نامید. آنها با الگوریتم‌های قرارداد، که باید پیش از انجام فرایند زمان را اعلام کنند، متفاوت هستند. در یک الگوریتم در هر زمان، یک فرایند می‌تواند دقیقاً اعلام کند که پایان می‌یابد. هندلر، جیمز A. ، سیستم‌های برنامه‌ریزی هوش مصنوعی، 1992 

 اهداف 
هدف الگوریتم‌های هر زمان این است که سیستم‌های هوشمند را قادر سازد تا در ازای زمان بیشتر، نتایج با کیفیت تری تولید کنند. زیلبرشتاین، شلومو. "استفاده از الگوریتم‌های هر زمان در سیستم‌های هوشمند". http://rbr.cs.umass.edu/shlomo/papers/Zaimag96.pdf  آنها همچنین باید در زمان و منابع انعطاف‌پذیر باشند.چمن، یوشع. "استدلال در مورد تخصیص منابع محاسباتی ." http://www.acm.org/crossroads/xrds3-1/racra.html  این الگوریتم‌ها مهم هستند زیرا برای تکمیل نتایج در یک مدت زمان کوتاه طراحی شده‌اند در صورتی که هوش مصنوعی یا الگوریتم‌های هوش مصنوعی می‌توانند مدت زمان زیادی را صرف تکمیل نتایج کنند. همچنین، این الگوریتم‌ها در نظر گرفته شده‌اند که درک بهتری از اینکه سیستم وابسته و محدود به فاکتورهایش و نحوهٔ همکاری آنها است، داشته باشند یک مثال، تکرار نیوتن-رافسون برای یافتن ریشه مرتبه دوم یک عدد است. الگوریتم در هر زمان از Free Online Dictionary of Computing (FOLDOC)  مثال دیگری که از الگوریتم‌های هر زمان استفاده می‌کند، مسائل مسیریابی هستند هنگامی که شما برای مقصودی هدف گذاری می‌کنید؛ جسم در حال حرکت در فضاست در حالی که منتظر به پایان رسیدن الگوریتم است و یک پاسخ، حتی اگر تقریبی باشد، اگر زود بدست آید می‌تواند به‌طور قابل توجهی وقوع آن را بهبود بخشد.

آنچه الگوریتم‌های هر زمان را منحصر به فرد می‌کند، توانایی آن‌ها در بازگرداندن تعداد زیادی نتیجه ممکن برای هر ورودی داده شده‌است. زیلبرشتاین، شلومو. "استفاده از الگوریتم‌های هر زمان در سیستم‌های هوشمند". http://rbr.cs.umass.edu/shlomo/papers/Zaimag96.pdf  الگوریتم در هر زمان از بسیاری از معیارهای اندازه‌گیری کیفی تعریف شده برای نظارت بر پیشرفت در حل مسائل و منابع محاسباتی توزیع شده استفاده می‌کند. آن به دنبال بهترین پاسخ ممکن با مقدار زمان مشخص داده شده، می‌گردد. این الگوریتم تا زمان تکمیل، اجرا نمی‌شود و اگر مجاز به اجرای طولانی‌تر باشد، ممکن است پاسخ را بهبود ببخشد. این اغلب برای مجموعه مشکلات یک تصمیم‌گیری بزرگ استفاده می‌شود. هارچ، مایکل سی، پول، دیوید "الگوریتم هر زمان برای تصمیم‌گیری در معرض عدم قطعیت" http://www.cs.ubc.ca/spider/poole/papers/randaccref.pdf  الگوریتم هر زمان به‌طور کلی، تا وقتی که مجاز به تمام شدن نباشد، اطلاعات مفیدی ارائه نمی‌دهد. بندر، ادوارد A. روش‌های ریاضی در هوش مصنوعی، انجمن کامپیوتر کامپیوتر IEEE، 1996  با اینکه این الگوریتم ممکن است شبیه به برنامه‌نویسی پویا به نظر برسد، تفاوت آنها در این است که الگوریتم در هر زمان بیشتر از آن که از طریق تنظیمات تصادفی، ترتیب یافته باشد، به خوبی تنظیم شده‌است.

الگوریتم‌های هر زمان به نوعی طراحی شده‌اند تا بتوان آنها را در هر زمان متوقف کرد و بهترین نتیجه ای که تا آن لحظه بدست آورده‌اند، دریافت کرده.چمن، یوشع. "استدلال در مورد تخصیص منابع محاسباتی ." http://www.acm.org/crossroads/xrds3-1/racra.html  به همین دلیل است که الگوریتم قطع نامیده می‌شوند. الگوریتم‌های هر زمان همچنین آخرین نتیجه را حفظ می‌کنند، به طوری که اگر به آنها زمان بیشتری را بدهیم، می‌توانند از جایی که فرایند را ترک کرده‌اند برای به دست آوردن نتایج بهتر ادامه دهند.

 درختان تصمیم‌گیری 
هنگامی که تصمیم گیرنده باید عمل کند، باید مقداری ابهام وجود داشته باشد. همچنین باید تعدادی ایده در مورد چگونگی حل این ابهام وجود داشته باشد. این ایده باید قابل ترجمه به یک حالت از نمودار عمل باشد. هارچ، مایکل سی، پول، دیوید "الگوریتم هر زمان برای تصمیم‌گیری در معرض عدم قطعیت" http://www.cs.ubc.ca/spider/poole/papers/randaccref.pdf 

 مشخصات عملکرد 
پروفایل سنجش عملکرد، کیفیت نتایج بر اساس ورودی و مقدار زمان که به الگوریتم اختصاص می‌یابد، تخمین می‌زند.چمن، یوشع. "استدلال در مورد تخصیص منابع محاسباتی ." http://www.acm.org/crossroads/xrds3-1/racra.html  هرچه این تخمین بهتر باشد، نتیجه نیز سریع تر بدست خواهد آمد. برخی سیستم‌ها دارای پایگاه داده بزرگتری هستند که این احتمال را موجب می‌شود که خروجی داده شده، همان خروجی مورد نظر باشد. مهم است که توجه داشته باشید که یک الگوریتم می‌تواند چندین پروفایل داشته باشد. تیتی، آنت ده، هارملن، فرانک. "توصیف روش‌های حل مسئله با استفاده از پروفیل‌های عملکرد هر زمان".  پروفایل‌های سنجش عملکرد، بیشتر اوقات با استفاده از آمار ریاضی که از موارد نمایه استفاده می‌کنند، ساخته می‌شوند. به عنوان مثال، در مسئله فروشنده دوره‌گرد، پروفایل سنجش عملکرد با استفاده از یک برنامه خاص تعریف شده توسط کاربر برای تولید آمار لازم ایجاد شد. هندلر، جیمز A. ، سیستم‌های برنامه‌ریزی هوش مصنوعی، 1992  در این مثال، پروفایل سنجش عملکرد همان نقشه‌برداری زمان طی رسیدن به نتایج مورد نظر است. این کیفیت را می‌توان به چند روش مختلف اندازه‌گیری کرد:
 اطمینان: احتمال صحت، کیفیت را تعیین می‌کند. هندلر، جیمز A. ، سیستم‌های برنامه‌ریزی هوش مصنوعی، 1992 
 دقت: محدوده خطا، کیفیت را تعیین می‌کند
 خاصیت: مقدار جزئیات، کیفیت را تعیین می‌کند

 پیش نیازهای الگوریتم 
رفتار اولیه: در حالی که برخی از الگوریتم‌ها با حدس‌های اولیه شروع می‌شوند، بقیهٔ آنها یک رویکرد محاسبه شده تر را پیش می‌گیرند و پیش از انجام هر حدسی، یک دورهٔ شروع و راه اندازی دارند. تیتی، آنت ده، هارملن، فرانک. "توصیف روش‌های حل مسئله با استفاده از پروفیل‌های عملکرد هر زمان". 
 جهت رشد: چگونگی تغییر کیفیت خروجی یا نتیجه برنامه، به صورت تابعی از مقدار زمان ("زمان اجرا"). تیتی، آنت ده، هارملن، فرانک. "توصیف روش‌های حل مسئله با استفاده از پروفیل‌های عملکرد هر زمان". 
 نرخ رشد: میزان افزایش با هر مرحله. آیا به‌طور مداوم تغییر می‌کند، مانند یک مرتب‌سازی حبابی، یا غیرقابل پیش‌بینی تغییر می‌کند؟
 شرط پایان: مقدار زمان اجرا مورد نیاز است

 منابع 

 خواندن بیشتر 

 Boddy, M, Dean, T. 1989. Solving Time-Dependent Planning Problems. Technical Report: CS-89-03, Brown University
 Grass, J. , and Zilberstein, S. 1996. Anytime Algorithm Development Tools. SIGART Bulletin (Special Issue on Anytime Algorithms and Deliberation Scheduling) 7(2)
 Michael C. Horsch and David Poole, An Anytime Algorithm for Decision Making under Uncertainty, In Proc. 14th Conference on Uncertainty in Artificial Intelligence (UAI-98), Madison, Wisconsin, USA, July 1998, pages 246-255.
 E.J. Horvitz. Reasoning about inference tradeoffs in a world of bounded resources. Technical Report KSL-86-55, Medical Computer Science Group, Section on Medical Informatics, Stanford University, Stanford, CA, مارس ۱۹۸۶
 Wallace, R. , and Freuder, E. 1995. Anytime Algorithms for Constraint Satisfaction and SAT Problems. Paper presented at the IJCAI-95 Workshop on Anytime Algorithms and Deliberation Scheduling, 20 August, Montreal, Canada.
 Zilberstein, S. 1993. Operational Rationality through Compilation of Anytime Algorithms. Ph.D. diss. , Computer Science Division, University of California at Berkeley.
 Shlomo Zilberstein, Using Anytime Algorithms in Intelligent Systems, AI Magazine, 17(3):73-83, 1996

رده:الگوریتم‌های جستجو
رده:صفحات با ترجمه بازبینی‌نشده
رده:هوش مصنوعی