Задача про мост

[Render]

Руст писал(а):

Соответственно, искомая вероятность $P=2^{m-n-2mn}N$, где N количество подграфов, соединяющих два берега.

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

[Руст]

Render писал(а):

Руст писал(а):

Соответственно, искомая вероятность $P=2^{m-n-2mn}N$, где N количество подграфов, соединяющих два берега.

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

Дело в том, что когда вероятность равна 1/2 это так. В общем случае каждый подграф рассматривается со своим множителем $p^k(1-p)^{M-k},M=2mn+m-n$. В искомой задаче этот множитель общий для всех $2^{-M}$ и есть обратная величина к количеству всех подграфов.

[Render]

А как попроще перебрать варианты всех искомых подграфов программно?

[Руст]

Программный перебор всех подграфов сведётся к нумерации М рёбер и перебору всех 2^M чисел: $0,1,...,2^M-1$. При этом двоичной записи числа х сопоставляем подграф, имеющие те ребёра, которые соответствует 1 в записи числа. Однако таким перебором на компьютере можно анализировать разве что случай M<=32.
В более ранней записи в качестве путей $L_i$ можно рассматривать минимальные связывающие два берега пути.

[Render]

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

[Руст]

Считать можно так. Пусть $X_1$ множество всех минимальных связных подграфов, соединяющих два берега, $X_2$ попарные объединения двух подграфов из $X_1$ (при этом некоторые подграфы могут войти в несколько раз, так как обединение a_1 с a_2 может совпасть с объеденением a_1 и a_3), $X_3$ тройные объединения и т.д. Тогда искомая вероятность равна

$$\sum_{j=1}^N \sum_{a\in X_j}(-1)^{j-1}2^{-|a|}.$$

Здесь $|a|$ означает количество рёбер подграфа а.

[Render]

Поделим вершины на группы, вершины в которых находятся на расстоянии i от первого берега для всех i от 1 до n.
Тогда для каждой вершины в i-й группе подсчитываем вероятности дойти до нее из вершин i-1 группы или из ее соседей из i-й группы, то есть из уже рассмотренной пройденной части моста.
Так я на последнем шаге получу вероятность дойти до другого берега через весь мост.
Правильно?

[Руст]

Render писал(а):

Поделим вершины на группы, вершины в которых находятся на расстоянии i от первого берега для всех i от 1 до n.
Тогда для каждой вершины в i-й группе посчитаю вероятности дойти до нее из вершин i-1 группы, то есть из уже рассмотренной пройденной части моста.
Так я на последнем шаге получу вероятность дойти до другого берега через весь мост.
Правильно?

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