Эффективное разбиение на пары

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

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

Для более точной математической формулировки задачи, мы считаем, что каждый мужчина и каждая женщина составляют свой индивидуальный список симпатий-антипатий. Например, в списке у женщины под номером 1 будет записан самый привлекательный для неё мужчина, под номером 2 чуть менее привлекательный мужчина, под номером 3 еще менее привлекательный, и т.д. Под последним N-ым номером у неё будет записан самый непривлекательный для неё мужчина. Аналогичные списки женщин составляет для себя и каждый мужчина.

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

Например, если получилось такое разбиение на пары, что в одной паре мужчине досталась женщина под номером 3 из его списка, а он сам в её списке имеет номер 5, то антипатия данной пары равна сумме 3+5=8. Надо посчитать такие суммы у всех пар, а потом просуммировать их по всем парам. Задача состоит в том, чтобы так разбить на пары, чтобы эта сумма была минимальная.

При N=1 задача тривиальная. Будет одна пара с суммарной фрустрацией равной 2, так как в списке мужчины будет всего одна женщина под номером 1, а в списке женщины будет только один мужчина под номером 1.

Пусть N=2 и мы имеем двух мужчин A1 и A2, и двух женщин B1 и B2. Здесь уже может быть несколько вариантов списков.

Первый вариант. Мужчина A1 указал женщину B1 первой в своем списке и женщина B1 тоже указала мужчину A1 первым в её списке. Аналогично, мужчина A2 указал женщину B2 первой в своем списке и женщина B2 тоже указала мужчину A2 первым в её списке. Тогда получаем единственное оптимальное разбиение на пары: (A1,B1) и (A2,B2). Фрустрация такого оптимального разбиения равна 4. Если мужчины поменяются своими женщинами (или женщины поменяются своими мужчинами), то фрустрация такого разбиения на пары увеличится до 8, так как в каждой паре фрустрация будет равна 2+2=4.

Второй вариант. Как и в первом варианте, мужчина A1 указал женщину B1 первой в своем списке и женщина B1 тоже указала мужчину A1 первым в её списке. Далее, как и в первом варианте, мужчина A2 указал женщину B2 первой в своем списке. Но женщина B2 указала в своем списке под номером 1 мужчину A1. В этом случае оптимальным будет разбиение на пары точно такое же, как и в первом варианте списков, то есть пары: (A1,B1) и (A2,B2). Только суммарная фрустрация системы будет больше, чем с первом варианте списков предпочтений. Теперь получаем: (1+1)+(1+2)=5. Если мужчины поменяются своими женщинами, то фрустрация такого разбиения на пары увеличится: (1+2)+(2+2)=7.

Третий вариант. Всё точно также, как и во втором варианте, но мужчина A2 теперь первой в своем списке указал B1. В этом варианте списков симпатий оба варианта разбиения на пары будут эквивалентны с точки зрения суммарной фрустрации всей системы. Оба разбиения на пары дают суммарную фрустрацию равную 6. А сами разбиения отличаются тем, что разбиение (A1,B1) и (A2,B2) дает очень совместимую пару (A1,B1) с минимальной внутрипарной фрустрацией равной 2 и очень несовместимую пару (A2,B2) с максимальной внутрипарной фрустрацией равной 4. В то время, как разбиение на пары (A1,B2) и (A2,B1) дает две среднесовместимые пары с внутрипарными фрустрациями равными 3.

Другие варианты. Все другие варианты сводятся к третьему варианту по своей суммарной фрустрации. Например, при кольцевом варианте у мужчины A1 первой в списке идет женщина B1, но у B1 первым в списке идет мужчина A2, а у A2 первая в списке идет B2, наконец, у B2 первым в списке идет A1. Нетрудно показать, что при таком кольцевом варианте разбиение на пары (A1,B1) и (A2,B2) дает суммарную фрустрацию 6, а внутрипарные фрустрации по 3. И разбиение на пары (A1,B2) и (A2,B1) тоже дает суммарную фрустрацию 6, а внутрипарные фрустрации по 3.

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

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

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

Рассмотрим сначала один из этих алгоритмов.

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

Первый случай - женщину никто не выбрал. Такая женщина на первом этапе ничего не делает и ждет второй этап.

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

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

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

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

Затем проводится точно также третий этап, четвертый и т.д.

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

Но есть еще один другой алгоритм. Этот другой алгоритм отличается от первого алгоритма только тем, что там вместо мужчин выборы на каждом этапе делают только женщины. Если в описании алгоритма, данного выше, все слова "мужчины" заменить на слова "женщины" и наоборот, то мы получим описание этого второго алгоритма.

Оказалось, что в общем случае, второй алгоритм приводит к другому оптимальному разбиению на пары с минимальной суммарной фрустрацией системы. Но сами минимальные суммарные фрустрации, полученные двумя алгоритмами, оказываются равными друг другу.

Оба разбиения на пары получаются одинаковыми по двум алгоритмам, например, в том случае, если некоторые женские и мужские списки симпатий симметричны друг другу. То есть это получается, когда мы можем так отсортировать всех мужчин (A1, A2, ..., AN) и так отсортировать всех женщин (B1, B2, ..., BN), что для некоторых пар мужчины AJ и женщины BJ из этих отсортированных списков, их списки симпатий совпадают с точностью до замены букв A и B. Это, например, первый и второй вариант для N=2 (см. примеры выше). Для третьего варианта при N=2 мы имеем два варианта отсортированных списков. Это вырожденный вариант, поэтому в этом варианте получается два разных решения.

А теперь, что самое забавное во всем этом.

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

Точно также, если на танцплощадке будут только "белые" танцы, то мужчины и женщины разобьются на пары по другому. Но влюбятся друг в друга примерно такое же количество мужчин и женщин, как и в случае, если на танцплощадке не будет ни одного белого танца.

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