Прошлые домены не функционирует! Используйте адрес
ARHIVACH.VC.
24 декабря 2023 г. Архивач восстановлен после серьёзной аварии. К сожалению, значительная часть сохранённых изображений и видео была потеряна.
Подробности случившегося. Мы призываем всех неравнодушных
помочь нам с восстановлением утраченного контента!
Постановка задачи.
Задача о марьяже — математическая задача из области кооперативных игр. Требуется найти стабильные соответствия между элементами двух множеств, имеющих свои предпочтения. В более простой формулировке: составить брачные пары из женихов и невест таким образом, чтобы мужа из одной семьи и жену из другой не тянуло друг к другу сильнее, чем к своим законным супругам. Решение задачи отмечено Нобелевской премией по экономике 2012 года.
Существует конструктивный метод нахождения одного из решений задачи.
1) мужчины делают предложение наиболее предпочитаемой женщине;
2) каждая женщина из всех поступивших предложений выбирает наилучшее и отвечает на него «может быть», на все остальные отвечает «нет»;
3) мужчины, получившие отказ, обращаются к следующей женщине из своего списка предпочтений, мужчины, получившие ответ «может быть», ничего не делают;
4) если женщине пришло предложение лучше предыдущего, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «может быть»;
5) если женщине пришло наилучшее предложение, то она прежнему претенденту (которому ранее сказала «может быть») говорит «нет», а новому претенденту говорит «да» и далее предложений не принимает;
6) шаги повторяются, пока у всех мужчин не исчерпается список предложений, в этот момент женщины отвечают «да» на те предложения «может быть», которые у них есть в настоящий момент.
Максимальное количество шагов для реализации алгоритма: n² шагов, где n — число мужчин и женщин.
А теперь вопрос для долбоебов. КАЖДЫЙ ДЕНЬ РОЖДАЮТСЯ И УМИРАЮТ ЛЮДИ, КАК БУДЕТ ВЫГЛЯДЕТЬ КАРТИНА ТРЕБОВАНИЙ, ЕСЛИ АЛГОРИТМ ПОСТОЯННО НАХОДИТСЯ В ДИНАМИКЕ? ПРАВИЛЬНО КАК НА ПЕРВОМ ПИКЕ.