Математика рассадки за столом

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

План рассадки – важнейший элемент подготовки к любой свадьбе. Останутся ли гости довольны праздником, в большой степени зависит от вашего решения, кого с кем посадить. Если вы все сделаете правильно, вам удастся успешно объединить друзей невесты и жениха. Если ошибетесь, будет трудно остановить недовольное ворчание в зале или даже небольшую потасовку за его пределами.

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

Чтобы выбрать лучший план рассадки, нужно сначала определиться, что вы подразумеваете под “лучшим”, то есть какова ваша главная цель. Хотите ли вы, скажем, по большей части угодить VIP персонам? Или предпочитаете, чтобы в среднем все гости были максимально удовлетворены? А может быть, даже хотите слегка насолить гостям, которых вы в глубине души терпеть не можете, но которых пришлось пригласить по соображениям этикета?

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

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

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

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

В данном случае решение очевидно: посадите Люка, Брюса и Щенка Далматинца за один стол, а тех, кто всегда всем портит настроение – Дарта, Джокера и Круэллу, – за второй.

Глядя на колонку Люка, мы видим, что он получает 20 “очков счастья” за удовольствие сидеть рядом с Брюсом и 60 – за Щенка, что в сумме дает ему 80 баллов.

По аналогичной системе Брюс получает 60 баллов, а Щенок будет абсолютно счастлив со своими новыми друзьями, получив в сумме 100 баллов.

За столом “ворчунов” Дарт получает 45 “очков счастья”, Джокер – 50, Круэлла – 35. По крайней мере, им будет приятно побрюзжать вместе. Если сложить баллы всех гостей, то в целом такой план дает нам 370 баллов. Для начала неплохо.

Но стоит нам поменять местами двух гостей, как разразится катастрофа. Если Щенок Далматинца поменяется с Дартом (и за первым столом окажутся Люк, Брюс и Дарт, а за вторым – Щенок, Джокер и Круэлла), сумма баллов обрушится до 120.

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

Основной принцип будет таким же, и теоретически проверить все возможные комбинации рассадки можно и вручную. Итак, проблема решена… если не считать того, что даже для совсем скромной свадьбы (17 приглашенных, два десятиместных стола) существует 131 702 различных вариантов рассадки!

Ох…

Компьютерная программа, способная обработать один вариант в секунду, будет перебирать все возможные комбинации свыше двух недель. На то, чтобы сделать это с помощью карандаша и бумаги, уйдут десятилетия (не отпугнет ли это одного из будущих супругов?). Чем больше гостей, тем больше нужно времени на вычисления. Свадьба на сто гостей и десять столов имеет 65 триллионов триллионов триллионов триллионов триллионов триллионов триллионов возможных вариантов рассадки. Если вы решите проверить их все в предвидении великого дня – желаю удачи, она вам понадобится…

И вот здесь и начинается собственно оптимизация.

Существует множество остроумных математических методов[13], которые позволяют исключить, не проверяя, огромные массивы ненужных комбинаций. Это означает, что вместо подсчета общего количества баллов для каждого возможного плана рассадки вы можете быстро и эффективно пройтись по комбинациям и определить лучшую – без необходимости проверять все.

В 2012 году Меган Беллоуз и Джей Ди Петерсон использовали эту стратегию, чтобы спланировать свою свадьбу. Они начали с того, что присвоили каждому из своих 107 гостей “оценку счастья”. Осознавая масштаб проблемы, они решили обойтись без карандаша и бумаги и сделали то, что и подобает сделать каждому уважающему себя организатору свадеб: использовали Общую систему алгебраического моделирования (GAMS ) совместно с пакетом программного обеспечения CPLEX . Компьютер сделал свою работу, и через 36 часов жених и невеста получили оптимальный план рассадки.

Если ваши знания численных методов оптимизации находятся не на самом высоком уровне, вам придется обработать два-три самых “трудных стола” вручную. Либо обратитесь к кому-нибудь из друзей-математиков. Насколько мне известно, они всегда рады помочь.

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