Универсальный путевыводитель из лабиринта.

[nikvic]

Лабиринт состоит из одинаковых квадратов-комнат, в каждом из которых есть хотя бы один выход - на Север, Юг, Запад, Восток.
Путевыводитель - список из этих команд-направлений. Существует ли путевыводитель, гарантирующий выход из лабиринта из любой начальной комнаты?

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

[lena7]

Если комнат конечное число, то и путей тоже. Путеводитель может их перебрать.

[nikvic]

Ну, есть у Вас список всех путей. Что дальше?

[_Ivana]

nikvic простите, непонятно в чем вы видите суть задачи. Вам уже ответили, что можно перебрать все пути без прохождения дважды одной клетки. Которые дают выход - те годятся. Их может не быть для каких-то точек и конфигураций лабиринта.

ЗЫ буквально пару месяцев назад решали с сыном эту задачку по его предложению. Написали программку с рекурсией: задаем размер лабиринта и внутренние стенки, программа перебирает все варианты, складывает в мешок годные, потом сортирует их по количеству шагов. Хотите, пришлю

[nikvic]

Ещё раз. Все пути есть. Можно ли собрать из них слово? Как?

[_Ivana]

nikvicЕще раз. Непонятно, что вы имеете в виду. Приведите пример. Результат в виде "вверх-влево-вверх-вправо-вверх" вас по каким-то причинам не устраивает?

[nikvic]

Пока не вижу алгоритма составления слова.

[rustot]

если выйти, а не оптимально выйти, то просто рекурсивный перебор с блокированием ячеек где уже побывали

func(pos)
  return if pos in way
  push way, pos
  bingo(way) if pos->exit
  func(next) for next in pos->ways
  pop way

[nikvic]

rustot в сообщении #755217 писал(а):

с блокированием ячеек где уже побывали

Стоп. Чукча не помнит, где когда был - прочтите условие.

[rustot]

в смысле вообще ни одной хранимой переменной кроме текущего положения? ну тогда только рандомно :)

[g______d]

(решение)

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

[Sonic86]

nikvic в сообщении #755189 писал(а):

Путевыводитель - список из этих команд-направлений. Существует ли путевыводитель, гарантирующий выход из лабиринта из любой начальной комнаты?

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

Я задачу понял так.
Пусть есть алфавит $A=\{U,D,L,R\}$, кодирующий ходы вверх, вниз, влево, вправо, на один шажок. $V_0$ - начальная точка, в которой находится путник. $E$ - точка выхода в лабиринте. Пусть $T\in A$, $V$ - точка, в которой находится путник, $T(V)$ - результат хода $T$ путником $V$ (если ход невозможен, то $T(V)=V$, иначе при $V=(x,y)$, $U(x,y)=(x,y+1), D(x,y)=(x,y-1),$ $L(x,y)=(x-1,y), R(x,y)=(x,y+1)$). Пусть $w$ - слово в алфавите $A$.
Вы спрашиваете, существует ли одно слово $w$ такое, что для любого лабиринта $L$ верно, что $w(V_0)=E$ (т.е. $(\exists w)(\forall L)(\forall V_0)(\forall E)w(V_0)=E$). Очевидно, что не существует: поскольку $|w|$ конечно, то для любого лабиринта такого, что расстояние $\rho (V_0,E)>|w|$ (метрика $\rho=|x_1-x_2|+|y_1-y_2|$) всегда верно, что $w(V_0)\neq E$.

Если я задачу понял неверно, просьба сформулировать ее по-человечески.

[nikvic]

Sonic86 в сообщении #755236 писал(а):

Вы спрашиваете, существует ли одно слово $w$ такое, что для любого лабиринта $L$

Тогда это будет не слово, а последовательность.

Задача, понятно, обобщается на любые графы (с отсутствием "ловушек" в случае ор-графов): на двери изнутри может быть написан номер, отличный от номеров других дверей "комнаты".

[g______d]

Если вопрос про одно слово для всех лабиринтор, можно просто все выписать по порядку.

-- 16.08.2013, 17:38 --

Слово, конечно, будет бесконечным.

[Sonic86]

nikvic в сообщении #755239 писал(а):

Тогда это будет не слово, а последовательность.

Ага, понял.

g______d в сообщении #755225 писал(а):

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

Можете пояснить, я не могу понять Т.е. я попробовал вывести 4-х человек, находящихся на расстоянии 1 от выхода для любого лабиринта. У меня не получается выписать отображение - построение не заканчивается. Т.е. если мы делаем некий шаг, из начального состояния $E=(0,0), V_1=(1,0), V_2=(0,1), V_3=(0,-1), V_4=(-1,0)$. Если в начальном состоянии было $k$ точек, то сначала возникает $2^{k-1}$ новых вариантов, а в худшем случае - $2^k$. И $2^k>1$ всегда, т.е. число вариантов после каждого хода увеличивается, как бы мы путеводитель не строили. А еще ведь есть и другие точки, из которых надо дойти до $E$. Конечно, множество [конечных] лабиринтов с точками счетно, но я не вижу явно.
Сейчас опять какие-нибудь аксиомы выбора полезут