Итак, для фиксированной вершины мы посчитали моменты достижения из этой вершины. Теперь нам нужно также посчитать все моменты достижения в эту вершину. Как это делать? Прошлый подход работает плохо. Потому что если мы будем пытаться просто запускать случайные блуждания, то теперь нам придется запускать их из разных вершин. То есть для каждой вершины нам придется запускать отдельные случайные блуждания из этой вершины. И пришлось бы так делать, учитывая очень много случайных блужданий, это очень долго. При этом оказывается, что можно посчитать точные значения усеченных моментов достижения в данную вершину рекурсивно, то есть в обратную сторону мы можем вместо случайных блужданий, вместо запуска случайных блужданий, сделать рекурсивный подсчет, и он даст нам даже точные значения усеченных моментов достижения. Для этого давайте обозначим через h (v, T), Т-усеченный момент достижения нашей вершины, которая нас интересует, из вершины v. И давайте разберем простой случай, все очень просто, если T = 0. Тогда у нас h (v, 0) — это всегда 0 для всех v. Потому что случайные блуждания у нас имеют длину 0, то есть мы никуда не ходим, и независимо от всего остального длина у нас будет 0, тут даже усреднять особо нечего, длина случайного блуждания будет 0 для всех вершин. Для Т > 0, конечно, все уже не так просто, но давайте проанализируем. Посмотрим на первый шаг блуждания. Пусть мы хотим дойти в вершину A, она нас интересует, а стартуем мы из вершины v, и мы для всех вершин v хотим посчитать эти моменты достижения до вершины A. И вот мы делаем первый шаг. Пусть у нашей вершины соседи u1, u2 и u3. На этой картинке я рисую ориентированные ребра, но потому что все это работает для ориентированного случая тоже, и в этом случае нам нужно рассмотреть соседей вершины v, которые из v исходят ребро. Для неориентированного случая нам нужно рассмотреть всех соседей вершины v, тут то же самое, просто нужно ориентацию с ребер стереть. Итак, что мы делаем на первом шаге? Мы переходим в одного из соседей v равновероятно. У нас три соседа, переход в каждого из них происходит с вероятностью 1/3. Хорошо. Что происходит дальше? А дальше мы по сути запускаем случайные блуждания из каждого соседа, но теперь уже длины T − 1. То есть после того, как первый шаг сделан, у нас происходят случайные блуждания длины T − 1 из той вершины, в которую мы попали на первом шаге. И тогда ожидаемая длина случайного блуждания из вершины v длины T будет равна 1 за первый шаг плюс усредненная ожидаемая длина случайных блужданий длины T − 1 по всем соседям вершины v. Мы можем написать это формулой h (v, T) = 1 (за первый шаг) + вероятность перейти в конкретного соседа (вероятность перейти в конкретного соседа — это единица на количество соседей v, количество соседей v мы здесь обозначаем через N (v), так что вероятность для каждой из этих вершин одинаковая, это 1, деленная на количество соседей). Дальше мы суммируем по всем соседям, длину случайного блуждания из этого соседа длины уже T − 1, получается вот такое соотношение. Чем оно хорошо? Оно хорошо тем, что у нас длина случайных блужданий длины T оценивается, вычисляется просто через длину случайных блужданий от длины T − 1, от T − 1. Получается, что если мы предварительно посчитали длину случайных блужданий длины T − 1 из всех вершин у графа, то мы теперь уже, опять же, из всех вершин графа сможем посчитать длину случайных блужданий длины T, просто пользуясь этим соотношением. Посмотрим, как это реализуется. Мы будем хранить двумерный массив для каждой вершины v, и для каждой длины случайного блуждания мы будем хранить ту самую величину h (v, T). Мы будем заполнять этот массив последовательно для возрастающих T. Начать просто. Для T = 0 мы просто заполняем массив по всем вершинам нулями. А для каждого следующего T мы вычисляем каждую ячейку массива и значение ячеек для момента T − 1. Формулу мы, опять же, выписывали. Сколько времени это займет? Для каждой длины от 0 до T мы проходим по всем вершинам графа. Тут вот это неизбежно. Для каждой вершины нужно сделать столько операций, сколько есть соседей у этой вершины. Если мы вспомним формулу, то нам нужно было для каждого соседа прибавить некоторую величину, поэтому операций будет примерно столько же, сколько соседей у данной вершины. То есть по сути для каждого T у нас число операций — это примерно сумма степеней всех вершин в графе. А это удвоенное число ребер для случая неориентированного графа. Так что на самом деле нам нужно порядка T * E операций, с точностью до константы. То есть для каждого T нам нужно порядка E операций. Это, видимо, чуть больше, чем в прошлый раз, не так легко сравнивать, но в прошлый раз у нас получилось v + S * T, где S — количество блужданий, которые мы брали. Здесь у нас, во-первых, вместо числа вершин использовалось число ребер, скорее всего, оно больше, и нам приходится его умножать на T, так что, скорее всего, эта процедура будет работать чуть дольше, но тем не менее время достаточно разумное. Итак, у нас еще есть третья величина, есть симметричный вариант меры близости. Это усеченное время перемещения. Можно напомнить, что это сумма моментов достижения в обе стороны между вершинами. И как же, собственно, вычислять время перемещения из данной вершины во все остальные? Теперь это несложно. Мы просто применяем два описанных метода и складываем результаты. То есть если мы два предыдущих метода уже реализовали, то реализовать третий совсем легко. Мы просто проходим по всем вершинам, складываем результаты предыдущих методов и получаем результат. [МУЗЫКА]
