Алгоритм Гейла-Шепли
Oct. 17th, 2017 11:27 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
snake_d_haФормальная задача:
"Составить брачные пары из женихов и невест таким образом, чтобы мужа из одной семьи и жену из другой не тянуло друг к другу сильнее, чем к своим законным супругам".
Существует конструктивный метод нахождения одного из решений задачи.
мужчины делают предложение наиболее предпочитаемой женщине;
каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть», на все остальные отвечает «нет»;
мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают;
если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть»;
если женщине пришло наилучшее предложение, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «да» и далее предложений не принимает;
шаги повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент.
Максимальное количество шагов для реализации алгоритма: n² шагов, где n — число мужчин и женщин.
Эти механизмы были внедрены в деятельность больниц по набору врачей и интернов, в правила многих американских профессиональных спортивных ассоциаций по набору спортсменов в команды. В соответствии с предложенными институциональными механизмами фирмы набирают на стажировку сотрудников, суды нанимают секретарей, родители находят подходящие школы для детей. Модель марьяжа в целом описывает последовательность действий индивидов при формировании пар на «рынках попутчиков» для совместных поездок, в некоторых видах спорта (парное фигурное катание, спортивные танцы), поведение участников в интерактивных реалити-шоу и пр.
Подробнее в Вики.
Нобелевка по экономике 2012 года, кстати.
А теперь ближе к реальной пользе.
Та, у кого есть право "отложенного согласия", то есть выбора и изменения своего решения (и она им пользуется), подбирает себе худшего партнера из своего списка. Тот, кто делает предложения - получает себе лучшего партнера из списка.
Где это применять? Да везде. Просто предлагайте, начиная с самых лучших для себя вариантов, и не бойтесь отказов. :)
"Составить брачные пары из женихов и невест таким образом, чтобы мужа из одной семьи и жену из другой не тянуло друг к другу сильнее, чем к своим законным супругам".
Существует конструктивный метод нахождения одного из решений задачи.
мужчины делают предложение наиболее предпочитаемой женщине;
каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть», на все остальные отвечает «нет»;
мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают;
если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть»;
если женщине пришло наилучшее предложение, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «да» и далее предложений не принимает;
шаги повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент.
Максимальное количество шагов для реализации алгоритма: n² шагов, где n — число мужчин и женщин.
Эти механизмы были внедрены в деятельность больниц по набору врачей и интернов, в правила многих американских профессиональных спортивных ассоциаций по набору спортсменов в команды. В соответствии с предложенными институциональными механизмами фирмы набирают на стажировку сотрудников, суды нанимают секретарей, родители находят подходящие школы для детей. Модель марьяжа в целом описывает последовательность действий индивидов при формировании пар на «рынках попутчиков» для совместных поездок, в некоторых видах спорта (парное фигурное катание, спортивные танцы), поведение участников в интерактивных реалити-шоу и пр.
Подробнее в Вики.
Нобелевка по экономике 2012 года, кстати.
А теперь ближе к реальной пользе.
Та, у кого есть право "отложенного согласия", то есть выбора и изменения своего решения (и она им пользуется), подбирает себе худшего партнера из своего списка. Тот, кто делает предложения - получает себе лучшего партнера из списка.
Где это применять? Да везде. Просто предлагайте, начиная с самых лучших для себя вариантов, и не бойтесь отказов. :)
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2017-10-18 05:19 am (UTC)no subject
Date: 2017-10-18 10:17 am (UTC)no subject
Date: 2017-10-18 05:36 am (UTC)Пример того, что до определенной степени математика в жизни бывает полезной. Правда, запредельные теоремы с множествами узлов в графах или разложимости чисел - уже для, мгм, фанатиков и специалистов. А вот такие иллюстративные алгоритмы-задачи - самое-то)
no subject
Date: 2017-10-18 10:17 am (UTC)Бо и название, и реферат их работы - просто трындец.
no subject
Date: 2017-10-18 07:49 am (UTC)no subject
Date: 2017-10-18 10:16 am (UTC)