pro.algorithms
Как можно найти кратчайший путь в лабиринте для пакмана, чтобы
съесть все точки?
Я использую А* с эвристической функцией которая находит расстояние в лабиринте между двумя самыми удаленными точками и расстояние от текущей позиции пакмана до ближайшего из этих точек. Затем суммирует оба расстояния и возвращает. Для маленького лабиринта работает достаточно быстро, но когда лабиринт большой и есть много точек, уже не справляется.
ПС: на лабиринте находятся только пакман и точки(фрукты)
6 ответов
Это ж коммивояжер (TSP)
Это ж коммивояжер (TSP)
по идее одним им не обойтись - надо сначала узнать расстояние между точками
Это ж коммивояжер (TSP)
А вроде обход графа в ширину
А вроде обход графа в ширину
С чего вдруг обход, если нам нужно найти путь с минимальной суммой длин рёбер, проходящий через каждую вершину
С чего вдруг обход, если нам нужно найти путь с ми...
Ой, да, вы правы, только встал, прочитал каким-то чудом, что ему нужно найти выход из лабиринта
Миршохид
Окилбеков
Автор вопроса
решил с помощью генетического алгоритма, даже если не самый оптимальный путь, но достаточно короткий, и находится в быстрое время когда есть много точек в лабиринте
Похожие вопросы
Обсуждают сегодня