Как я делал сайт для проведения Тайного Санты и зачем для этого нужны математика и алгоритмы

Поговорим о теории графов, гамильтоновых циклах и задаче коммивояжера. Пост может быть интересен как программистам, так и любопытным непрограммистам, которые хотят знать, какой хренью иногда занимаются разработчики.

Каждый год мы запускаем Тайного Санту у нас в семье. Вместо того, чтобы дарить каждому члену семьи мелкий бесполезный подарок, тебе случайным образом назначается один получатель, и ты даришь только ему. Получается, что вместо кучи бесполезных подарков от каждого, ты получаешь только один, но зато ценнее.

В этом году мы решили сделать небольшой веб-сайт для этого дела. Чтобы каждый член семьи мог зарегистрироваться, написать список пожеланий и узнать имя своего получателя. Таких сервисов в интернете довольно много, но после накопленного опыта мы решили сделать свой, чтобы можно было скорректировать алгоритм распределения получателей (об этом позже).

Когда все участники мероприятия зарегистрировались, нужно их случайным образом распределить в одну цепочку. Я дарю кому-то, он дарит еще кому-то, …, последний дарит мне. Алгоритм для такого распределения нам и нужно написать.

В таком виде задача решается просто. У нас есть множество всех участников. Берем из него случайного человека — получаем гипотетического Васю. Из оставшегося множества случайно выбираем того, кому дарит Вася — получаем гипотетическую Машу. Потом точно так же выбираем того, кому дарит Маша. Повторяем, пока не закончатся участники. Последний дарит Васе. Круг замкнулся, мы распределили получателей, задача решена.

Такой алгоритм называется наивным. Мы просто сделали то, что, в общем-то, очевидно. Обычно наивные алгоритмы не являются оптимальными по быстродействию, но эта задача настолько простая, что наивный алгоритм оказался оптимальным.

Теперь переходим к тому, из-за чего мы захотели сделать свой сайт — к особым требованиям. Одна из проблем, с которой мы столкнулись — это то, что при таком полностью случайном распределении можно в качестве Санты получить того, кому тяжело остаться анонимным. Например, если моим Тайным Сантой является моя жена, то это практически невозможно скрыть, и Санта перестает быть тайным.

Поэтому у нас появилась идея, что было бы неплохо добавлять ограничения. Например, Вася и Маша регистрируются для участия, но они не хотят дарить подарки друг другу. Нам нужно добавить дополнительную информацию при регистрации и изменить алгоритм, чтобы таких ситуаций не возникало.

Но в таком случае наивный алгоритм, который мы написали ранее, уже не подойдет. Берем уже упомянутую ситуацию: Вася и Маша не могут дарить подарки друг другу. Мы можем это учесть в наивном алгоритме: когда нужно выбрать получателя для Васи, мы просто берем случайного человека из всех кроме Маши. Но что, если других вариантов уже нет? Что, если это был последний шаг алгоритма, и нам осталось только выбрать получателя для Васи, а все остальные кроме Маши уже заняты? В этом случае алгоритм зашел в тупик и не может решить задачу до конца.

Что делать? Первое решение, которое мы поначалу использовали в нашем сайте — это перезапускать алгоритм, пока он не сойдется. Довольно примитивное решение, но на наших данных хватало одного-двух повторов, так что вариант был вполне рабочим.

Но давайте решим задачу как надо, чтобы алгоритм находил решение всегда, когда оно существует. Возможно, нам нужно представить данные как-то по-другому, чтобы можно было применить другие алгоритмы.

У нас есть участники. Так же у нас есть информация о связях между ними: Вася и Маша не могут дарить друг другу, но могут дарить другим. Когда у нас есть узлы и связи между ними, стоит сразу вспоминать о графах, потому что графы — это (помимо титула королевских должностных лиц) математические структуры, состоящие из узлов и связей между ними.

На этом графе узлы — это участники мероприятия, а линиями показано, могут ли они дарить подарки друг другу или нет. Теперь нам нужно найти такой путь, который проходит через всех участников. Причем начинаться и заканчиваться этот путь должен на одном и том же участнике — такой путь называется циклом.

Для цикла, который проходит через всех участников по одному разу, даже есть отдельное название — это гамильтонов цикл. Значит, мы свели задачу к уже существующей и просто можем взять готовый алгоритм из учебника.

Но гугл меня расстроил. Задача поиска гамильтонова пути (или цикла) не имеет оптимального алгоритма. Задачи такого типа называются NP-трудными. Или, может быть, NP-полными — я точно не знаю разницы. Я вообще больше про практику, чем про теорию. В общем, не важно, как это называется, а важно то, что мы можем только перебирать варианты, пока не найдем нужный, а это может быть долго. Но мы можем использовать различные ухищрения, чтобы ускорить перебор.

У поиска гамильтонова цикла есть одна родственная задача — задача коммивояжера. Ее суть в том, что есть странствующий торговец и какие-то города. Ему нужно построить оптимальный маршрут, чтобы он обошел все города по одному разу и его путь был наиболее выгодным. Эта задача часто рассматривается в учебниках и статьях про NP-задачи и про то, как сложно их решать.

В задаче коммивояжера нужно найти оптимальный маршрут. Это значит, что нужно перебрать действительно все варианты и потом выбрать из них самый выгодный. Количество вариантов при переборе считается с помощью факториала — произведения всех чисел от 1 до N. Если у нас 5 узлов в графе, то существует 120 вариантов их обхода. Если 10, то 3628800 вариантов. Если 20, то 2432902008176640000. Это много.

У нас задача гораздо проще, и в нашем случае не стоит бояться перебора. В графе может быть большое количество гамильтоновых циклов и нам нужно найти хотя бы один из них, а не перебирать их все. Даже с добавлением ограничений (Вася и Маша не могут дарить друг другу) у нас все еще много вариантов, хоть их и становится меньше.

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

Если на каком-то шаге переходить больше не куда, то мы зашли в тупик. Эта ситуация похожа на ту, которую я уже описывал ранее, когда наивный алгоритм не находил решения. Но в этом случае нам уже понятнее, что делать дальше. Мы можем вернуться на один узел назад и выбрать что-то другое. Теперь мы знаем, что этот переход не приводит к решению, поэтому больше туда не идем. Если мы вернулись назад и все равно больше некуда идти (либо из-за ограничений, либо потому что мы там уже были и ничего не нашли), то идем еще на один шаг назад. Такой поиск в графе называется поиском с возвратом или поиском в глубину.

Если мы обошли все варианты и вернулись в самое начало, то в этом графе нет гамильтонова цикла, а значит, при таких ограничениях мы не можем начать Тайного Санту — мы просто не сможем назначить всем получателя подарка в соответствии с их ограничениями. И это самый плохой случай. Чтобы понять, что решения нет, алгоритм должен перебрать все возможные варианты, а это, как мы помним, очень много.

Но вспоминаем, что мы решаем инженерную задачу, а не абстрактную математическую. У нас вполне себе понятное назначение программы. Будет очень странным, если у нас 100 участников, и кто-то из них добавит 90 в ограничения. 1-2 максимум. Можно сделать наверняка и запретить участникам добавлять больше 3 ограничений. Вот так мы с помощью интерфейса спасли нашу программу от зависания при переборе миллионов комбинаций.

Я сделал несколько тестов. При трех ограничениях у каждого участника алгоритму иногда нужно сделать 1-2 возврата, но в подавляющем большинстве случаев алгоритм находит решение за N шагов для N участников. Если ограничений делать много, то становится сильно хуже. Например, в тесте со 100 участниками, где у каждого было 50 ограничений, перебор иногда занимал 100 шагов, а иногда 400000 или даже 1500000.

Так как наша начальная задача выполнена, дальше оптимизировать алгоритм не нужно, он прекрасно работает на наших данных.

Я не буду углубляться в код, так как это уже детали, хоть и важные. Если кому-то интересно, моя реализация здесь:

Я использовал нерекурсивный алгоритм и сортировку на каждой итерации, чтобы отделить посещенные узлы от непосещенных. Из-за сортировки итоговая сложность получается O(n^2) (n на перебор и n на сортировку). Если заменить сортировку на манипуляции со множествами, то, я думаю, можно ускорить до O(n*m), где m — это среднее количество ограничений, но только для маленьких m.

#приходько_техпоп #техпоп #математика