[МУЗЫКА] Итак, у нас есть несколько мер близости, основанных на случайных блужданиях. И нам теперь придется их подсчитывать. Нам потребуется подсчитывать усеченные моменты достижения. Давайте обсудим, как это делать. Нас интересует задача нахождения ближайших вершин к данной. Таким образом, нам нужно подсчитывать усеченный момент достижения из нашей вершины до всех остальных, чтобы сравнить все остальные по близости к нашей. А также в обратную сторону, нам потребуется подсчитывать усеченные моменты достижения из всех вершин в нашу, опять же, чтобы сравнивать нашу вершину со всеми остальными. Давайте начнем с момента достижения из вершины, как их подсчитывать. Если мы попробуем действовать по определению, то что нам нужно будет сделать? Нам нужно будет перебрать все возможные пути из нашей вершины, и для каждой вершины в графе усреднить расстояние до нее по этим путям. Но это очень долго, просто если у нас T, даже если оно небольшое, все равно таких путей будет очень много, делать полный перебор — это очень затратно. Вместо этого мы будем подсчитывать моменты приближенно, и мы будем делать семплирование. Что мы будем делать? Мы будем запускать S, где S — некий параметр, который мы можем потом зафиксировать, случайное блуждание из нашей вершины. То есть просто запускаем наше случайное блуждание. По каждому блужданию мы меряем расстояние до всех вершин, мы меряем, сколько шагов потребовалось, чтобы дойти до каждой из оставшихся вершин. Давайте заметим сразу, что если T сильно меньше, чем число вершин, а это, скорее всего, у нас будет так, то для большинства вершин в графе расстояние будет T, потому что просто мы до них не дойдем, и сделаем T шагов, объявим усеченный момент равный T. Дальше мы так делаем, и, сделав S блужданий, усредняем это расстояние по всем сделанным блужданиям. И поскольку нас интересуют только ближайшие вершины к изначальным, то не так страшно, что большинство расстояний будет T. Да, для большинства вершин расстояние будет большое, но нас интересуют ближайшие, для них мы можем сравнить, какие на самом деле ближе. Таким образом, мы приближенно подсчитаем усеченные моменты достижения, взяв просто несколько случайных блужданий и усреднив по ним. Хорошо, давайте посчитаем, сколько времени это занимает. Что мы будем делать, как мы будем это реализовывать? Мы заведем массив по всем вершинам. Пусть у нас вершины A, B, C, D, E, F и G. Мы стартуем из вершины A. И давайте зафиксируем также T = 4, S = 10, и вот на этом примере сейчас разберем, что мы делаем. Мы проходим по случайным блужданиям, то есть мы запускаем случайное блуждание, пусть оно получилось такое, у нас четыре шага, и вот тогда получается пять вершин, мы начинаем из A, дальше C, E, потом так получилось, что мы вернулись в C, E и C соединены, это могло случиться, и дальше мы перешли в B. Вот, пожалуйста, наше блуждание. Что мы делаем дальше? Мы для всех вершин, которые встретились в блуждании, получаем в массиве первый момент, когда они были достигнуты. Например, вершина A была достигнута на шаге 0. В принципе, вершину A можно было игнорировать, поскольку до нее расстояние 0. Но давайте для единообразности ее тоже здесь писать. Ее мы достигли на шаге 0. На шаге 1 мы достигли C, пишем это. На шаге 2 мы достигли E, пишем это. На шаге 3 мы достигли снова C, но мы пишем только первый момент, когда мы встретили вершину, поэтому мы тут ничего не пишем. А на шаге 4 мы достигли B, пишем туда 4. Дальше, для всех остальных вершин блуждание тоже будет составлять четыре шага, и поэтому мы туда просто вписываем четверки, во все остальные вершины. И мы повторяем так для всех блужданий, усредняем по всем блужданиям, то есть мы суммируем, для каждого блуждания прибавляем эти числа туда, потом делим на десять, получаются какие-то такие числа. Видно, что до A расстояние 0, до B и С расстояние 2,4 и 2,5. Дальше идут E и F, там еще подальше D, вершина G оказалась вообще труднодостижима, до нее расстояние 4. То есть все пути либо достигли ее на шаге 4, либо не достигли вовсе. Вот получились такие показатели, вершины B и C поближе, дальше — E и F, дальше — D. Давайте посчитаем, сколько нам нужно операций на все это. На обработку каждого блуждания нам требовалось порядка T + V операций. Мы сначала должны пройти по блужданию, это примерно T шагов, то есть просмотреть все вершины блуждания по очереди и вписать, возможно, что-то в массив. А дальше мы должны еще пройти по всем вершинам в графе, то есть мы проходим по нашему массиву и добавляем четверки там, где ничего не добавилось. И это делается для каждого блуждания, поэтому всего нам потребуется порядка S * (T + V) операций, конечно, с точностью до какой-то константы. Такая получилась оценка. Обычно у нас T будет сильно меньше, чем v. То есть V — это число вершин в графе, оно может быть большое. T будет, скорее всего, не очень большое, поэтому T незначительно по сравнению с V, мы можем сказать, что оценка у нас на самом деле порядка S * V. V — это число вершин в графе, это мы не очень можем контролировать, то есть нам какой граф дали, такой у нас и есть. А S — это количество блужданий, чем оно больше, тем точнее наши приближенные подсчеты. Поэтому в принципе мы хотели бы, чтобы S было побольше. Тут не очень удачно получилось, что S умножается на V, если мы увеличиваем S, увеличиваем точность наших подсчетов, то и время растет. Если мы S хотим сделать большим, то и время тоже будет большим. Оказывается, что на самом деле мы можем эту проблему решить, можно то же самое сделать эффективнее. То есть мы на самом деле сейчас, по существу, повторим то же рассуждение, просто чуть аккуратнее проведем все эти подсчеты, и окажется, что это все можно делать эффективнее. Итак, как мы можем сделать иначе. Мы по-прежнему заведем массив, где будем хранить сумму расстояний по всем блужданиям до вершин, а потом в конце разделим его на S, получится усреднение. Но также мы заведем массив счетчиков для всех вершин, то есть мы для каждой вершины заведем счетчик. И что мы будем делать? Вот у нас есть блуждание, опять то же самое блуждание, A-C-E-C-B. Что мы делаем? Мы, во-первых, проверяем, встречалась ли данная вершина раньше в этом блуждании, то есть мы проходим по вершинам блуждания, проверяем, встречалась она нам раньше или нет, и вносим в первый массив информацию о том, какое там расстояние. То есть точнее будет сказать, прибавляем к ячейкам в этом массиве то расстояние, которое получилось в этом блуждании. Для A это 0, для C это 1, для E это 2, когда мы дойдем до второго C, мы увидим, что мы C уже раньше встречали, и тогда мы второй раз к C ничего не прибавляем, и для B это четверка. И второе, что мы делаем, на самом деле мы делаем это одновременно, мы увеличиваем счетчики вершин для всех этих вершин, которые встретились. Для A мы увеличиваем счетчик, поскольку она была встречена в этом блуждании, для B, для C и для E, для всех этих вершин мы увеличили счетчики. И так мы повторяем для каждого блуждания. У нас их всего 10, и получатся какие-то такие числа. То есть вершина A встретится все десять раз, для нее каждый раз будет расстояние ноль. Вершина B у нас в блужданиях встретилась восемь раз, суммарно получилось 16, C встретилась семь раз, D — пять и так далее. G встретилась всего один раз. Кстати, оказалось, что там длина блуждания была все равно 4, то есть мы до нее дошли, но длина получилась равна 4, тут четверка вписана. Итак, что у нас в данный момент записано в массиве расстояний? Там написаны суммы расстояний, но только для тех вершин, которые достигались в блужданиях. То есть если вершина не достигалась, то мы там не прибавляли четверку. Но, с другой стороны, у нас есть счетчики, которые говорят нам, сколько раз это произошло, сколько раз вершина была достигнута. Таким образом, мы массив расстояний можем поправить, мы можем прибавить туда недостающие четверки. Как это конкретно сделать? Мы к каждой ячейке массива прибавляем T, в нашем случае 4, умноженное на S минус значение ячейки в счетчике. Скажем, для вершины G, мы дошли до нее один раз, а во всех остальных блужданиях мы до нее не дошли, таких блужданий девять. Соответственно, мы должны в расстояниях прибавить четверку девять раз, то есть 9 * 4. Или, скажем, для вершины C мы должны прибавить четверку три раза, потому что мы семь раз дошли до C, а три раза не дошли, должны четыре прибавить три раза, то есть прибавить 4 * 3. Так мы делаем для каждой вершины, для этого мы проходим по массиву и делаем эти вычисления. И счетчики, соответственно, тоже правильно было бы увеличить, давайте их увеличим все до десяти, вот у нас сделали эти прибавления, получились вот такие результаты. И мы второй раз проходим по массиву, чтобы вычислить уже теперь среднее, теперь нам нужно поделить расстояние на величину счетчиков или на количество блужданий, что теперь уже одно и то же. Получатся вот такие результаты. И теперь мы нашли среднее значение по нашим блужданиям для каждой вершины. В чем плюс этого рассуждения? Плюс в том, что в предыдущем рассуждении мы проходили по массиву вершин каждый раз для каждого блуждания, мы проходили и прибавляли там четверки на каждом блужданий. Массив вершин, в нашем примере он небольшой, но, в принципе, он может быть огромный, вершин в графе может быть очень много, и проходить там каждый раз было бы очень неприятно. И вот ровно от этого мы избавляемся. На каждом шаге для каждого блуждания мы проходим только по блужданию, то есть делаем примерно T шагов, а дальше мы переходим к следующему блужданию. И проходим мы по массиву всех вершин только в самом конце, мы проходим, возможно, в начале, чтобы зафиксировать его нулями, и в конце, чтобы, во-первых, прибавить четверки в нужных количествах ко всем вершинам, а также увеличить счетчики. В конце мы проходим еще раз, чтобы поделить на количество блужданий, чтобы усреднить. Но так или иначе, мы проходим по массиву всего конечное число раз, какую-то константу раз, в начале и в конце. И тогда нам потребуется порядка V + S * T операций, на каждом блуждании мы делаем порядка T операций, и еще отдельно мы делаем обработку массива, это порядка V операций умножить на константу. Что у нас улучшилось? У нас улучшилось, что теперь V не умножается на S в этой оценке. Таким образом, мы можем сделать сильно больше блужданий, и при этом оставить время работы разумным. T сильно меньше, чем V, поэтому в такой реализации у нас будет возможность сделать S сильно больше, получить сильно более точные результаты. [МУЗЫКА]
