Самый быстрый путь для обхода всех заданных узлов

Question

Я пишу простую игру и сейчас занимаюсь искусственным интеллектом.NPC получает список своих «точек интереса», которые ему нужно посетить.Каждая точка имеет координату на карте.Мне нужно найти самый быстрый путь для персонажа, чтобы посетить все из указанных точек.

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

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

Спасибо завперед.

Answer 1

Это очень похоже на задачу коммивояжера , хотя я не буду пытаться доказать эквивалентность на практике.TSP является NP-полной, что означает, что решение проблемы может быть непрактичным, в зависимости от количества точек интереса.Существуют алгоритмы аппроксимации, которые могут оказаться более полезными.

Answer 2

Я бы использовал алгоритм вроде: алгоритм муравья.

Answer 3

См. Предыдущий пост о обходах дерева:

Алгоритм обхода дерева для структур каталогов с большим количеством файлов

Answer 4

Не непосредственно в точке, но то, что я делал в эмуляторе MMO, заключалось в том, чтобы хранить индексы путевых точек вместе с остальными данными маршрутизации.Если ваше требование заключается в демонстрации решений TSP, игнорируйте это.Если нет, то стоит рассмотреть IMO.

В моем случае это было наилучшее решение, так как в противном случае сервер мог бы иметь потенциально сотни (повторных) порождений мобов и вместе со всей остальной логикой ИИ пришлось бы записывать циклывычислительная логика маршрута.