Вычислить путь максимального покрытия в таблице занятости

Question

Я реализую базового робота, который использует алгоритм SLAM для создания сетки занятости своей среды.Это очень просто, без вероятностного аспекта, просто с перечислением пустых, занятых, неизведанных, недоступных и т. Д.

Мне было интересно, существует ли хорошо известный алгоритм для поиска кратчайшего пути, необходимого для посещения всехячейки сетки один раз (это Пылесос! ).Это проблема коммивояжера?

Я исследовал пару решений, основанных на графиках, например, нахождение гамильтоновых циклов, но мне было интересно, есть ли что-нибудь, что эффективно работало бы с сетками напрямую.

Сетка будет около 250x250 ячеек..

Спасибо!

Answer 1

Просто подумал, что id добавил мое решение к этому оставшемуся без ответа вопросу - большинство алгоритмов, которые я опробовал, были слишком сложными в вычислительном отношении.Я остановился на приближении траектории максимального покрытия, которая была достаточно эффективно рассчитана с использованием алгоритма обратного волнового фронта .

Используя этот алгоритм, я смог построить путь максимального охвата массива ячеек сетки 250x250 примерно за 5 секунд, что, безусловно, было приемлемо в моем сценарии.