было показано, что существует последовательность шагов, выводящая из любого квадратного лабиринта со стороной N. Так как длина последовательности положительна, значит существует наикратчайшая такая последовательность. Наикратчайшая последовательность для лабиринта 1x1 тривиальна. По уже указанной ссылке можно найти вполне правдоподобную наикратчайшую последовательность для лабиринта 2x2.
Предлагаю конкурс. Победителю всеобщий почёт и уважение. Ну и баллы разумеется.
Найти кратчайшую последовательность для лабиринтов 3x3 и 4x4.
Лабиринт состоит из клеток.
Клетки собраны в квадрат NxN.
По границам квадрата гарантированная стенка.
Внутри квадрата по границам клеток тоже могут быть стенки.
Выход - некая неизвестная программе точка - любая среди N^2.
Внутренние стенки стоят так, что из любой точки можно пройти к выходу.
Команды для робота: (для простоты выбраны чуть иначе, чем в оригинальной задаче)
L - шаг влево.
R - шаг вправо
U - шаг вверх
D - шаг вниз
Если робот не может выполнить команду, он её не выполняет.
Нет средств узнать, выполнил ли робот команду.
Нет средств узнать, где сейчас находится робот.
Кто хочет, может писать генерирующую прогу. Кто хочет колдует с карандашом.
Ответы принимаются в виде последовательностей букв. Проверяются всеми желающими.
открылась новая блатная номинация 2x2, которая в отличие от старших собратьев легко решается тупейшим брутфорсом.
Имею честь представить высокому собранию научный результат.
Минимальная длина последовательности, гарантированно приводящей из любой точки лабиринта 2x2 в любую другую точку, равна 11. Всего существует 16 таких последовательностей, а с точностью до поворотов и отражений ровно 2.
LURDLULDRUL
URDLURLDRUL
Забавно, что хвост этих двух последовательностей совпадает, а голова лишь слегка сдвинута. В первой сильно преобладают команды L, во второй всё равномернее — лишь D слегка обижены.
нет нужды требовать, чтобы лабиринт был квадратным. Достаточно того, что в нём не более чем N клеток. Число возможных лабиринтов при этом конечно и доказательство
ничуть не меняется — как мы перебирали все расположения стенок в квадратном лабиринте, так мы можем и перебрать расположения стенок в лабиринтах всех форм.
Таким образом, открываются новые номинации — найти минимальную последовательность, выводяшую из любого лабиринта, содержащего не более 2,3,4 итд клеток. Наверняка это всё решится простым брутфорсом.
В случае с 4 клетками потребуется не менее 11 шагов (но может оказаться, что и более).
Первый нетривиальный случай — для лабиринта площадью 2 — никому не отдам.
Длина минимальной последовательности равна 4, и с точностью до поворотов и отражений она единственна:
Привет, Pushkin!
P>Предлагаю конкурс. Победителю всеобщий почёт и уважение. Ну и баллы разумеется. P>Найти кратчайшую последовательность для лабиринтов 3x3 и 4x4.
P>Команды для робота: (для простоты выбраны чуть иначе, чем в оригинальной задаче)
P>L - шаг влево.
P>R - шаг вправо
P>U - шаг вверх
P>D - шаг вниз
P>Если робот не может выполнить команду, он её не выполняет.
P>Нет средств узнать, выполнил ли робот команду.
P>Нет средств узнать, где сейчас находится робот.
P>
И, наконец, последняя и главная номинация!
Робот не знает размера лабиринта...
Робот стоит в клетке. Запускается алгоритм поиска в лабиринте площадью два (LURD). Попал? Нет. Тогда запускается алгоритм поиска в лабиринте площадью 4, начинающийся с уже пройденной комбинации! Например, LURDLULDRUL. Выход найден? Еще нет. Тогда запускаем алгоритм поиска выхода в лабиринте площадью 6, начинающийся с LURDLULDRUL.
И т.д. Если сможем, конечно.
Вопрос очевиден. Можно ли без потерь ходов объединить все алгоритмы?
Жизненность алгоритма так же не должна вызывать сомнения. Глядишь, и индеец Джо подольше прожил бы...
P>Первый нетривиальный случай — для лабиринта площадью 2 — никому не отдам. P>Длина минимальной последовательности равна 4, и с точностью до поворотов и отражений она единственна:
P>
P>LURD
P>
Молодец!
А теперь то же, но для площади 3.
(Небольшие подразмышления )
Вот небольшая подзадача к твоей задаче:
Построить все правильные лабиринты для заданного N.
А вот небольшое подрешение для этой подзадачи:
Перебираем все стенки и определяем правильность лабиринта (это моя сама придумала! ).
Для определения правильности — можно использовать волновой алгоритм, но это долго.
Быстрее — при установке очередной стенки достаточно (?) определять, что путь по стенкам, включая внешние, не образует циклов.
A>И, наконец, последняя и главная номинация! A>Робот не знает размера лабиринта...
И ещё две постноминации!
N+1: Робот находится в трехмерном лабиринте. К его командам LRUD добавляются еще две F и B...
N+2: Робот находится в N-мерном лабиринте и не знает его мерности. Команды имеют вид Move(K, {+1, -1}), где К — номер измерения. Если такого измерения нет или стоит стенка — робот об этом не узнает...
Здравствуйте, mrhru, Вы писали:
M>Вот небольшая подзадача к твоей задаче: M>Построить все правильные лабиринты для заданного N.
M>А вот небольшое подрешение для этой подзадачи: M>Перебираем все стенки и определяем правильность лабиринта (это моя сама придумала! ). M>Для определения правильности — можно использовать волновой алгоритм, но это долго. M>Быстрее — при установке очередной стенки достаточно (?) определять, что путь по стенкам, включая внешние, не образует циклов.
Да, про циклы, это хорошо. Но это всё на компе.
Мне интересно, можно ли ручками хоть как-то снизить оценку 2^(2N(N-1)) для числа всех правильных лабиринтов?
Здравствуйте, Apapa, Вы писали:
A>И, наконец, последняя и главная номинация! A>Робот не знает размера лабиринта...
К сожалению, в этом случае, минимальная последовательность гарантированного выхода бесконечна, и я не вижу, чем хуже случайное блуждание.
Можно ещё поставить вопрос так:
— случайным образом выбираем лабиринт площадью N
— какая последовательность в среднем будет выводить быстрее всего?
Совсем не факт, что та же, которая выводит гарантированно.
Здравствуйте, Pushkin, Вы писали:
P>Да, про циклы, это хорошо. Но это всё на компе. P>Мне интересно, можно ли ручками хоть как-то снизить оценку 2^(2N(N-1)) для числа всех правильных лабиринтов?
Можно. Отталкиваясь от этих циклов.
Если взять левую верхнюю клетку, то из 4-х возможных вариантов её стенок, один даёт неправильный лабиринт.
Уже сокращает длину бороды на четверть.
Учитываем остальные клетки по углам.
Потом переходим к боковым клеткам. Потом к внутренним.
Затем переходим к группам клеток 2х2, 2х3, 3х3...
Привет, Pushkin!
A>>Робот не знает размера лабиринта...
P>К сожалению, в этом случае, минимальная последовательность гарантированного выхода бесконечна, и я не вижу, чем хуже случайное блуждание.
Вопрос то как раз в этом! Если у нас оказалось поле 2х2, то по описанному выше алгоритму мы попали к выходу, при этом в начале мы проверили гипотезу о том, а не 2х1 ли оно.
Если робот не знает размер поля, то ему следует совместить гипотезы о разных размерах таким образом, чтобы попасть к выходу как можно быстрее. Очевидно, что если бы получилось соединить алгоритмы для разных размеров так, что все они идут с начала, то это и есть оптимальный алгоритм в этой ситуации.
К примеру, пусть робот не знает размер поля, но знает, что его стенки не более 2 в длину. Тогда ему естественно использовать такой оптимальный алгоритм нахождения выхода на поле 2х2, при котором он как можно раньше проверит гипотезу поля 2х1. Так как гипотезу 2х2 он и так проверит, а если окажется, что поле 2х1, то хотелось бы попасть к выходу максимум за 4 хода.
Далее, если поле максимум 3х2, то оптимальный алгоритм должен быть таким, чтобы
— за 4 хода гарантировано попасть к выходу на поле 1х2 (т.е. начинается с точностью до обозначений с LURD);
— за 8 ходов — на поле 1х3 (LURD LUDR);
— за 11 ходов — на поле 2х2 (LURDLUDR ULD).
P>Можно ещё поставить вопрос так: P>- случайным образом выбираем лабиринт площадью N P>- какая последовательность в среднем будет выводить быстрее всего? P>Совсем не факт, что та же, которая выводит гарантированно.
Ну, конечно! В очень большом количестве случайных лабиринтов поле будет гораздо меньшего размера, а остальные части будут огорожены непроходимой стенкой. Поэтому мы не знаем реального размера поля, а знаем в лучшем случае его максимальный размер!
Здравствуйте, Apapa, Вы писали:
A>Ну, конечно! В очень большом количестве случайных лабиринтов поле будет гораздо меньшего размера, а остальные части будут огорожены непроходимой стенкой. Поэтому мы не знаем реального размера поля, а знаем в лучшем случае его максимальный размер!
А вот интересно.
Если мы взяли случайный лабиринт площадью N и случайную стартовую точку внутри. Какова площадь той части лабиринта которую можно достить из этой точки? Не будет ли предел этой величины конечным при стремлении N к бесконечности? Слабо найти? Хотя бы на компе...
Здравствуйте, Pushkin, Вы писали:
P>А вот интересно. P>Если мы взяли случайный лабиринт площадью N и случайную стартовую точку внутри. Какова площадь той части лабиринта которую можно достить из этой точки? Не будет ли предел этой величины конечным при стремлении N к бесконечности? Слабо найти? Хотя бы на компе...
Как же, дождёшься от вас Сам написал
Генерим лабиринт в квадрате NxN случайно.
В каждом месте ставим стеночку с вероятностью p.
Затем случайно выбираем стартовую точку.
Исследуем зависимость средней закрашенной площади S(N,p)
Зависимость явно степенная с полюсом в районе p=0.5,
где клякса становится глобальной и надо учитывать края.
Думаю, что если увеличивать N, последняя картинка не изменится ни чуть-чуть.
Имеем классический случай перколяции. Другой её известный пример — внезапное возникновение проводимости в смеси проводящих и непроводящих шариков при некоторой пороговой концентрации.
Здравствуйте, mrhru, Вы писали:
P>>Первый нетривиальный случай — для лабиринта площадью 2 — никому не отдам. P>>Длина минимальной последовательности равна 4, и с точностью до поворотов и отражений она единственна: P>>
P>>LURD
P>>
M> Молодец! M>А теперь то же, но для площади 3.
Если кому-то ещё интересно, для площади 3 есть 6 разных лабиринтов (2 с точностью до поворотов) и минимальная выводящая последовательность единственна и имеет длину 9
LULRUDRLD
Здесь замечательны 2 вещи.
1) Боже, какая же она уродливая! Ну абсолютно ничего примечательного на вид. А ведь она реализует некий экстремум на симметричной картинке. Странно ...
2) Забавно, что это последняя площадь, которую я смог обработать. Уже случай S=4 на 19-м ходу ушёл в столь долгие вычисления, что я его не дождался. Либо я где-то торможу (алгоритмисты, ау!) либо это самая трудоёмкая переборная задача, какую я встречал. Чтобы для такого детского входного параметра 4 перебор шёл часами??? Нельзя ли это как-то на службу людям поставить (в криптографии какой-нибудь?)
Здравствуйте, Pushkin, Вы писали:
P>Если кому-то ещё интересно, для площади 3 есть 6 разных лабиринтов (2 с точностью до поворотов) и минимальная выводящая последовательность единственна и имеет длину 9
P>
P>LULRUDRLD
P>
Замечательно!
P>Здесь замечательны 2 вещи. P>1) Боже, какая же она уродливая! Ну абсолютно ничего примечательного на вид. А ведь она реализует некий экстремум на симметричной картинке. Странно ... P>2) Забавно, что это последняя площадь, которую я смог обработать. Уже случай S=4 на 19-м ходу ушёл в столь долгие вычисления, что я его не дождался. Либо я где-то торможу (алгоритмисты, ау!) либо это самая трудоёмкая переборная задача, какую я встречал. Чтобы для такого детского входного параметра 4 перебор шёл часами??? Нельзя ли это как-то на службу людям поставить (в криптографии какой-нибудь?)
Есть достаточно много таких вещей. Например игра "Жизнь" Конвея или блуждание клеточного автомата на клетчатом поле (направление хода которого и метки, которые он оставляет после себя, зависят от окружающих клеток). Всех их объединяет то, что узнать их эволюцию, в общем случае можно, только её вычислив.
Для лабиринта 2х2 минимальная последовательность команд 11, и таких последовательностей 16, вот они:
LDRULDURDLU
DRULDRLURDL
RULDRURDLUR
DLURDLDRULD
ULDRULRDLUR
RDLURDULDRU
LURDLUDRULD
RULDRUDLURD
LURDLULDRUL
URDLURULDRU
URDLURLDRUL
LDRULDLURDL
DRULDRDLURD
DLURDLRULDR
ULDRULURDLU
RDLURDRULDR
Ранее указанная последовательность ULDRLURD (кажется, ее придумал Кодт, еще на заре империализма) не работает здесь:
+-----+
| |
+--+ |
|* |
+-----+
Для 2x3 (две строки, три столбца) нашел такую (длины 33):
DRULDLURRDLLDRRULULDURDRLLURULDRR
А теперь подумаем, верно ли это? Вот кинули робота в произвольный лабиринт 2х3 в произвольную клетку и сказали "DRULDLU...". А робот знает, где тут 2, а где 3? Он-то пользуется относительными координатами, и любая команда в абсолютной системе должна быть преобразована (нами или роботом, не важно) в относительную систему. А для этого (над или роботу) необходимо знать исходную ориентацию. Для квадратного лабиринта это не актуально: неверное или произвольное определение начальной ориентации робота можно свести к какой-то одной (например, вверх) путем поворота лабиринта. Так как последовательность команд выводит из любого лабиринта при любой начальной позиции, то выведет и из повернутого (про квадратный лабиринт говорим). С прямоугольным не так: поорот лабиринта на 90 градусов дает лабиринт другого размера, который не был учтен при составлении последовательности команд. В подтверждение сказанного приведу пример:
1x2:
RL
LR
2x1:
UD
DU
1x2 или 2x1:
LRDU
LDUR
...
Ну и приведу последовательности команд для лабиринта со сторонами 2 и 3, независимо от исходной ориентации робота (тут не все, длина у них 38 и тоже, скорее всего, не минимальные; когда точно найду минимальную, напишу).
DRULDLURURDLDRDLULURULDDRURUDRULLDRDDL
DRULDLURURDLDRDLULURULDDRURDDRUULLDRDL
DRULDLURURDLDRDLULURULDDRURDRDUULLDRDL
DRULDLURURDLDRDLULURULDDRUURDRULLDRDDL
DRULDLURURDLDLRRULULUDDRURDDLULURULDLU
DRULDLURURDLDLRRULURLLDDRURDDLLUURULDL
DRULDLURURDLDLRRULLULDDRURDDLULURULDLU
DRULDLURURDLDLRRULLULDDRURDDLULUDLURUL
DRULDLURURDLDLRRULLULDDRURDDLLULURULDL
DRULDLURURDDLULDDRRULURDRUULLDRDLULURR
DRULDLURURDDLULDRDRULURDRUULLDDRDLULUR
DRULDLURURDDLULDRUULRDRULLDDRUDLULURUL
DRULDLURURDDLULDRUULRDRULLDDRUDLLUURUL
Для 3х3 — две штуки длины 140 (опять же, это не минимум)
DRULULDDLURRURDDLULUDDRRULURULDLDRDLUURRDLDLRURDUULLRDDLLUURDRURULLDRDLRLULUDLDRUURDLDLURDRUDDLLURULULRRDDLDDRUUDLLURLDRDLRUDLUUDRURDDRULULD
DRULULDDLURRURDDLULUDDRRULURULDLDRDLUURRDLDLRURDUULLRDDLLUURDRURULLDRDLRLULUDLDRUURDLDLURDRUDDLLURULULRRDDLDDRUUDLLURLDRDLRUDLUUDRURDRDULULD
А теперь о том, откуда все это взялось.
Рассматриваем все возможные лабиринты в сочетании со всеми возможными исходными позициями робота. Этот маленький мирок (лабиринт+робот) я назвал realm. Рассматриваю сразу все realms (то есть если ищу последовательности для лабиринта 3х3, то рассматриваю 431*3*3=3879 realms). Всем realms посылаю одни и те же команды, слежу за посещением клеток лабиринта в каждой realm. Когда во всех realms все клетки посещены, выполненная последовательность команд является решением.
Использую поиск в глубину. Каждой ветви дерева поиска соответствует выполнение всеми realms группы из четырех команд. В качестве оценки перспективности использую максимум изменения количества посещенных клеток (сумма по всем realms). Таким образом, у каждой вершины дерева есть 256 поддеревьев, что, конечно, многовато. Поэтому есть возможность сделать оценку перспективности отсекающей оценкой (например, ограничив ветвление только 10-ю перспективными ветвями). Это быстрее даст решение, но тогда рискуем пропустить решение. Стопудово отсекающей оценкой является длина ветви. Как только она превышает длину минимальной найденной последовательности, ветвь обрывается.
Вот так.
P.S. Планирую применить поиск в ширину, но пока не придумал выражение для оценки перспективности, чтобы побыстрее найти решение.
Добрый день. Для начала хочу описать свой алгоритм поиска последовательностей команд для робота, затем расскажу о проблеме.
1. Рассмотрим множество M (maze) лабиринтов. Каждый из них может иметь произвольное количество клеток, но для удобства будем считать, что имеем N клеток в каждом лабиринте. Робот доберется до выхода, выполнив последовательность P (program), состоящую из L команд, если выполнение этой последовательности в любом лабиринте из рассматриваемого множеста M при любой начальном расположении робота приводит к тому, что все N клеток лабиринта будут хотя бы один раз посещены роботом.
Итого, суммируя по все лабиринтам, и рассматривая все варинаты исходного расположения робота, должно быть посещено N*N*[M] клеток. Изначально посещено (благодаря тому, что робот изначально где-то расположен) N*[M] клеток. Обозначим функцию суммарного количества посещенных клеток от длины начала последовательности P как V(l, P). Очевидно, это функция монотонно неубывает. Производная этой функции по аргументу l не может превышать N*[M] (такого значения я никогда не наблюдал).
Рассмотрим дерево поиска при поиске в ширину. Вершина дерева соответствует состоянию всех [M]*N лабиринтов (состояние — это информация о геометрии лабиринта, множество посещенных клеток в этом лабиринте, текущие координаты робота). Каждая вершина имеет вес, определяемый ... хз. Выбираем из этого дерева лист с наибольшим весом, добавляем к ней четыре ветви (каждая соответствует исполнению одной из команд 'L', 'U', 'R', 'D'). Новые образовавшиеся вершины теперь являются листьями, и могут подлежать дальнейшему ветвлению. Оценка перспективности ветвления — наивысший вес. Отсекающая оценка — расстояние от корня дерева до листа превышает длину уже найденной последовательности. Еще одна отсекающая оценка — недостижимость величины N*N*[M] с учетом максимального значения производной функции V(l, P), хотя эта оценка мало эффективна. И еще одна отсекающая оценка — окончание последовательности команд на "LRLR", "UDUD", "RLRL" и "DUDU". Эти подпоследовательности эквивалентны "LR", "UD", "RL" и "DU" соответственно, которые уже подвергались ветвлению ранее.
Окончанием поиска считается получение листа дерева, для которого V(1, P)==[M]*N*N.
2. Реализовал я это дело. Для хранения листьев дерева использовал multimap, где ключом был вес узла. Это позволяло легко определить следующий лист, который нужно ветвить.
Реализовал и офигел. multimap — на редкость живучая штука, переваривает до нескольких миллионов записей без каких либо проблем. Я бы так не смог. А почему так много? Все дело в том, как определять вес. Требования могут быть такими:
1) Вес минимальной последовательности, ограниченной длиной l, должен быть больше веса любой другой последовательности такой же длины.
2) Вес последовательностей, содержащих команды "LLL..L" или "RRR..R", состоящий из более чем W-1 команд (W — максимальная ширина лабиринта) — должен быть низок или равен 0. Аналогичная ситуация с "UUU..U" и "DDD..D".
3) Вес участков разной длины минимальной последовательности (последовательностей) не должен сильно отличаться. Это же ведь поиск в ширину, а не в глубину. Не стоит зацикливаться на одной последовательности.
Это все в идеале, а реально, так как минимальная последовательность изначально неизвестна (ее то мы и ищем), 1 и 3 отпадает. 2-е еще реально.
И проблема как раз в том, чтобы найти такое выражение для веса, чтобы:
1) Побыстрее найти решение.
2) Побыстрее найти более лучшее решение.
3) Не пожирать 320 Мб оперативной памяти для multimap, раздав нулевой вес бесперспективным листьям (нулевой — признак отсечения).
Здравствуйте, RS, Вы писали:
RS>Для 2x3 длина уже 27, щас не привожу, сорри
Страный у тебя выбор какой-то 2x3
Делал бы сразу для 3x3
Или для всех лабиринтов площадью 4 (не обязательно квадратных).
Их aж 23 и мой полный перебор закис на 19-м ходу,
интересно было бы твой неполный запустить, сколько выйдет...
Здравствуйте, Pushkin, Вы писали:
P>Страный у тебя выбор какой-то 2x3 P>Делал бы сразу для 3x3
P>Или для всех лабиринтов площадью 4 (не обязательно квадратных). P>Их aж 23 и мой полный перебор закис на 19-м ходу, P>интересно было бы твой неполный запустить, сколько выйдет...
Жди результатов в понедельник. Я не пробовал "любые лабиринты из N клеток", так как не могу придумать красивого способа генерить их. Но попробую. И почитай топик внизу.
Здравствуйте, RS, Вы писали:
RS>Я не пробовал "любые лабиринты из N клеток", так как не могу придумать красивого способа генерить их.
Кстати это сама по себе замечательный "этюд для программистов".
Даже чёрт с ними с внутренними стенками. Сколько существует полимино порядка N с точностью до поворотов и отражений?
Мартин Гарднер пишет, что общей формулы не существует — так что всё в наших руках.
Кто дойдёт до наибольшего N? Чистый спорт, блин!
Apapa.gif)
Евгений
Сам написал 
