2mincer,
"В разборе написана вот такая формуала:":
Допустим надо посчитать матожидание E[x], количество шагов, что мы куда-то дойдем из вершины X, для простоты положим, что у нас ациклический граф. Пусть из нее исходит набор дуг, скажем в Y1, Y2, Y3 и вероятности переходов p1, p2, p3. И обозначим за P[X, steps] - вероятность дойти куда надо из X за steps шагов. Ну и для простоты положим, что пути максимум длины 2.
Тогда будет что-то такое:
E[x] = p1 * P[Y1, 0] * (1 + 0) + p1 * P[Y1, 1] * (1 + 1) + p1 * P[Y1, 2] * (1 + 2) +
p2 * P[Y2, 0] * (1 + 0) + p2 * P[Y2, 1] * (1 + 1) + p2 * P[Y2, 2] * (1 + 2) +
p3 * P[Y3, 0] * (1 + 0) + p3 * P[Y3, 1] * (1 + 1) + p3 * P[Y3, 2] * (1 + 2)
Теперь несколько упростим выражение (разделим его на части, где наш текущий щаг (1 + ), и ту часть которую мы прошли после того, как перешли по ребру)
E[x] = p1 * P[Y1, 0] * 1 + p1 * P[Y1, 1] * 1 + p1 * P[Y1, 2] * 1 +
p2 * P[Y2, 0] * 1 + p2 * P[Y2, 1] * 1 + p2 * P[Y2, 2] * 1 +
p3 * P[Y3, 0] * 1 + p3 * P[Y3, 1] * 1 + p3 * P[Y3, 2] * 1 +
p1 * P[Y1, 0] * 0 + p1 * P[Y1, 1] * 1 + p1 * P[Y1, 2] * 2 +
p2 * P[Y2, 0] * 0 + p2 * P[Y2, 1] * 1 + p2 * P[Y2, 2] * 2 +
p3 * P[Y3, 0] * 0 + p3 * P[Y3, 1] * 1 + p3 * P[Y3, 2] * 2;
Теперь во второй части, вынесем p1, p2, p3:
E[x] = p1 * P[Y1, 0] * 1 + p1 * P[Y1, 1] * 1 + p1 * P[Y1, 2] * 1 +
p2 * P[Y2, 0] * 1 + p2 * P[Y2, 1] * 1 + p2 * P[Y2, 2] * 1 +
p3 * P[Y3, 0] * 1 + p3 * P[Y3, 1] * 1 + p3 * P[Y3, 2] * 1 +
p1 * (P[Y1, 0] * 0 + P[Y1, 1] * 1 + P[Y1, 2] * 2) +
p2 * (P[Y2, 0] * 0 + P[Y2, 1] * 1 + P[Y2, 2] * 2) +
p3 * (P[Y3, 0] * 0 + P[Y3, 1] * 1 + P[Y3, 2] * 2);
P[Yi, 0] * 0 + P[Yi, 1] * 1 + P[Yi, 2] * 2 -- это мат-ожидание дойти куда надо из Yi. Перепишем выражение с учетом этого:
E[x] = p1 * P[Y1, 0] * 1 + p1 * P[Y1, 1] * 1 + p1 * P[Y1, 2] * 1 +
p2 * P[Y2, 0] * 1 + p2 * P[Y2, 1] * 1 + p2 * P[Y2, 2] * 1 +
p3 * P[Y3, 0] * 1 + p3 * P[Y3, 1] * 1 + p3 * P[Y3, 2] * 1 +
p1 * E[Y1] + p2 * E[Y2] + p3 * E[Y3];
Теперь посмотрим на первую часть -- там сумма вероятностей по _всем_ возможным путям из X до "куда надо дойти", а сумма вероятностей по всем путям = 1
Получаем:
E[x] = 1 + p1 * E[Y1] + p2 * E[Y2] + p3 * E[Y3];
"Еще одна задача, на этот раз с NEERC 2006": Там dp'шкой можно решить, состояния это набор связных компонент, если одна компонента, то E = 0, если несколько, то если добавлять ребро между компонентами, то понятно, как, просто по той формуле, что в картинке, а если ребро в самой компоненте, то получается петля, ее нужно разрешить: скажем у нас С ребер которые мы можем провести и они лежат в какой-то компоненте, а E' = sum(E[состояние после соединения вершин ребром, которые в разных компонентах]), тогда матожидание для всех ребер будет E = 1 + E' + E * p * C => E = (E' + 1) / (1 - C * p)
Вот как-то так.
Может я не очень ясно выразился?