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

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

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

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

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

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

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


algorithm maze
person mussorsky    schedule 09.04.2011    source источник
comment
Не могли бы вы подробнее рассказать, как это работает? Разрешено ли вам исследовать лабиринт столько, сколько вы хотите, но при этом вы должны найти оптимальное решение с точки зрения наименьшего количества поворотов? Или время, которое вы тратите на изучение лабиринта в поисках решения, тоже учитывается? Что вы можете предположить о лабиринте?   -  person templatetypedef    schedule 10.04.2011

Ответы (2)


arrow_upward
7
arrow_downward

Я думаю, вы можете сделать это, сначала найдя все точки, до которых можно добраться за 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

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

person julx    schedule 09.04.2011
comment
Это динамическое программирование. Вы можете делать это от начальной точки до начальной точки. Однако вам нужно заботиться не только о точках, но и о точках и направлении (состоянии). Вопрос в том, какие из указанных состояний достижимы с 1 RT, а какие состояния достижимы с 2 RT ... Обратное: из каких состояний я могу достичь цели за 1 RT?, Из каких состояний я могу достичь цели с 2 RT - person ysdx; 10.04.2011
comment
Ответ abeln лучше. - person Sergey Orshanskiy; 14.10.2013

arrow_upward
4
arrow_downward

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

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

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

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

person abeln    schedule 09.04.2011