Алгоритм решения лабиринта. Сложные лабиринты

Question

Я нашел несколько алгоритмов для решения лабиринтов. Те, которые достаточно просты, подходят только в тех случаях, когда выход находится за внешней границей (Wall-follower, pledge ...).

Существуют ли более сложные алгоритмы для случаев, когда формы границ случайны, стоимость зон неравна и выход может быть где-то внутри лабиринта? (кстати, все элементы квадратичны)

Обновление : Кроме того, мы не знаем, как выглядит лабиринт, и видим только определенную область.

Answer 1

Если вы имеете в виду «нормальные» двухмерные лабиринты, подобные тем, которые можно найти на бумаге, вы можете решить их , используя анализ изображений .Однако, если вы каким-то образом находитесь в в (2D / 3D) лабиринте и должны найти выход, вам, вероятно, следует применить некоторые методы машинного обучения .Это работает, если вы не знаете, как именно выглядит ваш лабиринт, иначе вы только «видите» его часть.

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

Описание:

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

Answer 2

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

Если стоимость равна - подойдет BFS - в противном случае вам понадобится что-то вроде алгоритма Дейкстры или * алгоритм [который в основном является информированным dijkstra ], чтобы найти кратчайший путь.

Чтобы использовать эти алгоритмы, вам нужно смоделировать лабиринт в виде графика: G=(V,E), где V = { all moveable squares in the maze } и E = {(u,v) | you can move from u to v in a sinlgle step }

Если у квадратов есть стоимость, пусть она будет cost(v) за каждый квадрат, вам понадобится весовая функция: w:E->R: определите ее как w(u,v) = cost(v)

Answer 3

Алгоритм залога полезен для лабиринтов, о которых вы говорите.Он состоит из:

Выбор направления, если вы знаете общее направление к цели, но случайное направление подойдет.Допустим, вы выбрали Север.

Идите в этом направлении, пока не столкнетесь с препятствием.

Следуйте за препятствием, следя за тем, как сильно вы поворачиваете.Например, отправляясь на север, вы наталкиваетесь на стену Восток-Запад.Вы поворачиваете на восток (90d) и следуете за стеной, когда она поворачивает на юг (180d), на запад (270d) и на север (360d).Вы не прекращаете следовать за стеной до тех пор, пока сумма, которую вы повернули, не станет равной 0. Таким образом, вы продолжаете следовать, поворачивая на запад (270d - в противоположном направлении), на юг (180d), восток (90d) и, наконец, на север (0d),Теперь вы можете перестать следовать.

Делайте это каждый раз, когда вы сталкиваетесь с препятствием.В конце концов вы доберетесь до северной части лабиринта.Если вы все еще не нашли цель, потому что выбрали неверное направление, попробуйте еще раз с Востоком или Югом или в любом направлении, ближайшем к цели.