Направленный взвешенный граф ходьбы

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

ПустьP - матрица смежности для графа. То есть P _{i, j} - Вероятность перехода из вершины i в вершину j. Множество P _{A, A} = 1. Если мы возьмем вектор вероятности, присвоенные каждой вершине и умноженные на P , то результирующий вектор содержит средневзвешенное значение соседей каждой вершины. Мы ищем вектор v , такой, что P v = v и v _A = 1.

Этот вектор v является собственным вектором P, соответствующим собственному значению 1. Всегда ли P имеет такое собственное значение? К счастью, теорема перрона-Фробениуса говорит нам, что это так, и что это самое большое собственное значение P . Тогда решение состоит в том, чтобы сформировать матрицу смежности P и найти собственный вектор, соответствующий его наибольшему собственному значению.

Существует также приближенное решение. Если мы возьмем вектор x вероятностей вершин, с x _A = 1, а остальные элементы, установленные в 0, тогда P ^k x сойдутся в v, поскольку k уходит в бесконечность. P ^k может быть, проще вычислить для малых значений k , чем собственный вектор.

---

Пример

Давайте рассмотрим следующий простой график:

Если мы упорядочиваем вершины по алфавиту, то матрица P, соответствующая графу, имеет вид:

Эта матрица имеет собственное значение, равное 1, и соответствующий собственный вектор равен: [1 0 70/79 49/79]. То есть, точная вероятность достижения A из C равна 70/79, а из D - это 49/79. Если Вы выработаете ответ для B , он выйдет на 9/79 и 30/79, что именно то, что мы ожидаем.

Значение P¹⁶ [1 0 0 0] приблизительно [1 0 0.886 0.62] и правильно до 6 знаков после запятой.