Лабиринт решает оптимальный алгоритм без левого поворота

Question

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

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

Для алгоритма обратного отслеживания я собирался использовать стек.Мой алгоритм будет выглядеть примерно так:

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

IМне было интересно, если кто-нибудь может указать мне в направлении оптимального алгоритма для этого.

Мне трудно думать о чем-то лучше, чем возвращение назад.

Answer 1

Я думаю, что вы можете сделать это, сначала найдя все точки, которые достижимы с 0 правыми поворотами.Затем всего 1 поворот направо и так далее.Вы можете использовать очередь для этого.Обратите внимание, что в n-й фазе у вас есть оптимальные решения для всех точек, которые могут быть достигнуты за n правых поворотов.Более того - любая еще не достигнутая точка достижима с> n точками или вообще не достижима.Чтобы достичь оптимальной временной сложности, вы должны использовать тот факт, что вам нужно искать новые достижимые точки только из тех достигнутых точек, которые имеют недостижимого соседа в соответствующем направлении.Поскольку у каждой точки есть только 4 соседа, вы будете искать ее только 4 раза.Вы можете реализовать это, поддерживая отдельный список для каждого направления D, содержащего все достигнутые точки с недостижимым соседом в этом направлении.Это дает вам временную сложность, пропорциональную площади лабиринта, которая пропорциональна размеру ваших входных данных.

Ниже я приведу графический пример:

 .  .  .  .  .  .   (0) .  .  .  .  .    0  1  1  1  1 (1)   0  1  1  1  1  1
 .  #######  .  .    0  ##########  .    0  ##########  .    0  ##########  2
 .  #  .  #  .  .    0  #  .  #  .  .    0  #  .  #  .  .    0  #  .  #  . (2)
 .  #  .  .  .  .    0  #  .  .  .  .    0  #  .  .  .  .    0  #  .  .  . (2)
 .  ####  .  #  .    0  ####  .  #  .    0  ####  .  #  .    0  ####  .  #  2
(.) .  .  .  .  .   (0) .  .  .  .  .    0  1  1  1  1  1    0  1  1  1  1  1

 0  1  1  1  1  1    0  1  1  1  1  1
 0  ##########  2    0  ##########  2
 0  #  .  #  3  2    0  #  4  #  3  2
 0  # (3) 3  3  2    0  #  3  3  3  2
 0  ####  .  #  2    0  ####  4  #  2
 0  1  1 (1) 1  1    0  1  1  1  1  1

( ) обозначаетдостигнуты точки с не достигнутым соседом

Answer 2

Постройте график, построив четыре узла для каждой позиции в лабиринте. Каждый узел будет соответствовать определенному направлению: N, S, E, W.

Там будут ребра между каждым узлом и не более, чем тремя из его соседних соседей: те, которые находятся "спереди", "сзади" и "справа" (если они существуют). Ребро, ведущее к узлу в «front» и «back», будет иметь вес 0 (поскольку длина пути не имеет значения), тогда как ребро к узлу в «right» будет иметь вес 1 (это то, что представляет стоимость правого поворота).

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

Хитрость для обработки весов ребра 0/1 заключается в использовании deque вместо стандартной реализации очереди. В частности, узлы, достигшие через грани веса 0, будут выдвигаться впереди deque, а узлы, достигаемые через грани веса 1, будут задвигаться сзади.