Новый метод поиска решений в комбинаторной геометрии: MCTS с учётом геометрии

Разработан метод MCTS для решения экстремальных задач комбинаторной геометрии: он учитывает геометрические ограничения и использует симметрии для ускорения поиска решений, что позволило получить новые результаты по ряду задач.

Исследователи предложили новый подход для решения сложных задач комбинаторной геометрии — систему поиска по дереву Монте-Карло с учётом геометрии (MCTS). Традиционные методы часто сталкиваются с проблемой «комбинаторного взрыва» и другими ограничениями, а новая система позволяет строго соблюдать геометрические условия, постепенно уточняя возможные варианты действий. Авторы использовали геометрические симметрии, чтобы ускорить поиск подходящих конфигураций точек на сетке. В ходе экспериментов они добились новых результатов по пяти из шести рассмотренных задач, в том числе нашли новые конфигурации для задачи Max-N3IL и определили новые верхние границы для задачи с наименьшим полным набором.