Есть лабиринт (нарисован на клетчатой бумаге/стенки --- вдоль линий бумаги/выход --- какое-то поле на бумаге)
Известно
1. его размер = N (пусть он в квадрате N*N)
2. из каждой точки есть выход из лабиринта
В какой-то точке лабиринта находиться робот.
Он исполняет программу из следующих команд:
1. пойти направо, если можно
2. пойти налево, если можно
3. пойти прямо, если можно
4. пойти назад, если можно
Вопрос. Существует ли для заданного N программа длины C(N) < \infty:
что робот, исполняя эту программу, гарантированно выйдет из лабиринта.
P.S. Робот не может определить есть ли рядом с ним стенка, если он попытается пойти на стенку, то
не сдвинется с места, но об этом не узнает...
Уточни пожалуйста несколько моментов:
1) Вокруг лабиринта по периметру квадрата гарантировано стоит стенка?
2) Одна и та же программа должна выводить из любой стартовой точки?
3) Выводить это значит проводить робота в процессе выполнения черех заданную клетку x0,y0?
4) Правильно ли я понял, что у робота есть текущее направление взгляда (начальное задано или не задано?) и потом при командах направо, налево, назад оно меняется. Т.е. вот такой путь если робот изначально стоит в нижнем левом углу и смотрит вправо, кодируется последовательностью {вперёд, налево, направо}, а обратный ход потом будет {назад, налево, направо}?
И ещё вопросы:
5) Спректирован ли лабиринт так, что из каждой точки лабиринта можно найти выход по алгоритму "придерживаться левой стенки"?
6) Известна ли программе схема лабиринта и точка выхода, или программа знает лишь о размере лабиринта?
Представляется, что наиболее простое решение — это случайное блуждание. Размер программы фиксирован, а за время меньшее infinity, робот точно добредёт до выхода ...
Здравствуйте, KonstantinA, Вы писали:
KA>Он исполняет программу из следующих команд: KA>1. пойти направо, если можно KA>2. пойти налево, если можно KA>3. пойти прямо, если можно KA>4. пойти назад, если можно
KA>P.S. Робот не может определить есть ли рядом с ним стенка, если он попытается пойти на стенку, то KA>не сдвинется с места, но об этом не узнает...
Если это исчерпывающий набор команд, то, имхо, вряд ли.
Абсолютно слепой робот тычется куда попало безо всяких условий.
Хотя бы возможность ветвления по результатам диагностики нужна...
Впрочем, можно дать оценку "длина бороды по Нильсу Бору" (скорость света * возраст )
Число мест для перегородок в лабиринте W = 2*N*(N+1). O(W)=O(N^2)
Число разных лабиринтов не превосходит L = 2^W. O(L) = O(exp N^2). На самом деле, существуют лабиринты без выхода, например, со всеми перегородками; тривиальные лабиринты с большими залами без перегородок... Наверное, нужно их исключать...
Число различных стартовых позиций P = N^2. O(P*L) = O(exp (N^2 log N)).
Длина пути выхода не превышает T = N^2. O(P*L*T) = O(exp (N^2 log N)).
Абсолютно неоптимизированная программа для абсолютно слепого робота представляет собой склейку из оптимальных программ выхода из каждой точки любого алгоритма.
Вполне конечный размер получается: С = (N^4)*(2^N^2).
M>1) Вокруг лабиринта по периметру квадрата гарантировано стоит стенка?
да M>2) Одна и та же программа должна выводить из любой стартовой точки?
да M>3) Выводить это значит проводить робота в процессе выполнения черех заданную клетку x0,y0?
да M>4) Правильно ли я понял, что у робота есть текущее направление взгляда (начальное задано или не задано?) и потом при командах направо, налево, назад оно меняется.
если хочется, можно считать и так M>Т.е. вот такой путь если робот изначально стоит в нижнем левом углу и смотрит вправо, кодируется последовательностью {вперёд, налево, направо}, а обратный ход потом будет {назад, налево, направо}?
вообще говоря обратный путь неясен, если неизвестна конфигурация. Так, если перед нами стенка, то обратный к "пойти прямо" --- "ничего не делать"
M>5) Спректирован ли лабиринт так, что из каждой точки лабиринта можно найти выход по алгоритму "придерживаться левой стенки"?
нет M>6) Известна ли программе схема лабиринта и точка выхода, или программа знает лишь о размере лабиринта?
только размер
M>Представляется, что наиболее простое решение — это случайное блуждание. Размер программы фиксирован, а за время меньшее infinity, робот точно добредёт до выхода ...
а все-таки хочется что-то неслучайное
Здравствуйте, Кодт, Вы писали:
К>Если это исчерпывающий набор команд, то, имхо, вряд ли.
Да нет можно...
Важен не размер программы, а ее существование.
К>Абсолютно неоптимизированная программа для абсолютно слепого робота представляет собой склейку из оптимальных программ выхода из каждой точки любого алгоритма.
Почти правда, но не совсем точно. Для простоты рассмотрим фиксированный лабиринт. Пусть в нем точки 1,...,N и программы P_1 ... P_N --- выводят соответствующую точку из лабиринта. Тогда программа P = P_N * P_{N-1} * ... * P_1 не обязана выводить все точки из лабиринта. Например, может случиться, что P_1( 2 ) = 1; P_2(1) = ... = P_N(1) = 1; Тогда 2 не выведется.
Здравствуйте, Кодт, Вы писали:
К>Впрочем, можно дать оценку "длина бороды по Нильсу Бору" (скорость света * возраст )
К>Абсолютно неоптимизированная программа для абсолютно слепого робота представляет собой склейку из оптимальных программ выхода из каждой точки любого алгоритма.
Я думаю, на это и задачка, но проблема в том, как вернуться назад в ту же точку! Или узнать где ты сейчас.
Т.е. ты сейчас идёшь в предположении, что идёшь отсюда, а выполнив этот кусок, должен взять следующий, но отсюда же, а ты уже в другом месте, так и будешь за своей тенью гоняться.
Сначала докажем следующее утверждение.
Если нам известно расположение стен и точки выхода, то мы можем написать маршрут, приводящий к цели, независимо от того, где изначально находится робот.
Для этого сначала предположим, что он находится в левом верхнем углу. Для этого случая мы вполне можем (зная позицию стен и цели) написать нужную последовательность шагов к цели P_00. Если мы не дошли, то значит неверно предположили стартовое положение. Предполагаем следующее исходное положение — точку x=0, y=1 и ищем, как из неё добраться до цели. Но я напомню, что мы уже выполнили программу P_00. Поэтому, если мы и находились раньше в точке (0,1), то теперь уже находимся в точке (0,1)+P_00 и писать путь мы должны из этой точки. Если нас и на этот раз постигнет неудача, то мы будем искать путь из первоначальной точки (0,2) т.е. текущей (0,2)+P_00+P_01. И так далее. Рано или поздно мы переберём все точки и так как где то мы в начале находились, наткнёмся на верный маршрут.
Ну а теперь совсем просто.
Раз у нас есть супер-программа, выводящая из любой точки при заданном расположении стен и цели, то выполненная для каждой комбинации того и другого, она выведет нас и для любого лабиринта.
Дадим оценку длины программы в шагах для квадратного лабиринта со стороной N.
Длина супермаршрута очевидно не более чем N^3.
Это ещё надо умножить на число позиций для выхода N^2 и число конфигураций стен 2^(2N(N-1))
Итого длина универсального маршрута, гарантировано выводящего из квадратного лабиринта со стороной N
L(N) = N^5 * 2^(2N(N-1))
Для N=1 формула даёт, как и ожидалось, L=1. А вот уже для N=2 L=512.
Так что я, пожалуй, поленюсь выписывать даже первую нетривиальную последовательность
Здравствуйте, Pushkin, Вы писали:
P>Сначала докажем следующее утверждение. P>Если нам известно расположение стен и точки выхода, то мы можем написать маршрут, приводящий к цели, независимо от того, где изначально находится робот.
P>Для этого сначала предположим, что он находится в левом верхнем углу. Для этого случая мы вполне можем (зная позицию стен и цели) написать нужную последовательность шагов к цели P_00. Если мы не дошли, то значит неверно предположили стартовое положение. Предполагаем следующее исходное положение — точку x=0, y=1 и ищем, как из неё добраться до цели. Но я напомню, что мы уже выполнили программу P_00. Поэтому, если мы и находились раньше в точке (0,1), то теперь уже находимся в точке (0,1)+P_00 и писать путь мы должны из этой точки. Если нас и на этот раз постигнет неудача, то мы будем искать путь из первоначальной точки (0,2) т.е. текущей (0,2)+P_00+P_01. И так далее. Рано или поздно мы переберём все точки и так как где то мы в начале находились, наткнёмся на верный маршрут.
Не уверен, что это правильно.
Мы же применяем некоторую последовательность алгоритмов к некоторой последовательности наших местоположений.
Я вполне допускаю, что для некоторых лабиринтов возможна ситуация, что:
применение любого
неправильного алгоритма к текущему местоположению — не приводит нас к выходу.
Тогда, чтобы найти выход, в нашей последовательности алгоритмов, необходимо как минимум одно совпадение алгоритма и местоположения. Это не доказано.
Здравствуйте, mrhru, Вы писали:
M>Здравствуйте, Pushkin, Вы писали:
P>>Сначала докажем следующее утверждение. P>>Если нам известно расположение стен и точки выхода, то мы можем написать маршрут, приводящий к цели, независимо от того, где изначально находится робот.
P>>Для этого сначала предположим, что он находится в левом верхнем углу. Для этого случая мы вполне можем (зная позицию стен и цели) написать нужную последовательность шагов к цели P_00. Если мы не дошли, то значит неверно предположили стартовое положение. Предполагаем следующее исходное положение — точку x=0, y=1 и ищем, как из неё добраться до цели. Но я напомню, что мы уже выполнили программу P_00. Поэтому, если мы и находились раньше в точке (0,1), то теперь уже находимся в точке (0,1)+P_00 и писать путь мы должны из этой точки. Если нас и на этот раз постигнет неудача, то мы будем искать путь из первоначальной точки (0,2) т.е. текущей (0,2)+P_00+P_01. И так далее. Рано или поздно мы переберём все точки и так как где то мы в начале находились, наткнёмся на верный маршрут.
M>Не уверен, что это правильно. M>Мы же применяем некоторую последовательность алгоритмов к некоторой последовательности наших местоположений.
Здесь вся фишка в выделенном фрагменте.
Мы последовательно предполагаем, где мы находились в самом начале, и ищем путь к выходу из той точки (текущей), где мы оказались бы к настоящему моменту, выполнив всё, что выполнили до сих пор (исходя из наших предыдущих предположений). Из любой точки лабиринта выход гарантированно есть (по условию), значит и из текущей он всегда есть!
Обрати внимание, текущая пересчитывается полностью (!) заново в момент перехода к следующему предположению о старте, а не просто нарастает. Она находится как прибавление к новой стартовой точке всей последовательности наших предыдущих действий. Т.е. мы находим, куда бы мы попали сейчас, после всех наших совершенно как выяснилось неверных шатаний, если предположить, что мы были в самом начале вот здесь. И из этой уже точки, куда нас занесло, ищем выход. Он гарантированно есть.
Здравствуйте, Pushkin, Вы писали:
P>Дадим оценку длины программы в шагах для квадратного лабиринта со стороной N. P>Длина супермаршрута очевидно не более чем N^3.
P>Это ещё надо умножить на число позиций для выхода N^2 и число конфигураций стен 2^(2N(N-1)) P>Итого длина универсального маршрута, гарантировано выводящего из квадратного лабиринта со стороной N P>L(N) = N^5 * 2^(2N(N-1))
Для конкретного лабиринта (а таких, как известно, не более 2^(2N*(N-1)) ) предположим, что робот находится в точке (x1,y1).
Напишем программу, заставляющую его дойти до точки (x2,y2), где, предположительно, есть выход. Длина пути — не более O(N^2).
Умножим на число стартовых (N^2) и стоповых (O(N) -- на периметре, или N^2 -- в недрах) точек — получим O(N^5) или O(N^6).
Однако, это довольно непродуктивно: робот игнорирует промежуточные точки пути, а ведь в них тоже может быть выход!
Напишем программу, по которой робот из точки (x1,y1) добирается до всех возможных точек выхода.
Затрудняюсь дать оценку, но очевидно, что она лежит между O(N^2) и O(N^4). Возможно, там будет O(N^2*log N) (задача обхода дерева с N^2 узлами).
Ну, и, как обычно, помножим на число стартовых точек и на число лабиринтов.
P>Для N=1 формула даёт, как и ожидалось, L=1. А вот уже для N=2 L=512. P>Так что я, пожалуй, поленюсь выписывать даже первую нетривиальную последовательность
Для N=2 есть простое решение.
Лабиринт (правильный ) может быть одним из 4:
+---+---+ +---+---+ +---+---+ +---+---+
| a b | | | | | | | |
+ + + +---+ + + + + + +---+
| c | d | | | | | | |
+---+---+ +---+---+ +---+---+ +---+---+
Из любой ячейки можно достичь любой другой, выполнив программу
ВВЕРХ ВЛЕВО ВНИЗ ВПРАВО ВЛЕВО ВВЕРХ ВПРАВО ВНИЗ
то есть — полный круг по часовой, затем против часовой стрелки.
Здравствуйте, Кодт, Вы писали:
P>>Длина супермаршрута очевидно не более чем N^3. К>Напишем программу, заставляющую его дойти до точки (x2,y2), где, предположительно, есть выход. Длина пути — не более O(N^2). К>Умножим на число стартовых (N^2) и стоповых (O(N) -- на периметре, или N^2 -- в недрах) точек — получим O(N^5) или O(N^6).
Да, тут я одно N потерял. Длина супермаршрута N^4.
К>Однако, это довольно непродуктивно: робот игнорирует промежуточные точки пути, а ведь в них тоже может быть выход! К>Напишем программу, по которой робот из точки (x1,y1) добирается до всех возможных точек выхода. К>Затрудняюсь дать оценку, но очевидно, что она лежит между O(N^2) и O(N^4). Возможно, там будет O(N^2*log N) (задача обхода дерева с N^2 узлами).
Клёво!
Но для двоичного дерева с K узлами длина пути L(K) != K*logK
Легко написать для полного дерева рекуррентную формулу
Итак для полного двоичного дерева мы имеем линейный рост!
Для совсем неполного дерева, когда всё выстроилось в одну ветку, длина
L(k)=k-1
Разумно предположить, что и для любого дерева длина полного обхода растёт не сильнее чем число узлов. Это легко доказать по индукции — если для любого дерева с k узлами длина обхода не более чем 2k, то дерево с k+1 узлом очевидно можно обойти за 2k+2=2*(к+1) шагов (сходив от ближайшего родителя добавленного вниз-вверх).
К>Ну, и, как обычно, помножим на число стартовых точек и на число лабиринтов.
Итоговая оценка 2*N^4*2^(2N*(N-1))
L(2) снова после всех поправок оказалась 512
К>Из любой ячейки можно достичь любой другой, выполнив программу К>ВВЕРХ ВЛЕВО ВНИЗ ВПРАВО ВЛЕВО ВВЕРХ ВПРАВО ВНИЗ К>то есть — полный круг по часовой, затем против часовой стрелки.
Гениально
Но ведь и у человека не бывает бороды длиной в 100 световых лет
К>Из любой ячейки можно достичь любой другой, выполнив программу К>ВВЕРХ ВЛЕВО ВНИЗ ВПРАВО ВЛЕВО ВВЕРХ ВПРАВО ВНИЗ К>то есть — полный круг по часовой, затем против часовой стрелки.
взять второй лабиринт и из ячейки "D" попасть в ячейку "C"
у меня не получилось
К>>Из любой ячейки можно достичь любой другой, выполнив программу К>>ВВЕРХ ВЛЕВО ВНИЗ ВПРАВО ВЛЕВО ВВЕРХ ВПРАВО ВНИЗ К>>то есть — полный круг по часовой, затем против часовой стрелки.
P>взять второй лабиринт и из ячейки "D" попасть в ячейку "C" P>у меня не получилось
Результаты для Пушкина (только длина, если надо, приведу и последовательности, просто с этим трудности).
N=4 L=20
N=5 L=44
Об алгоритме(ах) поиска.
Я использовал в различных сочетания три базовых алгоритма поиска пути:
1. Полный последовательный поиск в глубину.
Имеем префикс p, не являющийся решением. Дополняем его суффиксами длиной 1 (L, U, R, D) и проверяем каждый из четырех вариантов. Если среди них нет решения, увеличиваем длину суффикса до двух и перебираем 16 вариантов. И так продолжаем до тех пор, пока длина префикса+длина суффикса не превысит длину самого короткого решения.
Чрезвычайно долго, особенно если префикс короткий. Однако если решение есть, его не пропустишь. Этот алгоритм является самым быстрым алгоритмом получения всех решений, начинающихся с данного префикса.
2. Поиск в глубину с возвращением.
Имеем префикс p, не являющийся решением. Дополняем его суффиксами длиной 1 (L, U, R, D) и проверяем каждый из четырех вариантов. Повторяем данный процесс для каждой из последовательности p+'L', p+'U', p+'R', p+'D'. В каком порядке выполняеть поиск для этих четырех новых последовательностей — большой вопрос. Жадный алгоритм.
После выполнения программы в каждом лабиринте посещено (как минимум по одному разу) некоторое количество клеток (visitcount). Критерием выбора нового префикса для продолжения поиска выберем как раз суммарную величину visitcount для каждого лабиринта. И каким бы очевидным и естественным не казался этот критерий, основанный на нем алгоритм поиска сам себе подкладывает свинью. В определенный момент возникает ситуация, когда ни один из четырех вариантов развития не увеличивает visitcount. Это не значит, что они бесперспективны. Быть может, один из них через две итерации даст решение. Но какой именно? Наш критерий ветвления оказался бессилен. Что выбрать? L, U, R или D. Ну давайте всегда выбирать их именно в указанном порядке. То есть начнем с L. И вот тут я сталкивался с ситуацией, когда после нескольких таких выборов L все роботы во всех лабиринтах упиральсь в стенки, и прога падала от переполнения стека.
Я использовал такой выход: когда 2 раза подряд не менялся visitcount, я запускал Полный последовательный поиск в глубину.
3. Поиск в ширину.
Имеем некоторое множество префиксов (быть может, разной длины). Выбираем из них самый перспективный, нагромождаем на него L, U, R, D и все четыре варианта добавляем к множеству префиксов, а исходный префикс удаляем оттуда. Что делать, когда будет найдено решение? Ну неплохо бы провести прореживание данного множества, удаляя оттуда все префиксы большей длины, чем найденное решение.
Как выбирать наиболее перспективный префикс? Не знаю, хотя вариантов перебрал много.
Этот метод жрет память, как голодный косолапый мишка после зимней спячки. Здесь я использовал такой прием: когда число элементов этого множества достигает некоторого предельного значения, берем оттуда несколько наиболее перспективных и ищем, начиная с них, в глубину. Если поиск окажется удачным, произведем прореживание элементов множества.
Вообщем, это все brute force. Никакого более-менее аналитического подхода предложить не могу.
Т.е. существует последовательность длины 20,
гарантированно выводящая из всех лабиринтов площади 4?
А я-то, дурак, свой перебор на 19-и выключил
RS>Вообщем, это все brute force. Никакого более-менее аналитического подхода предложить не могу.
Вообще очень интересно, если вот сейчас задать случайный лабиринт площади 20 и пообещать нам всем, таким умным, что первая вышедшая прога получит бакс, и так 100 раз... Не победит ли прога самого ленивого, который просто реализует случайные блуждания? Мне почему-то кажется, что если и не победит, то и лучше неё реально никто не напишет...
Евгений
)
Перекуём баги на фичи!
Длина супермаршрута N^4.
