Решение лабиринта со всех стартовых точек

Недавно я столкнулся с проблемой, которая заявила;
Предположим, что лабиринт с символами *, ., C. * представляет собой стены и ./C разрешены. Есть только одна точка, которая отмечена C. Теперь, когда бот стоит на любой из разрешенных точек, существует серия команд (например, LDDRU или LLLRRDU и т. Д.), Так что если бот начинается с любой допустимой точки, он проходит по крайней мере один раз через C.
Например:Решение лабиринта со всех стартовых точек

****** 
*.C..* 
**.*** 
*....* 
******

Команда: RLLURUU

Теперь я знаю, как решить лабиринт с помощью DFS/BFS (для кратчайшего пути). Но может ли кто-нибудь дать понять, как я буду продолжать такие проблемы?
РЕДАКТИРОВАТЬ: если следующий шаг в стену/внешний лабиринт, он игнорируется. И как обычно L IS LEFT R ПРАВИЛЬНО U IS UP D IS DOWN.

источник

2016-07-25 yobro97

Дальнейшее перемещение по горизонтали - 3 шага; так, например, например; LLL, вы можете быть только на трех позициях в сетке; после другого R вы можете находиться в трех положениях в вертикальном коридоре; после UU вы обязательно пропустили C. Итак, в общем: сделайте несколько ходов, которые уменьшают количество позиций, в которых вы могли бы находиться, а затем отслеживайте все ваши возможные роботы и делайте каждый проход через C, используя «если есть стена, то робот не двигается». Каждый раз, когда два возможных робота оказываются на одном и том же квадрате, удалите один из них. – m69

@ m69, спасибо за ответ. Но, чтобы быть более ясными, можете ли вы использовать приведенный пример и объяснить свою логику, приходящую на ответ ... спасибо! – yobro97

Существует 9 возможных позиций в 3 строках; после LLL любой робот находился бы в самом левом положении в своем ряду, так что теперь у вас есть только 3 возможных положения; после другого R, 3 робота будут находиться во втором левом положении (вертикальный коридор); после UU они все закончили бы на C. – m69

Эта проблема связана с понятием synchronizing words или порядков сброса для конечных автоматов. Вы можете представить себе создание автомата, где

каждое открытое пространство, плюс C, является состоянием;
Каждое состояние, отличное от C, переходит в себя для каждого перемещения, которое попадает в стену;
каждое состояние, отличное от С, переходит в соседнее открытое состояние в указанном направлении, если есть открытое пятно в этом направлении; и
состояние C переходит к себе на всех ходах.

Учитывая этот автомат, вы теперь ищете последовательность, которая принимает каждое состояние в состояние C, следовательно, соединение с синхронизирующими словами. Существует множество алгоритмов для поиска синхронизирующих слов, и любой из них может быть адаптирован для решения этой конкретной проблемы. Один из вариантов: build the power automaton from the original automaton и поиск пути от состояния начала до состояния C, который (я считаю) оказался теоретически оптимальной версией комментария, говорящей о сворачивании виртуальных роботов (в том, что он всегда найдет оптимальный путь.)

источник

2016-07-25 03:31:17 templatetypedef

«построить мощный автомат» - это экспоненциально, даже если мы строим только доступные узлы. Что-нибудь быстрее? Мне даже не нужно кратчайшее синхронизирующее слово. –

Вы связались с мобильной версией wikipedia. Пожалуйста исправьте. –

@JanDvorak О, извините, я не понимал, что вам не нужно кратчайшее решение. Конструкция энергетического автомата является наихудшей экспонентой для произвольных автоматов, но я не уверен, что конкретные автоматы в этом случае фактически вызовут ее. Мне придется подумать об этом. Существуют и другие подходы, которые, как известно, являются наихудшим полиномиальным временем, хотя я менее знаком с ними. – templatetypedef

Решение лабиринта со всех стартовых точек

ответ

Смежные вопросы