Одна из классических задач в алгоритмах – подбор пар по рейтингам предпочтений. Она известна минимум в двух модификациях: когда пары несимметричны (например, первый элемент пары – дипломник, второй элемент пары – куратор) и когда пары симметричны (например, разбиваем отряд на боевые двойки).
Возьмём задачу, когда пары симметричны. Нам надо из 2n элементов составить n пар (ну пусть не бойцов в боевые двойки, пусть разработчиков в двойки парного программирования). Каждый из 2n разработчиков ранжирует для себя остальных 2n - 1 коллег по предпочтениям, с кем бы он хотел работать. И допустим (почему я перешёл от бойцов к разработчикам), что разбивка по парам идёт от эйчара как рекомендация, а не от топ-менеджера как предписание, т.е. при желании разработчики могут перераспределиться.
Что произойдёт, если в итоговой разбивке находятся двое разработчиков из разных пар, для каждого из которых личный рейтинг второго больше, чем того, с кем их поставили (ну то есть, Петю поставили с Васей, Колю с Серёжей, а Петя больше хотел бы работать с Колей, и Коля больше хотел бы работать с Петей)? Они оба захотят лучше работать в одной паре, чем в тех, в которых их поставили. Петя с Колей договорятся и перейдут в одну пару. Но тогда у нас получатся две неполные пары (Вася и Серёжа), которые, в свою очередь, может быть, вместе работать совсем-совсем не хотят, и будут искать других напарников, и возникнет цепная реакция перемещений. То есть, такая разбивка будет неустойчивой. Соответственно, задача алгоритма подбора пар – чтобы не было таких ситуаций.
Иногда устойчивое решение возможно, иногда нет (например, в ситуациях циклического рейтинга, типа камень-ножницы-бумага). Однако в устойчивых решениях, в ситуациях, когда рейтинг более или менее не зависит от того, кто рейтингует (ну то есть, например, Петю любят почти все, а Серёжу только Мамба) мы зачастую наблюдаем как бы расслоение на два кластера: пары, где оба элемента обладают высоким рейтингом (и эти пары устойчивы по той причине, что им ничего менять не хочется, им и так хорошо), и пары, где оба элемента обладают низким рейтингом (и эти пары устойчивы – хотя им плохо, но с ними никто меняться не хочет).
И вот тут мы опять через айти приходим к вопросу про рай и ад.
В этой модели рай и ад появляются не как поощрение и наказание (ересь юридизма), а как неминуемое следствие свободы каждого. Элементы с высоким рейтингом кластеризуются в раю, где средний взаимный рейтинг высокий, а элементы с низким рейтингом кластеризуются в аду, где средний взаимный рейтинг низкий, и получающееся распределение устойчиво.
А я всегда говорил – нормальная уважающая себя религия не только предельно логична, но и потрясающе красива по кибернетической структуре.
23 подписчика