Ученые представили алгоритм L-NAMOA* для ускорения многокритериального поиска путей

Группа ученых представила новый алгоритм L-NAMOA* для решения задачи многокритериального поиска кратчайших путей (MOSP). Работа опубликована на arXiv и описывает способ интеграции многозначных эвристик с методами снижения размерности, что ранее было нетривиальной задачей.

Традиционные алгоритмы MOSP используют однозначные эвристики, которые дают нижнюю границу стоимости, но не отражают структуру компромиссов Парето-фронта. Многозначные эвристики (MVH) предоставляют множественные оценки, улучшая навигацию, но их сочетание со снижением размерности (DR) нарушает инварианты упорядочивания, делая поиск некорректным.

Авторы сначала формализовали проблему и предложили базовый алгоритм NAMOA*_dr-mvh, восстанавливающий корректность за счет ограничений на эвристики. Однако его практическая применимость ограничена. Главное достижение — алгоритм L-NAMOA*_dr-mvh, который использует «ленивый» оптимистичный подход к снижению размерности. Он динамически обнаруживает и исправляет локальные нарушения порядка, сохраняя точность при допустимой многозначной эвристике.

Тестирование на различных бенчмарках показало, что L-NAMOA*_dr-mvh не уступает лучшим современным алгоритмам MOSP, а в некоторых случаях достигает ускорения более чем в 10 раз. Эффект особенно заметен, когда дополнительная информация от MVH позволяет сильнее отсекать неперспективные варианты.

Новый алгоритм может найти применение в логистике, робототехнике, сетевом планировании и других областях, где требуется учитывать несколько противоречивых критериев, таких как время, стоимость и риск.

Исследование доступно в виде препринта на arXiv и в настоящее время проходит рецензирование.