Задача о свадьбе — математическая задача из области кооперативных игр. Требуется найти стабильные соответствия между элементами двух множеств, имеющих свои предпочтения. В более простой формулировке: составить брачные пары из женихов и невест таким образом, чтобы мужа из одной семьи и жену из другой не тянуло друг к другу сильнее, чем к своим законным супругам[1]. Решение задачи отмечено Нобелевской премией по экономике 2012 года.
Решение задачи было описано в 1962 году математиками Дэвидом Гейлом (Университет Брауна) и Ллойдом Шепли (Принстонский университет) в статье «Поступление в колледж и стабильность браков» (College admissions and the stability of marriage) в журнале American Mathematical Monthly[2]. Набор правил, следование которым всегда приводит к образованию стабильных пар, получил название алгоритма Гейла-Шепли или «алгоритма отложенного согласия».
Множество практических механизмов на основе алгоритма Гейла-Шепли разработал нобелевский лауреат Элвин Рот. Эти механизмы были внедрены в деятельность больниц по набору врачей[3] и интернов[4], в правила многих американских профессиональных спортивных ассоциаций по набору спортсменов в команды[5]. В соответствии с предложенными институциональными механизмами фирмы набирают на стажировку сотрудников[6], суды нанимают секретарей[7], родители находят подходящие школы для детей[8]. Модель марьяжа в целом описывает последовательность действий индивидов при формировании пар на «рынках попутчиков» для совместных поездок, в некоторых видах спорта (парное фигурное катание, спортивные танцы), поведение участников в интерактивных реалити-шоу и пр[9].
Задачу можно сформулировать следующим образом:
Пусть даны два множества M и Ж, причём для каждого элемента из М элементы из Ж отсортированы в некотором порядке. То есть мы можем говорить, какие элементы Ж для данного элемента m из М являются более предпочтительными, а какие менее. Сортировки, конечно же, для каждого элемента могут быть свои. Аналогичные предпочтения введены и для элементов из Ж. Суть задачи сводится к разбиению M и Ж на пары. В каждую пару берется по одному элементу из M и из Ж. При этом в результате мы должны получить не просто разбиение, а так называемое стабильное разбиение. Стабильность — общее понятие для теории игры, которое в данном конкретном случае означает, что отсутствуют пары (m, ж) и (m', ж'), обладающие таким свойством: для m элемент ж' является предпочтительнее ж, а для ж' элемент m является предпочтительнее m'.
— Андрей Коняев. Давай поженимся. // Lenta.ru 15.10.2012
Существует конструктивный метод нахождения одного из решений задачи.
Максимальное количество шагов для реализации алгоритма: n² шагов, где n — число мужчин и женщин.
В результате невозможно завести новый брак — если у мужчины А в списке есть женщина Б и наоборот, хотя бы один женится. Соответственно, если списки полные, женятся все мужчины или все женщины.
Аналогично женщины могут ходить по мужчинам. Совпадают ли получившиеся браки? Нет, и контрпример прост. Пусть есть два мужчины и две женщины. Андрей хочет Веру, Борис — Галю. Женщины наоборот — Вера Бориса, Галя Андрея (но и на другом жениться или выйти замуж все четверо не прочь). Если мужчины ходят по женщинам — Андрей женится на Вере, Борис на Гале. Если женщины по мужчинам — Андрей на Гале, Борис на Вере.
При этом, если мужчины делают предложения женщинам, мужчины получат самый лучший для себя результат из всех устойчивых паросочетаний: не существует устойчивого паросочетания, чтобы все мужчины оказались в том же или лучшем положении. Для женщин результат, наоборот, будет наихудшим.
Пример на языкe Си:
#include"conio.h"
#include"stdio.h"
int make_offer(int);
const int n = 5 + 1; // dlya matritsy 5x5
int mass_index[n]; //massiv tekuschego indeksa muzhchin
int mass_offer[n]; // massiv tekuschih predlozheniy zhenschin
int massA[n][n],massB[n][n];
int global_i;
void main(){
int i,j,offer,count,count_0=0;
for (i=1;i<n;i++){mass_index[i] = 1; mass_offer[i] = -1;};
FILE *f;
f = fopen("input.txt","r");
for (i=1; i<n; i++)
for (j=1; j<n; j++)
fscanf(f,"%d", &massA[i][j]);
for (i=1; i<n; i++)
for (j=1; j<n; j++)
fscanf(f,"%d", &massB[i][j]);
fclose(f);
global_i = 1;
int x;
while (count_0 != n-1){
x = make_offer(global_i);
if (x == 0){
count_0++;
global_i = count_0 + 1;
}
else global_i = x;
}
for (i=1; i<n; i++)
printf("%d - %d \n", i, mass_offer[i] );
getch();
}
int make_offer(int count){
int offer, i;
offer = massA[count][mass_index[count]];
if (mass_offer[offer] == -1){
mass_offer[offer] = count;
return 0;
}
else{
for (i=1; i<n; i++){
if ((massB[offer][i] == mass_offer[offer]) | (massB[offer][i] == count))
if (massB[offer][i] == mass_offer[offer]){
mass_index[count]++;
return count;
}
else{
int x = mass_offer[offer];
mass_index[mass_offer[offer]]++;
mass_offer[offer] = count;
return x;
}
}
}
}
// Coding: Anikin Dmitry
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .