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

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

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

Имена

Алгоритм в любое время можно также назвать «прерываемым алгоритмом». Они отличаются от алгоритмов контрактов, которые должны заранее объявлять время; в алгоритме в любое время процесс может просто объявить о своем завершении. ^[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]

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж Хендлер, Джеймс А., изд. (2014) [1992]. Системы планирования искусственного интеллекта: материалы первой конференции (AIPS 92) . Эльзевир. ISBN 978-0-08-049944-4 .
^ Jump up to: ^а ^б ^с Зильберштейн 1996 г.
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Грасс, Дж. (1996). «Рассуждения о распределении вычислительных ресурсов. XRDS: Перекресток» . Журнал ACM для студентов . 3 (1): 16–20. дои : 10.1145/332148.332154 . S2CID 45448244 .
^ Алгоритм в любое время из Бесплатного онлайн-словаря вычислений (FOLDOC)
^ «Алгоритмы в любое время» . Когнитивные архитектуры . Лаборатория искусственного интеллекта Мичиганского университета. Архивировано из оригинала 13 декабря 2013 года.
^ «Алгоритм в любое время — Справочник по вычислительной технике» . eLook.org . Архивировано из оригинала 12 декабря 2013 года.
^ Jump up to: ^а ^б Хорш и Пул, 1998 г.
^ Бендер, Эдвард А. (1996). Математические методы в искусственном интеллекте . Уайли. ISBN 978-0-8186-7200-2 .
^ Jump up to: ^а ^б ^с ^д Тейдже, Австралия; ван Хармелен, Ф. (2000). «Описание методов решения проблем с использованием профилей производительности в любое время» (PDF) . Материалы 14-й Европейской конференции по искусственному интеллекту . стр. 181–5.

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

Бодди, М.; Дин, Т. (1989). «Решение задач нестационарного планирования» . Материалы 11-й международной совместной конференции по искусственному интеллекту . Том. 2. С. 979–984. Университет Брауна CS-89-03.
Грасс, Дж.; Зильберштейн, С. (1996). «Инструменты разработки алгоритмов в любое время» . Бюллетень СИГАРТ . 7 (2 специальный выпуск, посвященный алгоритмам в любое время и планированию обсуждений): 20–27. дои : 10.1145/242587.242592 . S2CID 7670055 .
Хорш, MC; Пул, Д. (1998). «Алгоритм принятия решений в любое время в условиях неопределенности» (PDF) . Материалы Четырнадцатой конференции «Неопределенность в искусственном интеллекте» . стр. 246–255. arXiv : 1301.7384 . ISBN 978-1-55860-555-8 .
Хорвиц, Э.Дж. (март 1986 г.). Рассуждения о компромиссных выводах в мире ограниченных ресурсов (Технический отчет). Группа медицинской информатики, секция медицинской информатики, Стэнфордский университет. КСЛ-86-55.
Уоллес, Р.; Фрейдер, Э. (1995). «Алгоритмы в любое время для удовлетворения ограничений и проблем SAT» . Бюллетень ACM SIGART . 7 (2): 7–10. дои : 10.1145/242587.242589 . S2CID 8250394 .
Зильберштейн, С. (1993). Операционная рациональность посредством компиляции алгоритмов в любое время (доктор философии). Отдел компьютерных наук Калифорнийского университета в Беркли. UMX GAX94-08166.
Зильберштейн, Шломо (1996). «Использование алгоритмов Anytime в интеллектуальных системах» (PDF) . Журнал ИИ . 17 (3): 73–83.

[Hendler-1] Jump up to: ^а ^б ^с ^д ^и ^ж Хендлер, Джеймс А., изд. (2014) [1992]. Системы планирования искусственного интеллекта: материалы первой конференции (AIPS 92) . Эльзевир. ISBN 978-0-08-049944-4 .

[Zilberstein-2] Jump up to: ^а ^б ^с Зильберштейн 1996 г.

[Grass-3] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Грасс, Дж. (1996). «Рассуждения о распределении вычислительных ресурсов. XRDS: Перекресток» . Журнал ACM для студентов . 3 (1): 16–20. дои : 10.1145/332148.332154 . S2CID 45448244 .

[FOLDOC-4] Алгоритм в любое время из Бесплатного онлайн-словаря вычислений (FOLDOC)

[umich-5] «Алгоритмы в любое время» . Когнитивные архитектуры . Лаборатория искусственного интеллекта Мичиганского университета. Архивировано из оригинала 13 декабря 2013 года.

[elook-6] «Алгоритм в любое время — Справочник по вычислительной технике» . eLook.org . Архивировано из оригинала 12 декабря 2013 года.

[Horsch-7] Jump up to: ^а ^б Хорш и Пул, 1998 г.

[Bender-8] Бендер, Эдвард А. (1996). Математические методы в искусственном интеллекте . Уайли. ISBN 978-0-8186-7200-2 .

[Teije-9] Jump up to: ^а ^б ^с ^д Тейдже, Австралия; ван Хармелен, Ф. (2000). «Описание методов решения проблем с использованием профилей производительности в любое время» (PDF) . Материалы 14-й Европейской конференции по искусственному интеллекту . стр. 181–5.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]