Алгоритм в любое время - Anytime algorithm
В информатике алгоритм в любое время - это алгоритм, который может вернуть действительное решение проблемы, даже если оно было прервано до завершения. Ожидается, что алгоритм будет находить все лучшие и лучшие решения, чем дольше он работает.
Большинство алгоритмов работают до завершения: они дают единственный ответ после выполнения некоторого фиксированного количества вычислений. Однако в некоторых случаях пользователь может пожелать прервать алгоритм до его завершения. Например, объем требуемых вычислений может быть значительным, и может потребоваться перераспределение вычислительных ресурсов. Большинство алгоритмов либо работают до завершения, либо не предоставляют полезной информации о решении. Однако в любое время алгоритмы могут возвращать частичный ответ, качество которого зависит от объема вычислений, которые они смогли выполнить. Ответ, сгенерированный алгоритмами в любое время, является приближением правильного ответа.
Имена
Алгоритм в любое время может также называться «алгоритмом прерывания». Они отличаются от контрактных алгоритмов, которые должны заранее объявлять время; в алгоритме в любое время процесс может просто объявить о завершении.
Цели
Цель постоянных алгоритмов - дать интеллектуальным системам возможность получать результаты более высокого качества в обмен на время обработки. Они также должны быть гибкими во времени и ресурсах. Они важны, потому что искусственный интеллект или алгоритмы ИИ могут занять много времени для получения результатов. Этот алгоритм разработан для выполнения в более короткие сроки. Кроме того, они предназначены для лучшего понимания того, что система зависит и ограничена своими агентами и как они работают совместно. Примером может служить итерация Ньютона – Рафсона, применяемая для нахождения квадратного корня из числа. Другой пример, в котором используются алгоритмы в любое время, - это проблемы с траекторией, когда вы целитесь в цель; объект движется в пространстве, ожидая завершения алгоритма, и даже приблизительный ответ может значительно повысить его точность, если будет дан заранее.
Что делает алгоритмы в любое время уникальными, так это их способность возвращать множество возможных результатов для любого заданного входа. Алгоритм в любое время использует множество четко определенных показателей качества для отслеживания прогресса в решении проблем и распределенных вычислительных ресурсов. Он продолжает поиск наилучшего возможного ответа за то время, которое ему отведено. Он может не работать до завершения и может улучшить ответ, если ему разрешено работать дольше. Это часто используется для задач с большим набором решений. Как правило, это не дает полезной информации, если не разрешено закончить. Хотя это может показаться похожим на динамическое программирование , разница в том, что оно настраивается путем случайных корректировок, а не последовательного.
Алгоритмы в любое время разработаны таким образом, чтобы можно было сказать, что нужно остановиться в любой момент, и они вернули лучший результат, который он нашел до сих пор. Вот почему он называется прерываемым алгоритмом. Некоторые алгоритмы в любое время также поддерживают последний результат, поэтому, если им дается больше времени, они могут продолжить с того места, где они остановились, чтобы получить еще лучший результат.
Деревья решений
Когда принимающий решение должен действовать, должна быть некоторая двусмысленность. Также должно быть какое-то представление о том, как разрешить эту двусмысленность. Эта идея должна быть преобразована в диаграмму состояния в действие.
Профиль производительности
Профиль производительности оценивает качество результатов на основе входных данных и количества времени, отведенного алгоритму. Чем точнее оценка, тем скорее будет найден результат. Некоторые системы имеют большую базу данных, которая дает вероятность того, что результат является ожидаемым. Важно отметить, что один алгоритм может иметь несколько профилей производительности. В большинстве случаев профили производительности строятся с использованием математической статистики с использованием репрезентативных случаев. Например, в задаче коммивояжера профиль производительности был сгенерирован с использованием определенной пользователем специальной программы для генерации необходимой статистики. В этом примере профиль производительности - это отображение времени на ожидаемые результаты. Это качество можно измерить несколькими способами:
- определенность: где вероятность правильности определяет качество
- точность: где граница ошибки определяет качество
- специфичность: где количество деталей определяет качество
Предпосылки алгоритма
Первоначальное поведение: в то время как некоторые алгоритмы начинаются с немедленных предположений, другие используют более расчетный подход и имеют период запуска, прежде чем делать какие-либо предположения.
- Направление роста: как качество «вывода» или результата программы зависит от количества времени («времени выполнения»).
- Скорость роста: величина увеличения с каждым шагом. Меняется ли он постоянно, например, при сортировке пузырьков, или меняется непредсказуемо?
- Конечное условие: необходимое время выполнения