Ну как пряли. Не пряли, конечно, а лайкали друг на друга. По условиям конкурса «мисс Салтан» девицы должны были выбрать меж собой лучшую.
«Какой-то странный конкурс», — беспокоились девицы. И это было правдой. По правилам конкурса вес лайка участника зависел от того, сколько лайков он получает от других. Что это значит, — никто из девиц до конца не понимал.
«Как все сложно», — тосковали девушки и подбадривали себя песней «Кабы я была царицей».
Вскоре «в светлицу вошел царь — стороны той государь» (показан на рисунке). «Во все время разговора...», — ну понятно в общем.
«Собираем лайки нежности — формируем матрицу смежности», — бодро срифмовал он.
Девицы-красавицы с именами Алена, Варвара и Софья засмущались, но лайки (из балалайки) передали.
Вот что там было:
- Алена получила 1 лайк от Софьи и 2 лайка от Варвары.
- Варвара получила по лайку от Алены и Софьи.
- А Софья получила 2 лайка от Алены и 1 от Варвары.
Царь взял лайки, покрутил гайки, постучал по колесам, пошмыгал носом, причмокнул губами, поскрипел зубами, сгонял в палаты и объявил результаты.
Наибольший вес лайков (7 баллов) получила Софья, но титул «мисс Салтан» достался Алене (15 баллов).
вектор потенциалов равен (5, 4, 7), а вектор потоков — (15, 12, 14).
После объявления результатов девицы
1. Уравнение баланса
В основе нашего мира лежит баланс. Это означает, что если в одном месте что-то прибыло, то в другом месте столько же убыло.
Физики демонстрируют данный баланс уравнением непрерывности для сплошных и непрерывных сред. Но в современном мире рулят танковые клинья дискретные системы — графы.
У графа есть узлы, через которые течет поток (ну как течет — толчками и нерегулярно). Принцип баланса прост — в узле графа остается разница между тем, сколько из него вытекло и сколько в него втекло. А куда течет поток из узла? Правильно — в другие узлы, соответственно втекает поток в узел тоже из других узлов.
Запишем это множество слов формулой:
Здесь обозначает количество входящего потока в i-й узел,
— количество исходящего из узла потока,
— изменение остатка в узле.
Да, остатки в наших кошельках подчиняются данному уравнению баланса. И весь бухгалтерский учет на нем основан, — даже названия специальные придумали: исходящий поток — кредит, входящий — дебет.
Неизвестно, кто и почему ввел принцип баланса в естественные (физические) системы, но в основу искусственных систем (учет, рейтинги, кармы и пр.) лучше закладывать принцип баланса. Если мир выжил на балансе, то и у такой системы есть шанс.
В многих ситуациях (в частности с нашим конкурсом оценок) учет остатка в узле не нужен. То есть он всегда нулевой — сколько втекло — столько и вытекло. Игра с нулевой стоимостью нулевым остатком. Для таких систем уравнение упрощается:
Круто. Но пока малополезно.
Баланс потенциалов
Когда мы говорили о том, что поток может течь из узла i в узел j, мы подразумевали, что есть некая связь между данными узлами. Иначе потоку просто не по чему течь. Связность узлов графа обычно называют матрицей смежности (связности), ее элементы обозначают через
Есть связь — есть поток, нет связи — нет потока. Логично предположить, что чем сильнее связь — тем больше поток.
Итак, поток между узлами пропорционален величине связи узлов. Но чему равен коэффициент пропорциональности?
Ответ будет немного туманный — поток из узла пропорционален некоему потенциалу узла.
Суть данного ответа в том, что узлы обладают неким потенциалом и данный потенциал непосредственно определяет величину исходящего потока. Если, например, у нас есть два узла, проводимость между которыми одинакова в обоих направлениях (
), то суммарный поток между узлами будет определяться разностью потенциалов данных узлов. Существование электрических сетей доказывает, что это реально работает.
Связь потока с потенциалами и проводимостью выражается простой формулой:
Подставляя (1.3) в уравнение баланса (1.2) получаем систему уравнений для расчета потенциалов узлов:
В данном уравнении известными являются проводимости, а неизвестными — потенциалы.
Количество уравнений в системе равно количеству узлов графа. Решение системы балансовых уравнений является прямой задачей расчета потенциалов (и потоков) графа.
В уравнении (1.4) мы использовали понятие общей проводимости исходящих из узла связей — степень узла:
Рейтинги и самооценки
«Все это здорово,» — сказали девушки, зевая. — «Но причем тут лайки?»
В системах голосования, при которых участники оценивают друг друга, оценки берутся с учетом веса голоса каждого участника. А вес голоса опять же зависит от того, как данного участника оценили другие.
Связываем с потоками. Когда i-й участник с весом голоса оценивает j-го участника с оценкой (количеством лайков)
то он делится с ним своим потоком
. Копить остатки тут ни к чему, поэтому каждый участник делится с остальными всем, что получил.
Вес голоса участника — это потенциал , матрица лайков — это матрица смежности (связности), а итоговая оценка — суммарный полученный (он же отданный) поток
.
Для ранжирования участников (определения лучших) нам надо решить уравнение баланса (1.4), то есть определить веса участников, которые сбалансируют систему.
2. Лапласианы
Когда я
Помню «вау-эффект», когда я узнал о том, что есть и другой способ расчета потенциалов, о котором, видимо, знали еще наши деды Лаплас и Кирхгоф. Способ основывается на свойствах матриц-лапласианов. Тут уже недавно вспоминали лапласианы в непрерывных средах. Дискретные лапласианы не менее интересны и важны.
Для того, чтобы определить матрицу лапласиана по заданной матрице смежности, используем веденное выше понятие степени узлов. Степени узлов расположим по диагонали лапласиана, а остальные элементы возьмем из матрицы смежности с обратным знаком. Получившуюся матрицу называют также матрицей Кирхгофа:
Примем, что проводимость исходящих из узла i дуг задается в i-м столбце матрицы. Соответственно в i-й строке матрицы – проводимость входящих в узел дуг. Тогда сумма элементов каждого столбца лапласиана равна нулю.
Вообще говоря, матрицы данного вида образуют отдельный класс, — лапласианы. Определитель лапласианов всегда равен нулю, поэтому, например, для них не существует обычной обратной матрицы. Но зато есть другая (псевдо)обратная, есть и своя единичная матрица. Получить лапласиан можно не только приведенным выше преобразованием. Например, преобразование девиации тоже дает лапласиан на выходе.
Лапласианы могут быть симметричными — в них потенциалы всех узлов равны между собой — для нашей задачи они пока неинтересны.
Матрица Кирхгофа относится к классу лапласианов.
Потенциалы лапласианов
В линейной алгебре есть понятие дополнительного минора матрицы — это определитель матрицы, полученной из исходной вычеркиванием строк и столбцов. Дополнительные миноры играют большую роль в лапласианах.
Потенциалом 1-го порядка лапласиана называется определитель матрицы, полученный вычеркиванием из исходного лапласиана одной строки и одного столбца.
Поскольку мы приняли, что в наших лапласианах сумма каждого столбца нулевая, то значение потенциала определяется только вычеркнутой колонкой, — строка может быть любой. Удобно вычеркивать ту же строку, что и колонка, — тогда не надо думать о знаке определителя.
Итак, если обозначить через дополнительный минор матрицы, то определение потенциала лапласиана можно записать как
Так вот эти потенциалы 1-го порядка от матрицы Кирхгофа и являются искомым решением уравнения (1.4).
Удивительно. Не нужны никакие циклы, начальные присваивания, произведение матриц и пр. Удалил строку/колонку, посчитал определитель — получил ответ.
- Потенциал узла представляет собой сумму произведений (кортежей) проводимостей ребер графа по всем возможным путям в данный узел, исключая контуры (циклы).
- Количество множителей в произведении на 1 меньше размерности (количества узлов) графа.
- Потенциал узла не зависит от проводимостей исходящих из него дуг.
- Каждый кортеж (путь) в выражении для потенциала узла состоит из дуг, которые исходят из всех узлов, кроме данного. В одном кортеже нет двух дуг, исходящих из одного узла, но могут быть дуги, входящие в один узел.
- В каждом кортеже (пути) обязательно присутствует дуга, входящая в узел (замкнутость).
- В выражении для потенциала отсутствуют кортежи, содержащие циклы (контуры).
- Количество кортежей в выражении для потенциала определяется известной формулой Кэли
, и быстро растет с ростом узлов графа. Для 4-х узлов имеем 4^2 = 16 слагаемых, для пяти — 5^3 = 125 и т. д.
- В симметричном графе потенциалы всех узлов равны – следствие того, что структура выражения для потенциалов всех узлов одна и та же (разница лишь в направлении).
Для определения потока через узел достаточно умножить потенциал узла на его степень:
Мы получили, что хотели.
Это вес голоса каждого участника. Теперь считаем потоки и определяем, кто сколько голосов набрал:
Алена набрала больше всех голосов.
Как считать потенциалы больших графов
Если граф большой (много узлов), то считать вектор потенциалоф через вычисление определителей миноров лапласиана неудобно (затратно). В таких ситуациях лучше использовать обращение матрицы. Алгоритм следующий:
- В матрице лапласиана заменяем первую строку на вектор (1, 0, 0, ...).
- Считаем обратную матрицу от полученной и находим ее детерминант.
- Делим значения первой колонки полученной обратной матрицы на ее детерминант. Это и есть искомый вектор потенциалов. В первой строке — потенциал первого узла, во второй — второй и т. д.
- Если абсолютное значение потенциала неважно, то считать и делить на детерминант необязательно.
Ранжирование объектов на основе потенциалов и потоков
По итогам нашего примера получилось так, что наибольший вес голоса получила Софья, но больше всего баллов набрала Алена.
Это означает, что авторитетные и избранные — это не одно и тоже.
Что именно должно служить основанием для ранжирования, — потенциалы или потоки,- требует отдельного рассмотрения в каждой задаче, поскольку определяется прикладным аспектом.
Результаты турниров
Рассмотрим применение системы ранжирования применительно к определениям итогов шахматного турнира. Справедлива ли нынешняя система определения победителя простой суммой очков? На наш взгляд, она имеет лишь одно достоинство — простота. Но в век смартфонов кого волнует простота?
Несправедливо то, что выигрыш сильного по сути приравнивается в «простой системе» выигрышу у слабого.
Современный и правильный подход — считать взвешенные очки, то есть использовать расчет потенциалов и потоков. Еще один плюс — при данной системе практически исключена дележка мест — не надо думать о том, что делать при равенстве очков.
Как раз недавно в Москве закончился турнир претендентов (поздравляем Сергея Карякина с победой!), по итогам которого большое количество участников поделило места (2-3, 4-7). Используя метод потенциалов, попробуем разобраться, кто же какое место занял на самом деле.
Результаты турнира — это матрица смежности графа. В терминах лайков проигрыш участника — это проставление лайка победителю (хотя и звучит немного непривычно). От проигравшего к победителю идет поток взвешенных очков.
А что такое потенциал применительно к игрокам?
Потенциал — это показанная участником сила игры (в данном турнире). Чем выше потенциал участника — тем большую ценность имеют очки, полученные от него другими.
Возможно ли, чтобы менее сильный игрок набрал большее количество очков, чем более сильный? Да, такое вполне возможно, хоть и бывает не так часто. Например, на упомянутом турнире претендентов сила участника и набранные им очки совпали — ранжирование по потенциалам и потокам оказались эквивалентными.
| Сергей Карякин | Хикару Накамура | Аниш Гири | Виши Ананд | Веселин Топалов | Левон Аронян | Фабиано Каруана | Петр Свидлер | |
| U | 17,8 | 11,4 | 12,5 | 13,7 | 6,4 | 12,0 | 13,8 | 12,4 |
| J | 14,5 | 11,8 | 13,0 | 13,2 | 9,0 | 12,4 | 13,3 | 12,8 |
| М | 1 | 7 | 4 | 3 | 8 | 6 | 2 | 5 |
Каруана все-таки второй, а Гири — 4-й.
Потенциалы пьяницы
Последний пример, который мы рассмотрим в данной статье — это расчет ценности карт в народной игре «Пьяница».
Спасибо за данный пример astgtciv. Без его статьи, возможно, не было бы и этой.
Подробности о постановке задачи есть в упомянутой статье, — карты бьют друг друга по правилам старшинства, но пи этом шестерка бьет туза.
Данная задача хороша тем, что значения потенциалов (хм, а потоки тут что значат?) могут быть выражены в явном виде — несложными формулами.
Общий вид матрицы смежности соответствует результатам карточных сравнений — кто кого бьет.
Нумеруя карты от условного туза к условной шестерке, получаем следующий вид матрицы смежности:
Ключевая особенность — в правом нижнем углу — «шестерка бьет туза».
Тогда матрица Кирхгофа будет иметь вид:
Теперь наглядно видно, почему потенциал «шестерки» равен (n-2)! Потому что вычеркнув колонку и столбец шестерки, мы получаем треугольную матрицу, определитель которой считается простым умножением элементов главной диагонали.
То же самое справедливо и для туза с той лишь разницей, что у него в составе множителей два раза встречается элемент (n-2). Поэтому сразу видно, что потенциал туза всегда в (n-2) раза больше потенциала шестерки.
Интересно, что сумма потенциалов всех карт (кроме шестерки и туза) равна потенциалу туза:
Заключение
Сколько могли старались и слушали девицы сказ царя Салтана про возможности лапласиана, да все равно сморил их крепкий сон.
Снились им добры-молодцы с большим потенциалом, управляющие крупными потоками.
Пришла и нам пора закругляться. Используйте потенциалы!
Комментарии (0)