Подземелья и драконы:об одной комбинаторной задаче

[Nuflyn]

У нас имеется лабиринт состоящий из N комнат в каждой из которых (кроме двух) 4 двери, за тремя из них - другие комнаты, а за четвертой - дракон, который съедает незадачливого исследователя. Две комнаты отличаются от остальных - в них все так же четыре двери, три из которых ведут в комнаты лабиринта, а четвертые двери особые: одна из них вход в лабиринт, а другая выход. Сколько всего вариантов прохождения лабиринта есть у исследователя (имеются в виду пути ведущие от входа ко выходу и идущие через "безопасные " двери)? Самопересечения одной и той же траектории не допускаются. И какова вероятность не попасть на обед к дракону (не в качестве почетного гостя, разумеется) при однократном пробном прохождении?
NB: первый вопрос вероятно мелькал в том или ином виде в теории перколяции, но я как-то ничего не нашел...
А ответ на второй вероятно должен быть основан на произведении вероятностей и степенной зависимости от N.
Помогите, прояснить, коллеги.

[gris]

Вспомнилась нечто подобное. "Лабиринт" задавался матрицей $N\times N$ вероятностей перехода из комнаты с номером по строке в комнату с номером по столбцу. В Вашем случае, наверное, в каждой строке и столбце стоит четыре $0.25$ и матрица симметрическая. Ну, ясно, что переход к дракону, вход и выход как-то обозначаются. Я пытался какую-то теорию применить, но в результате просто моделировал проходы на компьютере. Запрет самопересечения тоже был: в виде обнуления соответствующих элементов матрицы. Конечно, очень многое зависит от топологии лабиринта, хотя ясно, что в среднем у посетителя шансов выжить мало. Многие вопросы требуют разрешения. Вы хотите искать вероятность успешного прохода по всем возможным лабиринтам или по лабиринту с заданной матрицей? Переходы симметричны? Что запрещает запрет самопересечений?

[DeBill]

Nuflyn
Мне кажется, с Вашей задачей что-то не то...
1. Как связаны комнаты? Связен ли граф? Мы его знаем? Или мы случайно скачем из комнаты в комнату?
2. С фига ли запрещены самопересечения? А, мы, видимо, гадим в комнатах, и потому назад возвращаться - стремно.
Но тогда, помимо исходов "на обед", и "домой", будет исход "тупик"...
Тогда (если граф задан), вероятность равна сумме, по всем путям, чисел $4^{-n}$, где $n$ - длина пути.
Но вот без знания графа - фиг чё тут найдешь. А в графе, кстати, могут быть кратные дуги? И степень каждой вершины равна 3?

[Утундрий]

И кроме того, в каждом приличном лабиринте должен быть ровно один дракон.

[Sender]

А любой уважающий себя дракон располагается так, что мимо него не пройдёшь.

[Nuflyn]

gris в сообщении #1150739 писал(а):

Вы хотите искать вероятность успешного прохода по всем возможным лабиринтам или по лабиринту с заданной матрицей? Переходы симметричны? Что запрещает запрет самопересечений?

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

-- 13.09.2016, 16:26 --

DeBill в сообщении #1150740 писал(а):

Nuflyn
Мне кажется, с Вашей задачей что-то не то...
1. Как связаны комнаты? Связен ли граф? Мы его знаем? Или мы случайно скачем из комнаты в комнату?
2. С фига ли запрещены самопересечения? А, мы, видимо, гадим в комнатах, и потому назад возвращаться - стремно.

Да вот как в предыдущем посте я уточнил этот момент. Кроме решения не худо бы конечно установить каких данных не хватает для решения. )

-- 13.09.2016, 16:35 --

DeBill в сообщении #1150740 писал(а):

Nuflyn
Тогда (если граф задан), вероятность равна сумме, по всем путям, чисел $4^{-n}$, где $n$ - длина пути.

можно тут поподробнее, мне не ясно откуда такой вывод

-- 13.09.2016, 16:37 --

DeBill в сообщении #1150740 писал(а):

Nuflyn
И степень каждой вершины равна 3?

Да, три двери из четырех ведут в соседние комнаты кроме четвертой, которая ведет к быстрому и мучительному финалу

[Sender]

Nuflyn в сообщении #1150930 писал(а):

Думаю что можно ограничиться скажем лабиринтом при котором узлы и ребра (то бишь комнаты и двери) образуют квадратную сетку как если бы мы нарисовали квадрат в школьной тетрадке в клетку причем двери с одного торца (за исключением входа и выхода) этого квадрата ведут в комнаты с другого торца (такие "кольцевые" граничные условия имеют место скажем во многих версиях модели Изинга).

Nuflyn в сообщении #1150930 писал(а):

DeBill в сообщении #1150740

писал(а):
Nuflyn
И степень каждой вершины равна 3?
Да, три двери из четырех ведут в соседние комнаты кроме четвертой, которая ведет к быстрому и мучительному финалу

Вот эти части противоречат друг другу, как мне кажется. Или у нас просто лабиринт в виде тетрадки, в некоторых комнатах которого расставлены драконы?

[gris]

А зачем бояться бесконечных блужданий? Это хотя и не невозможное событие, но вероятность его равна нулю. В формуле там, мне кажется, $(2/3)^n$, то есть даже при бесконечном при суммировании мы вероятность спасения намного не увеличим.
<Я думаю, что при прикосновении к плохой двери просто проваливается пол в подземелье, где и сидит ровно один дракон. Хотя в задаче этот дракон только мешает, так как провоцирует на конкретизацию совершенно нематематических деталей.>