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

Не вижу рисунка с картой лабиринта. Пришлите изображение или опишите граф лабиринта (узлы перекрёстков и дорожки между ними, где выходы). Тогда дам точное числовое решение. Пока — подробный метод вычисления и пример, чтобы вы могли применить его к вашему рисунку.

Что нужно посчитать

• В точке A игрок выбирает направление с равной вероятностью среди всех дорожек, выходящих из A.
• В следующих перекрёстках нельзя возвращаться по той же дороге назад (то есть при входе в узел у нас число доступных вариантов вниз по лабиринту равно количеству дорожек в узле минус одна, если дверь пришла с другой дорожки).
• Вероятность добраться до конкретного выхода — произведение степеней 1/(число доступных путей) на каждом узле вдоль выбранного пути.
• Вероятность добраться до любого выхода — сумма вероятностей путей к всем выходам.

Как посчитать шаг за шагом

1. Постройте граф лабиринта с направлением от узла A к «вперёд» (чёткого направления нет, но учитывайте правило: на старте у A доступно deg(A) дорог).
2. Для каждого узла v, если вы пришли в него по одной дороге, то число доступных переходов вперед равно deg(v) − 1. Для стартовой точки A число доступных переходов равно deg(A).
3. Для каждого пути от A до выхода L запишите вероятность: P(A → … → L) = 1/deg(A) × ∏ по всем переходам далее 1/(deg(v) − 1), где v — узлы между A и L (не включая A, включая каждый промежуточный узел, на котором вы делаете выбор).
4. Сложите вероятности по всем путям, ведущим к выходам. Если все листья являются выходами, сумма равна 1 (вы точно попадёте на выход). Если есть невыходные концы, сумма будет меньше 1.

Пример (наглядный, чтобы понять метод) Допустим простой лабиринт с такими узлами:

• A соединён с тремя дорогами: к B, к C и к F. deg(A) = 3.
• Узел B соединён с тремя дорогами: к A (назад), к E1 и к E3. То есть deg(B) = 3, поэтому с B вперед можно выбрать 2 варианта (deg(B) − 1 = 2).
• Узел C — выход (E2).
• Узел F соединён с двумя дорогами: к A (назад) и к E4. deg(F) = 2, значит с F вперед один путь (deg(F) − 1 = 1).
• Узлы E1, E3, E4 — выходы.

Расчёт:

• Вероятность уйти к выходу C через C: P(C) = 1/deg(A) = 1/3.
• Вероятность уйти к выходу E1 через A → B → E1: P(E1) = 1/deg(A) × 1/(deg(B) − 1) = (1/3) × (1/2) = 1/6.
• Вероятность уйти к выходу E3 через A → B → E3: P(E3) = 1/3 × 1/2 = 1/6.
• Вероятность уйти к выходу E4 через A → F → E4: P(E4) = 1/deg(A) × 1/(deg(F) − 1) = (1/3) × 1/1 = 1/3.

Сумма по выходам: 1/3 + 1/6 + 1/6 + 1/3 = 1. Это значит, что в этом примере все пути приводят к выходам (нет невыходных концов).

Как это применить к вашему рисунку

• Пришлите карту лабиринта или перечислите:
  • какие узлы (A и все перекрёстки) есть, какие дороги выходят из каждого узла и какие узлы являются выходами;
  • количество дорог в каждом узле (deg(v)).
• Я посчитаю точную вероятность для вашего конкретного рисунка, используя формулы выше и выпишу пошаговое решение.

Если хотите, могу также дать маленькую программку/псевдокод, чтобы автоматически посчитать вероятность по любому графу лабиринта (при условии, что лабиринт действительно можно трактовать как дерево или что вы учитываете правило без возврата).