Алгоритм в любое время - Anytime algorithm

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

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

Имена

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

Цели

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

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

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

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

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

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

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

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

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

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

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

Рекомендации

  1. ^ а б c d е ж Хендлер, Джеймс А., Системы планирования искусственного интеллекта, 1992
  2. ^ а б c Зильберштейн, Шломо. «Использование алгоритмов в любое время в интеллектуальных системах», 1996. http://rbr.cs.umass.edu/shlomo/papers/Zaimag96.pdf
  3. ^ а б c d е ж грамм час я Трава, Джошуа. "Рассуждения о Вычислительный ресурс Распределение ". http://www.acm.org/crossroads/xrds3-1/racra.html В архиве 2007-12-12 на Wayback Machine
  4. ^ алгоритм в любое время из Free Online Dictionary of Computing (FOLDOC)
  5. ^ «Алгоритмы в любое время». Когнитивные архитектуры. Лаборатория искусственного интеллекта Мичиганского университета. Архивировано из оригинал 13 декабря 2013 г.
  6. ^ «Алгоритм в любое время - Справочник по вычислениям». eLook.org. Архивировано из оригинал 12 декабря 2013 г.
  7. ^ а б Хорш, Майкл К., Пул, Дэвид "Всегда и везде алгоритм принятия решений в условиях неопределенности", 2013, http://www.cs.ubc.ca/spider/poole/papers/randaccref.pdf
  8. ^ Бендер, Эдвард А. Математические методы в искусственном интеллекте, IEEE Computer Society Пре, 1996
  9. ^ а б c d Тейе, Аннет десять, Хармелен, Франк. «Описание методов решения проблем с использованием профилей производительности в любое время», 2000.

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

  • Бодди, М., Дин, Т. 1989. Решение зависящих от времени задач планирования. Технический отчет: CS-89-03, Брауновский университет
  • Грасс, Дж. И Зильберштейн, С. 1996. Инструменты разработки алгоритмов в любое время. Бюллетень SIGART (Специальный выпуск об алгоритмах в любое время и расписании обсуждения) 7 (2)
  • Майкл С. Хорш и Дэвид Пул, Алгоритм в любое время для принятия решений в условиях неопределенности, In Proc. 14-я конференция по неопределенности в искусственном интеллекте (UAI-98), Мэдисон, Висконсин, США, июль 1998 г., страницы 246-255.
  • E.J. Хорвиц. Рассуждения о компромиссных выводах в мире ограниченных ресурсов. Технический отчет KSL-86-55, Группа медицинских компьютерных наук, Секция медицинской информатики, Стэнфордский университет, Стэнфорд, Калифорния, март 1986 г.
  • Уоллес, Р., Фрейдер, E. 1995. Алгоритмы в любое время для удовлетворения ограничений и задач SAT. Документ, представленный на семинаре IJCAI-95 по алгоритмам в любое время и планированию обсуждения, 20 августа, Монреаль, Канада.
  • Зильберштейн, С. 1993. Операционная рациональность за счет компиляции алгоритмов в любое время. Кандидат наук. дисс., Отдел компьютерных наук Калифорнийского университета в Беркли.
  • Шломо Зильберштейн, Использование алгоритмов в любое время в интеллектуальных системах, Журнал AI, 17(3):73-83, 1996