вторник, 17 октября 2017
19:24

Шано
- ты ведь, наверно, слышала про алгоритм Гейла-Шепли (Gale-Shapley)?
Вкратце, там так: каждый из n мальчиков и n девочек упорядочивает всех участников противоположного пола в порядке
убывания привлекательности. Наша задача разбить их на пары, так чтобы ситуация была стабильна, то есть не было бы мальчика и девочки, которые предпочитают друг друга своим партнерам.
Оказывается, что это всегда возможно. В первом раунде каждый мальчик делает предложения первой девочке в своем списке. Девочки, у которых есть предложения, выбирают лучшее (в соответствие со своим списком) и обручаются. Во втором раунде все отвергнутые мальчике делают предложения следующим девочкам в своих списках. Девочки, получившие предложения опять выбирают лучшее. Это так же относится к уже обрученным - они выбирают лучшего среди сделавших предложение и текущего жениха. Ну и так далее.
Это все заканчивается стабильной разбивкой на пары. Что интересно, в результате этого алгоритма, каждая девочка оказывается в самом плохом браке (из всех для нее возможных при стабильной разбивке на пары), а у мальчиков все наоборот. Конечно, если поменять роли, алгоритм становится оптимальным для девочек.
По-моему, очень убедительно, надо делать предложения, а не ждать их.
sumka-mumi-mamy.livejournal.com/353364.html?thr...

@темы: женский вопрос

URL
Комментарии
18.10.2017 в 10:52

Интендант 1 ранга
Wein, Weiber, Waffen
Это доказывает исключительно, что такие вопросы нельзя доверять решать самостоятельно глупым и ненадёжным человекам :gigi:
URL
18.10.2017 в 11:05

-Bait-
В основе всего лежит равноценный обмен ...
Какой маразм.:)
URL
18.10.2017 в 12:32

TrashTank
"Можно выклянчить все! Деньги, славу, власть, но только не Родину… Особенно такую, как моя Россия"
такие вопросы нельзя доверять решать самостоятельно глупым и ненадёжным человекам
Реквестируется робот-сваха? :marry:
URL
18.10.2017 в 12:36

Интендант 1 ранга
Wein, Weiber, Waffen
Реквестируется робот-сваха? :marry:

Именно! Нужно написать алгоритм, который находил бы в этой игре равновесие по Парето :)
И все строем в ЗАГС согласно полученному списку — к светлому технократическому будущему!
URL
18.10.2017 в 12:38

Шано
суворов, говорят, просто строил брачующихся по росту. самодур был
URL
18.10.2017 в 12:40

Интендант 1 ранга
Wein, Weiber, Waffen
Шано, у меня есть неподтверждённая версия, что результат такого метода будет отличаться в плане успешности от выбора нынешних "современных и независим личностей" в пределах статпогрешности :)
URL
18.10.2017 в 12:41

Шано
а мне кажется, ничуть не будет отличаться))
URL