В любое время А*
В информатике — A* это семейство вариантов алгоритма поиска A* . Как и другие алгоритмы в любое время , он имеет гибкую временную стоимость, может возвращать допустимое решение задачи поиска пути или обхода графа , даже если оно прерывается до завершения, путем генерации быстрого неоптимального решения перед его постепенной оптимизацией. Эта способность быстро генерировать решения сделала его привлекательным для поисковых сайтов и проектов искусственного интеллекта .
Предыстория и история
[ редактировать ]Выполнение оптимального алгоритма A* до завершения является слишком дорогостоящим для многих целей. Оптимальностью A* можно пожертвовать, чтобы сократить время выполнения за счет увеличения эвристики, как в случае с взвешенным A* 1970 года. [1] Итеративное уменьшение степени «раздутости» эвристики обеспечивает простой алгоритм в любое время (ATA*, 2002), но это повторяет предыдущую работу. [2] о более эффективной и ограниченной ошибками версии, которая повторно использует результаты, Anytime Repairing A* ( ARA* ). В 2003 году сообщалось [3] [4] Динамическая (в смысле D* ) модификация ARA*, Anytime Dynamic A* ( ADA* ), была опубликована в 2005 году. Она сочетает в себе аспекты D* Lite и ARA*. [5] Anytime Weighted A* (1997, 2007) аналогичен взвешенному A*, за исключением того, что он продолжает поиск после нахождения первого решения. Он находит лучшие решения итеративно и в конечном итоге находит оптимальное решение без повторения предыдущей работы, а также предоставляет границы ошибок на протяжении всего поиска. [6] [7] Рандомизированная взвешенная оценка A* (2021 г.) ввела рандомизацию в систему взвешенная A* в любое время и продемонстрировала лучшую эмпирическую эффективность. [8]
Отличие от А*
[ редактировать ]
Алгоритм поиска A* может быть представлен функцией f( n ) = g( n ) + h( n ) , где n — последний узел на пути, g( n ) — стоимость пути от начального узла. до n , а h( n ) — эвристика, оценивающая стоимость самого дешевого пути от n до цели. В отличие от алгоритма A*, наиболее важной функцией алгоритма Anytime A* является то, что их можно остановить, а затем перезапустить в любое время. В любое время семейство алгоритмов A* обычно основывается на взвешенной версии поиска A*: где используется f w ( n ) = g( n ) + w × h( n ) , w > 1 , и выполняется поиск A* как обычно, что в конечном итоге происходит быстрее, поскольку расширяется меньше узлов. [1]
ATA* предполагает выполнение взвешенного A* несколько раз, при этом w каждый раз постепенно снижается до тех пор, пока w = 1, когда поиск просто становится простым A*. Хотя это может работать путем многократного вызова A* и отбрасывания всей предыдущей памяти, ARA* делает это, вводя способ обновления пути. [4] Начальное значение w определяет минимальное (первое) время выполнения ATA*.
Взвешенный в любое время A* превращает взвешенный A* в алгоритм в любое время следующим образом. [6] [7] Каждый целевой тест выполняется при создании узла, а не при его расширении, и текущее решение становится лучшим целевым узлом на данный момент. Если алгоритм не прерывается, поиск продолжается до тех пор, пока не будет найдено оптимальное решение. Во время поиска граница ошибки равна стоимости текущего решения c минус наименьшее значение f в открытом списке. Оптимальное решение обнаруживается, когда больше нет узлов с f( n ) ≤ c , остающихся открытыми, и в этот момент алгоритм завершается с c как стоимостью оптимального решения. В 2021 году было обнаружено, что при ограничении времени поиска взвешенный в любое время A * в среднем дает лучшие решения за счет простого случайного переключения веса после каждого расширения узла, чем за счет использования точно настроенного статического веса или постепенного снижения веса после каждого расширения. решение. [8]
Ссылки
[ редактировать ]- ^ Jump up to: а б Поль, Ира (1970). «Первые результаты о влиянии ошибки при эвристическом поиске». Машинный интеллект 5 . Издательство Эдинбургского университета. стр. 219–236. ISBN 978-0-85224-176-9 . ОСЛК 1067280266 .
- ^ Чжоу, Р.; Хансен, Э.А. (2002). Множественное выравнивание последовательностей с использованием A* (PDF) . Восемнадцатая национальная конференция по искусственному интеллекту. стр. 975–976. ISBN 978-0-262-51129-2 .
- ^ Лихачебв, Максим; Гордон, Джефф; Трун, Себастьян. ARA*: формальный анализ (PDF) (Технический отчет). Школа компьютерных наук Университета Карнеги-Меллон . Проверено 24 июля 2018 г.
- ^ Jump up to: а б Лихачев, Максим; Гордон, Джефф; Трун, Себастьян. ARA*: Anytime A* с доказуемыми границами субоптимальности (PDF) (технический отчет). Школа компьютерных наук Университета Карнеги-Меллона . Проверено 24 апреля 2018 г.
- ^ Краузе, Алекс (2005). «Anytime Dynamic A*: алгоритм перепланирования в любое время» . Материалы пятнадцатой Международной конференции по автоматизированному планированию и составлению графиков . стр. 262–271. ISBN 978-1-57735-220-4 .
- ^ Jump up to: а б Хансен, Э.А.; Зильберштейн, С.; Данильченко, В.А. (1997). Эвристический поиск в любое время: первые результаты (Технический отчет). Факультет компьютерных наук Массачусетского университета в Амхерсте. 97-50.
- ^ Jump up to: а б Чжоу, Р.; Хансен, Э.А. (2007). «Эвристический поиск в любое время». Журнал исследований искусственного интеллекта . 28 : 267–297. arXiv : 1110.2737 . дои : 10.1613/jair.2096 . S2CID 9832874 .
- ^ Jump up to: а б Бхатия, Абхинав; Свельято, Джастин; Зильберштейн, Шломо. «О преимуществах случайной корректировки взвешенной в любое время A*» . Материалы четырнадцатого международного симпозиума по комбинаторному поиску . Проверено 21 июля 2021 г.