Алгоритм в любое время
Алгоритм, который может вернуть действительное решение проблемы даже в случае прерывания

В информатике алгоритмом anytime является алгоритм , который может вернуть действительное решение проблемы, даже если он был прерван до того, как закончился. Ожидается, что алгоритм будет находить все лучшие и лучшие решения, чем дольше он работает.

Большинство алгоритмов работают до завершения: они предоставляют один ответ после выполнения некоторого фиксированного количества вычислений. Однако в некоторых случаях пользователь может захотеть завершить алгоритм до его завершения. Например, объем требуемых вычислений может быть значительным, и вычислительные ресурсы могут быть перераспределены. Большинство алгоритмов либо работают до завершения, либо не предоставляют никакой полезной информации о решении. Однако алгоритмы Anytime способны возвращать частичный ответ, качество которого зависит от объема вычислений, которые они смогли выполнить. Ответ, сгенерированный алгоритмами Anytime, является приближением правильного ответа.

Имена

Алгоритм anytime также может называться «прерываемым алгоритмом». Они отличаются от алгоритмов контракта, которые должны объявлять время заранее; в алгоритме anytime процесс может просто объявить, что он завершается. [1]

Цели

Целью алгоритмов anytime является предоставление интеллектуальным системам возможности выдавать результаты лучшего качества в обмен на время выполнения. [2] Они также должны быть гибкими во времени и ресурсах. [3] Они важны, потому что алгоритмам искусственного интеллекта или ИИ может потребоваться много времени для завершения результатов. Этот алгоритм разработан для выполнения за более короткий промежуток времени. [3] Кроме того, они предназначены для лучшего понимания того, что система зависит и ограничена своими агентами и тем, как они работают совместно. [3] Примером является итерация Ньютона-Рафсона , применяемая для нахождения квадратного корня числа. [4] Другим примером, который использует алгоритмы anytime, являются задачи траектории, когда вы нацеливаетесь на цель; объект движется в пространстве, ожидая завершения алгоритма, и даже приблизительный ответ может значительно повысить его точность, если дать его заранее. [3]

Что делает алгоритмы anytime уникальными, так это их способность возвращать множество возможных результатов для любых заданных входных данных. [2] Алгоритм anytime использует множество четко определенных показателей качества для отслеживания прогресса в решении проблем и распределенных вычислительных ресурсов. [2] Он продолжает искать наилучший возможный ответ за то количество времени, которое ему дано. [5] Он может не работать до завершения и может улучшить ответ, если ему позволить работать дольше. [6] Это часто используется для больших задач с множеством решений. [7] Это, как правило, не дает полезной информации, если ему не позволить завершиться. [8] Хотя это может показаться похожим на динамическое программирование , разница в том, что он настраивается с помощью случайных корректировок, а не последовательных.

Алгоритмы Anytime разработаны таким образом, что им можно приказать остановиться в любой момент и они вернут наилучший результат, который они нашли до сих пор. [3] Вот почему он называется прерываемым алгоритмом. Некоторые алгоритмы Anytime также сохраняют последний результат, так что если им дать больше времени, они могут продолжить с того места, где остановились, чтобы получить еще лучший результат. [3]

Деревья решений

Когда решающий должен действовать, должна быть некоторая двусмысленность. Также должна быть некоторая идея о том, как разрешить эту двусмысленность. Эта идея должна быть транслируема в диаграмму состояния к действию. [7]

Профиль производительности

Профиль производительности оценивает качество результатов на основе входных данных и количества времени, выделенного алгоритму. [3] Чем лучше оценка, тем скорее будет найден результат. [3] Некоторые системы имеют большую базу данных, которая дает вероятность того, что выход является ожидаемым выходом. [3] Важно отметить, что один алгоритм может иметь несколько профилей производительности. [9] В большинстве случаев профили производительности строятся с использованием математической статистики с использованием репрезентативных случаев. Например, в задаче о коммивояжере профиль производительности был сгенерирован с использованием определенной пользователем специальной программы для генерации необходимой статистики. [1] В этом примере профиль производительности представляет собой отображение времени на ожидаемые результаты. [1] Это качество можно измерить несколькими способами:

  • определенность: где вероятность правильности определяет качество [1]
  • точность: где предел погрешности определяет качество [1]
  • специфичность: где количество деталей определяет качество [1]

Предпосылки алгоритма

Первоначальное поведение: в то время как некоторые алгоритмы начинают с немедленных догадок, другие используют более расчетливый подход и имеют начальный период, прежде чем делать какие-либо догадки. [9]

  • Направление роста: как качество «выхода» или результата программы меняется в зависимости от количества времени («времени выполнения») [9]
  • Темп роста: Величина увеличения с каждым шагом. Она постоянно меняется, как при пузырьковой сортировке , или меняется непредсказуемо?
  • Конечное условие: необходимое количество времени выполнения [9]

Примеры

В литературе описано много известных алгоритмов anytime. Перечислим некоторые из них.

Ссылки

  1. ^ abcdef Хендлер, Джеймс А., ред. (2014) [1992]. Системы планирования искусственного интеллекта: Труды первой конференции (AIPS 92). Elsevier. ISBN 978-0-08-049944-4.
  2. ^ abc Зильберштейн 1996
  3. ^ abcdefghi Grass, J. (1996). «Рассуждения о распределении вычислительных ресурсов. XRDS: Перекрестки». Журнал ACM для студентов . 3 (1): 16– 20. doi : 10.1145/332148.332154 . S2CID  45448244.
  4. ^ алгоритм anytime из Free Online Dictionary of Computing (FOLDOC)
  5. ^ "Anytime algorithms". Когнитивные архитектуры . Лаборатория искусственного интеллекта Мичиганского университета. Архивировано из оригинала 13 декабря 2013 года.
  6. ^ "Anytime algorithm - Computing Reference". eLook.org . Архивировано из оригинала 12 декабря 2013 г.
  7. ^ ab Хорш и Пул 1998
  8. ^ Бендер, Эдвард А. (1996). Математические методы в искусственном интеллекте . Wiley. ISBN 978-0-8186-7200-2.
  9. ^ abcd Teije, AT; van Harmelen, F. (2000). «Описание методов решения проблем с использованием профилей производительности в любое время» (PDF) . Труды 14-й Европейской конференции по искусственному интеллекту . С.  181–5 .
  10. ^ Пино, Джоэль; Гордон, Джефф; Трун, Себастьян (2003-08-09). «Итерация значений на основе точек: алгоритм POMDP в любое время». Труды 18-й Международной совместной конференции по искусственному интеллекту . IJCAI'03. Сан-Франциско, Калифорния, США: Morgan Kaufmann Publishers Inc.: 1025–1030 .

Дальнейшее чтение

  • Бодди, М.; Дин, Т. (1989). «Решение задач планирования, зависящих от времени». Труды 11-й международной совместной конференции по искусственному интеллекту . Том 2. С.  979–984 . Университет Брауна CS-89-03.
  • Grass, J.; Zilberstein, S. (1996). «Anytime Algorithm Development Tools». ACM SIGART Bulletin . 7 (2 Специальный выпуск по Anytime Algorithms и Deliberation Scheduling): 20–27 . doi :10.1145/242587.242592. S2CID  7670055.
  • Хорш, М. К.; Пул, Д. (1998). "Алгоритм принятия решений в любое время в условиях неопределенности" (PDF) . Труды Четырнадцатой конференции по неопределенности в искусственном интеллекте . С.  246–255 . arXiv : 1301.7384 . ISBN 978-1-55860-555-8.
  • Хорвиц, Э. Дж. (март 1986 г.). Рассуждения о компромиссах вывода в мире ограниченных ресурсов (технический отчет). Медицинская компьютерная научная группа, секция медицинской информатики, Стэнфордский университет. KSL-86-55.
  • Уоллес, Р.; Фройдер, Э. (1995). «Anytime Algorithms for Constraint Satisfaction and SAT Problems». ACM SIGART Bulletin . 7 (2): 7– 10. doi : 10.1145/242587.242589 . S2CID  8250394.
  • Зильберштейн, С. (1993). Операционная рациональность через компиляцию алгоритмов любого времени (PhD). Отделение компьютерных наук, Калифорнийский университет в Беркли. UMX GAX94-08166.
  • Зильберштейн, Шломо (1996). «Использование алгоритмов Anytime в интеллектуальных системах» (PDF) . Журнал AI . 17 (3): 73–83 .
Взято с "https://en.wikipedia.org/w/index.php?title=Anytime_algorithm&oldid=1272266526"