Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Имена [ править ]

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

Дальнейшее чтение [ править ]

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