ВОт,ехал в тачке из Дюссельдорфа,пришла такая задача в голову:

"Лабириинт" представляет из себя доску размерами n*n ,в которой каждая перегородка между клетками(неважно горизонтальная или вертикальная) открыта с вероятностью p.

Вход в лабиринт - в шамхатном A1,выход в шахматном H8.
C какой вероятностью в лабиринте имеется путь ведущий к выходу?


Тут наверно что-нибудь с теорией графов.А ведь и теория лабиринтов есть какая-то.

чую, что решением является

Σp^(a_i)

где i (кол-во элементов в сумме) равняется кол-ву возможных путей с А до Б, a_i - длина (кол-во пройденых перегородок) каждого из этих возможных путей. если сумма принимает значение >= 1, то прохождение лабиринта возможно с вероятностью 1

вся соль теперь расчитать i и a_i, а вот это не знаю, теорию графов знал на довольно примитивном уровне, из этих знаний в голове осталось на сегодняшний день процентов пять

swar0g пишет:

---

чую, что решением является

Σp^(a_i)

где i (кол-во элементов в сумме) равняется кол-ву возможных путей с А до Б, a_i - длина (кол-во пройденых перегородок) каждого из этих возможных путей. если сумма принимает значение >= 1, то прохождение лабиринта возможно с вероятностью 1

вся соль теперь расчитать i и a_i, а вот это не знаю, теорию графов знал на довольно примитивном уровне, из этих знаний в голове осталось на сегодняшний день процентов пять

---

эта вероятность зависит только от p и n. и никак уж не может быть больше 1...она очень маленькая,даже при cравнительно больших p.

вероятность (a И б) == вероятность(a)*вероятность(б)
вероятность (a ИЛИ б) == вероятность(a)+вероятность(б)

разве не так?

swar0g пишет:

---

вероятность (a И б) == вероятность(a)*вероятность(б)
вероятность (a ИЛИ б) == вероятность(a)+вероятность(б)

разве не так?

---

первая формула действует только если а и б независимые собития(unabhängig),вторая действует только если они унверайнбар(не имеют пересечений).в целом не так.

GRIBOEDOV пишет:

---

эта вероятность зависит только от п и н. и никак уж не может быть больше 1...она очень маленькая,даже при цравнительно больших п.

---

Ищем [P(p,n)]. В случае [n=2] всё просто:

[P(p,2)= 2*p^2-p^4], а потом может индукция ... Напоминает мне Фэйнмановский подход к квантовой механике

Ксати: [P(p,2)< or = P(1,2)=1]

Pankrat пишет:

---

Ищем [P(p,n)]. В случае [n=2] всё просто:

[P(p,2)= 2*p^2-p^4], а потом может индукция ... Напоминает мне Фэйнмановский подход к квантовой механике

Ксати: [P(p,2)< or = P(1,2)=1]

---

да индукция полюбому поможет

Pankrat пишет:

---

Ищем [P(p,n)]. В случае [n=2] всё просто:

[P(p,2)= 2*p^2-p^4], а потом может индукция ... Напоминает мне Фэйнмановский подход к квантовой механике

Ксати: [P(p,2)< or = P(1,2)=1]

---

да, 2*p^2 - p^4 понятно.

но как вывести проходимость n+1*n+1 из проходимости n*n ?

GRIBOEDOV пишет:

---

первая формула действует только если а и б независимые собития(unabhängig),вторая действует только если они унверайнбар(не имеют пересечений).в целом не так.

---

для n=2 у нас две дороги по две перегородки каждая. почему формула для n=2 не равна 2n² ? ведь у нас два независимые друг от друга, не пересекающихся пути. или одна дорога, или другая.

хотелось бы привести свои знания в порядок. да и интересно стало

GRIBOEDOV пишет:

---

да, 2*п^2 - п^4 понятно.

но как вывести проходимость н+1*н+1 из проходимости н*н ?

---

Это сложно. Особенно потому, что перегородки на границах шахматной доски имеют вероятность открытости равную нулю. Интересные получаются [Markov-Ketten] Это же твоя стихия.

swar0g пишет:

---

для n=2 у нас две дороги по две перегородки каждая. почему формула для n=2 не равна 2n² ? ведь у нас два независимые друг от друга, не пересекающихся пути. или одна дорога, или другая.

хотелось бы привести свои знания в порядок. да и интересно стало

---

p(a oder b) = p(a) + p(b) - p(a und b)

в этом случае
p(a) = p(b) = p^2 (вероятность что один из путей открыт)

p(a und b) = p^4
(вероятность что оба открыты)

Классно! Есть такая percolation theory, там похожие задачки решают. Вроде "с какой вероятностью можно пройти с одного края доски на другой". Механический отказ так моделируется, например. (С какой вероятностью много маленьких трещинок соединятся в одну большую).

С ходу придумалась нижняя оценка для вероятности, но она не шибко интересная. (p^4+2p^2(1-p)^2+4*p^3(1-p))^(n-1). Получается, если идти "по диагонали".

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

А предложение swar0g'а, как верно указал Гриб, не сработает именно потому, что вероятности реализуемости разных путей не взаимно независимые.

В общем, надо думать.

xWanderer пишет:

---

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

---

Т.е. не вероятности, а события.

Может быть обратную задачу будет проще решать? С какой вероятностью существует "сплошная стена из перегородок" от одного края доски до другого, концы которой лежат по разные стороны от диагонали A1-H8.

То есть стена начинается у верхнего или у левого края доски, а заканчивается у нижнего или у правого края.

xWanderer пишет:

---

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

А предложение swar0g'а, как верно указал Гриб, не сработает именно потому, что вероятности реализуемости разных ...

---

кароче помоему задача весьма глубинная. надо профу чтоли какому-нить написать из штохастикоф. можно было б диплом делать по этой теме..

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

imnotsleeping пишет:

---

Может быть обратную задачу будет проще решать? С какой вероятностью существует "сплошная стена из перегородок" от одного края доски до другого, концы которой лежат по разные стороны от диагонали A1-H8.

То есть стена начинается у верхнего или у левого края доски, а заканчивается у нижнего или у правого края.

---

да,ведь если есть хоть одна такая стена есть - проход невозможен.

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

нет.

GRIBOEDOV пишет:

---

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

нет.

---

А почему? Есть картинка? Четко взаимоисключающие ситуации вроде бы. Либо проход, либо стенка.

Можно для начала примериться с помощью нумерики. Алгоритм довольно тривиальный, можно просчитать на компе. Конечно с очень большими n надо будет очень долго ждать Но если сверить малые n, скажем до 10-20, можно уже получить примерное представление

LLoin пишет:

---

Можно для начала примериться с помощью нумерики. Алгоритм довольно тривиальный, можно просчитать на компе. Конечно с очень большими n надо будет очень долго ждать Но если сверить малые n, скажем до 10-20, можно уже получить примерное представление

---

что ты собираешься перебирать? все расстановки? а потом выйти из этого на формулу?