الگوریتم در هر زمان - ویکی‌پدیا، دانشنامهٔ آزاد

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

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

نام‌ها[ویرایش]

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

اهداف[ویرایش]

هدف الگوریتم‌های هر زمان این است که سیستم‌های هوشمند را قادر سازد تا در ازای زمان بیشتر، نتایج با کیفیت تری تولید کنند.[۲] آنها همچنین باید در زمان و منابع انعطاف‌پذیر باشند.[۳] این الگوریتم‌ها مهم هستند زیرا برای تکمیل نتایج در یک مدت زمان کوتاه طراحی شده‌اند در صورتی که هوش مصنوعی یا الگوریتم‌های هوش مصنوعی می‌توانند مدت زمان زیادی را صرف تکمیل نتایج کنند.[۳] همچنین، این الگوریتم‌ها در نظر گرفته شده‌اند که درک بهتری از اینکه سیستم وابسته و محدود به فاکتورهایش و نحوهٔ همکاری آنها است، داشته باشند[۳] یک مثال، تکرار نیوتن-رافسون برای یافتن ریشه مرتبه دوم یک عدد است.[۴] مثال دیگری که از الگوریتم‌های هر زمان استفاده می‌کند، مسائل مسیریابی هستند هنگامی که شما برای مقصودی هدف گذاری می‌کنید؛ جسم در حال حرکت در فضاست در حالی که منتظر به پایان رسیدن الگوریتم است و یک پاسخ، حتی اگر تقریبی باشد، اگر زود بدست آید می‌تواند به‌طور قابل توجهی وقوع آن را بهبود بخشد.[۳]

آنچه الگوریتم‌های هر زمان را منحصر به فرد می‌کند، توانایی آن‌ها در بازگرداندن تعداد زیادی نتیجه ممکن برای هر ورودی داده شده‌است.[۲] الگوریتم در هر زمان از بسیاری از معیارهای اندازه‌گیری کیفی تعریف شده برای نظارت بر پیشرفت در حل مسائل و منابع محاسباتی توزیع شده استفاده می‌کند.[۲] آن به دنبال بهترین پاسخ ممکن با مقدار زمان مشخص داده شده، می‌گردد.[۵] این الگوریتم تا زمان تکمیل، اجرا نمی‌شود و اگر مجاز به اجرای طولانی‌تر باشد، ممکن است پاسخ را بهبود ببخشد.[۶] این اغلب برای مجموعه مشکلات یک تصمیم‌گیری بزرگ استفاده می‌شود.[۷] الگوریتم هر زمان به‌طور کلی، تا وقتی که مجاز به تمام شدن نباشد، اطلاعات مفیدی ارائه نمی‌دهد.[۸] با اینکه این الگوریتم ممکن است شبیه به برنامه‌نویسی پویا به نظر برسد، تفاوت آنها در این است که الگوریتم در هر زمان بیشتر از آن که از طریق تنظیمات تصادفی، ترتیب یافته باشد، به خوبی تنظیم شده‌است.

الگوریتم‌های هر زمان به نوعی طراحی شده‌اند تا بتوان آنها را در هر زمان متوقف کرد و بهترین نتیجه ای که تا آن لحظه بدست آورده‌اند، دریافت کرده.[۳] به همین دلیل است که الگوریتم قطع نامیده می‌شوند. الگوریتم‌های هر زمان همچنین آخرین نتیجه را حفظ می‌کنند، به طوری که اگر به آنها زمان بیشتری را بدهیم، می‌توانند از جایی که فرایند را ترک کرده‌اند برای به دست آوردن نتایج بهتر ادامه دهند.[۳]

درختان تصمیم‌گیری[ویرایش]

هنگامی که تصمیم گیرنده باید عمل کند، باید مقداری ابهام وجود داشته باشد. همچنین باید تعدادی ایده در مورد چگونگی حل این ابهام وجود داشته باشد. این ایده باید قابل ترجمه به یک حالت از نمودار عمل باشد.[۷]

مشخصات عملکرد[ویرایش]

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

  • اطمینان: احتمال صحت، کیفیت را تعیین می‌کند.[۱]
  • دقت: محدوده خطا، کیفیت را تعیین می‌کند[۱]
  • خاصیت: مقدار جزئیات، کیفیت را تعیین می‌کند[۱]

پیش نیازهای الگوریتم[ویرایش]

رفتار اولیه: در حالی که برخی از الگوریتم‌ها با حدس‌های اولیه شروع می‌شوند، بقیهٔ آنها یک رویکرد محاسبه شده تر را پیش می‌گیرند و پیش از انجام هر حدسی، یک دورهٔ شروع و راه اندازی دارند.[۹]

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

منابع[ویرایش]

  1. ↑ ۱٫۰ ۱٫۱ ۱٫۲ ۱٫۳ ۱٫۴ ۱٫۵ هندلر، جیمز A. ، سیستم‌های برنامه‌ریزی هوش مصنوعی، 1992
  2. ↑ ۲٫۰ ۲٫۱ ۲٫۲ زیلبرشتاین، شلومو. "استفاده از الگوریتم‌های هر زمان در سیستم‌های هوشمند". http://rbr.cs.umass.edu/shlomo/papers/Zaimag96.pdf
  3. ↑ ۳٫۰ ۳٫۱ ۳٫۲ ۳٫۳ ۳٫۴ ۳٫۵ ۳٫۶ ۳٫۷ ۳٫۸ چمن، یوشع. "استدلال در مورد تخصیص منابع محاسباتی ." http://www.acm.org/crossroads/xrds3-1/racra.html بایگانی‌شده در ۱۲ دسامبر ۲۰۰۷ توسط Wayback Machine
  4. ↑ الگوریتم در هر زمان از Free Online Dictionary of Computing (FOLDOC)
  5. ↑ "Anytime algorithms". Cognitive architectures. University of Michigan Artificial Intelligence Laboratory. Archived from the original on 13 Dec 2013.
  6. ↑ "Anytime algorithm - Computing Reference". eLook.org. Archived from the original on 12 Dec 2013.
  7. ↑ ۷٫۰ ۷٫۱ هارچ، مایکل سی، پول، دیوید "الگوریتم هر زمان برای تصمیم‌گیری در معرض عدم قطعیت" http://www.cs.ubc.ca/spider/poole/papers/randaccref.pdf
  8. ↑ بندر، ادوارد A. روش‌های ریاضی در هوش مصنوعی، انجمن کامپیوتر کامپیوتر IEEE، 1996
  9. ↑ ۹٫۰ ۹٫۱ ۹٫۲ ۹٫۳ تیتی، آنت ده، هارملن، فرانک. "توصیف روش‌های حل مسئله با استفاده از پروفیل‌های عملکرد هر زمان".

خواندن بیشتر[ویرایش]

  • 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
برگرفته از «https://fa.wikipedia.org/w/index.php?title=الگوریتم_در_هر_زمان&oldid=36035837»