Алгоритм anytime
Алгори́тм anytime — это алгоритм в области информатики, который способен возвращать допустимое решение задачи, даже если его выполнение было прервано до завершения. Ожидается, что по мере продолжения работы такой алгоритм будет находить всё лучшие решения.
Большинство алгоритмов выполняются до завершения: они предоставляют единственный ответ после определённого объёма вычислений. Однако в ряде случаев пользователь может пожелать остановить алгоритм до завершения — например, если вычисления слишком затратны, а вычислительные ресурсы необходимо перенаправить. Обычно такие алгоритмы либо завершаются полностью, либо не предоставляют никакой полезной информации. Алгоритмы anytime способны вернуть частичный ответ, качество которого зависит от объёма выполненных вычислений. Ответ, выдаваемый таким образом, является приближением к правильному.
Названия
Алгоритм anytime также называют «прерываемым алгоритмом». В отличие от контрактных алгоритмов, которым заранее указывается время работы, anytime-алгоритм может быть остановлен в любой момент — достаточно лишь сообщить процессу о прекращении работы[1].
Цели
Цель anytime-алгоритмов — дать интеллектуальным системам возможность улучшать качество выдаваемых результатов за счёт увеличения времени вычислений[2]. Такие алгоритмы также должны быть гибкими по времени и потребляемым ресурсам[3]. Они важны, поскольку алгоритмы искусственного интеллекта часто требуют значительных затрат времени на вычисления. Anytime-алгоритмы предназначены для сокращения времени получения приемлемых результатов[3]. Кроме того, такие алгоритмы способствуют лучшему пониманию зависимости системы от её агентов и особенностей их кооперации[3]. Примером может служить применение итерации метода Ньютона — Рафсона для вычисления квадратного корня числа[4]. Ещё один пример применения anytime-алгоритмов — задачи траекторий, когда объект движется в пространстве и даже приближённый ответ, полученный заранее, может заметно повысить точность[3].
Особенностью anytime-алгоритмов является способность возвращать множество возможных исходов для одного и того же входного набора[2]. Они используют чётко определённые меры качества для отслеживания прогресса в решении задач, распределённых по различным вычислительным ресурсам[2]. Алгоритм продолжает поиск наилучшего результата в пределах выделенного времени[5]. Он может быть незавершённым, но при увеличении времени способен улучшать ответ[6]. Такой подход часто используется при решении задач с большим пространством вариантов[7]. В отличие от динамического программирования, такие алгоритмы тонко настраиваются за счёт случайных корректировок, а не последовательных шагов.
Алгоритм anytime предназначен для того, чтобы в любой момент работы по требованию можно было получить наилучший из найденных результатов[3]. Поэтому его называют также прерываемым алгоритмом. Некоторые алгоритмы this типа сохраняют последнее найденное решение, что позволяет при выделении дополнительного времени продолжить вычисления и получить ещё лучший результат[3].
Деревья решений
В ситуациях, когда необходимо принять решение, часто возникает неоднозначность. Кроме того, важно иметь схему, позволяющую разрешить эту неоднозначность, которую можно выразить с помощью диаграммы «состояние-действие»[7].
Профиль производительности
Профиль производительности оценивает качество результата в зависимости от входных данных и выделенного на алгоритм времени[3]. Точность такой оценки влияет на быстроту получения результата[3]. Некоторые системы используют объёмные базы данных, чтобы повысить вероятность соответствия ответа ожидаемому[3]. Один и тот же алгоритм может иметь несколько профилей производительности[8]. Чаще всего, профили формируются с использованием математической статистики на репрезентативных данных. Например, в задаче коммивояжёра профиль был построен с помощью специальной программы, генерирующей необходимые статистики[1]. В данном случае профиль связывает время вычислений с ожидаемыми результатами[1]. Оценивать качество можно по следующим критериям:
Предпосылки для алгоритма
- Начальное поведение: Некоторые алгоритмы начинают с мгновенных предположений, другие же подходят более взвешенно и требуют времени на инициализацию перед выдачей первых результатов[8];
- Направление развития: Как качество выходных данных изменяется по мере увеличения времени работы[8];
- Скорость развития: Величина улучшения на каждом шаге. Происходит ли она постоянно, как в сортировке пузырьком, или изменяется непредсказуемо?
- Условие завершения: Необходимое время исполнения[8].
Примечания
Литература
- Boddy, M.; Dean, T. (1989). “Solving time-dependent planning problems”. Proceedings of the 11th international joint conference on Artificial intelligence [англ.]. 2. pp. 979—984. Дата обращения 2024-06-14.
- Grass, J.; Zilberstein, S. (1996). “Anytime Algorithm Development Tools”. ACM SIGART Bulletin [англ.]. 7 (2 Special Issue on Anytime Algorithms and Deliberation Scheduling): 20—27. DOI:10.1145/242587.242592. S2CID 7670055. Дата обращения 2024-06-14.
- Horsch, M.C.; Poole, D. (1998). “An anytime algorithm for decision making under uncertainty” (PDF). Proceedings of the Fourteenth conference on Uncertainty in artificial intelligence [англ.]. pp. 246—255. arXiv:1301.7384. ISBN 978-1-55860-555-8. Дата обращения 2024-06-14.
- Horvitz, E.J. (Март 1986). Reasoning about inference tradeoffs in a world of bounded resources (Technical report) [англ.]. Medical Computer Science Group, Section on Medical Informatics, Stanford University. KSL-86-55.
- Wallace, R.; Freuder, E. (1995). “Anytime Algorithms for Constraint Satisfaction and SAT Problems”. ACM SIGART Bulletin [англ.]. 7 (2): 7—10. DOI:10.1145/242587.242589. S2CID 8250394. Дата обращения 2024-06-14.
|access-date=требует|url=(справка) - Zilberstein, S. (1993). Operational Rationality through Compilation of Anytime Algorithms (PhD) [англ.]. Computer Science Division, University of California at Berkeley. Дата обращения 2024-06-14.
- Zilberstein, Shlomo (1996). “Using Anytime Algorithms in Intelligent Systems” (PDF). AI Magazine [англ.]. 17 (3): 73—83. Дата обращения 2024-06-14.