Stable marriage (matching)

[michael]

Pomogite naiti Stable marriage (matching) dlia sleduwego polojenia

Company List:

Intel: Mike,Vasia,Lenia,Petia,John
Microsoft: Vasia,Lenia,John,Mike,Petia
Ibm: John,Mike,Petia,Lenia,Vasia

Student List:

Mike: Intel,Ibm,Microsoft
Vasia: Ibm,Microsoft,Intel
Lenia: Intel,Microsoft,Ibm
Petia: Intel,Ibm,Microsoft
John: Ibm,Microsoft,Intel

Company delaiut predlojenia Student. Kak eto sdelat'?

[Vovik]

Слушай, а можно более подробно, что нужно сделать? А то я так и не понял, это типа паросочитания или как?

[michael]

Да паросочитаний.
При количестве m мужшин и n женшин (m=n) находит оптимальное (для мужшин) сочетание пар. Вот алгоритм

Код: Выделить всё

Initialize each person to be free.
         while (some man m is free and hasn't proposed to every woman)
            w = first woman on m's list to whom m has not yet proposed
         if (w is free)
             assign m and w to be engaged
        else if (w prefers m to her fiancé m')
             assign m and w to be engaged, and m' to be free
        else
            w rejects m

Но мне нужно разроботать алгоритм где количество женщин больше количества мужшин или в моём случае количество студентов больше чем количество компаний, поэтому и прошу помощи так как сам пока не додумался. Как вы видели каждая компания может выбирать из большого количества студентов, но студенты могут выбирать из более ограниченного списка

[Vovik]

По какому критерию оптимальное? Компании расположены у студентов в порядке предпочтения?

Короче какой параметр, кроме количества пар, нужно оптимизировать. Что означает "w prefers m to her fiancé m'"

[michael]

Извини- ты конечно прав я исходил из того что это довольно известный алгоритм. Объяснение-
Каждый муж. имеет список придпочтений жен. также как и жен. имеют список предпочитаемых муж.
Муж предлагает себя жен. Если та свободна она всегда соглашается. Если жен. не свободна но муж. предлагаюший ей себя стоит на более высоком месте в её приорететах (т.е. сейчас она с муж. номер 2 , а ей себя предлагает муж. номер 1) она бросает своего "жениха" ради более высокого приоритета. В другом случае жен. отвергает муж. Как результат после выполнения алгоритма создаются "прочные связи". Т.е. не возможно найти более удачного сочетания пар. Короче все счастливы и "я там был мёд пиво пил...." да не о том сказка. Дело в том , что счастливы они по той самой причине , что количество муж.=количество жен. В моей же проблеме количество жен. больше чем муж. Значит не все будут счастливы. Надо разработать алгоритм который для моего случая (компании студенты) тоже дал бы "прочные связи". (оптимальные если уж так хочется)

[Vovik]

OK. Теперь почти понятно. А почему твой алгоритм не работает, когда m<n? В таоем примере получается
Intel - Mike
Microsoft - Vasya
Ipm - John
все получили что хотели.

[Oscar]

Vovik, как видно - не все.
Лёню и Петю явно обидели.

[michael]

mne nujno 4to bi bili s4astlivi studenti a ne kompanii

[Vovik]

Тогда за чем было писать, что оптимальный для мужчин (ведь роль мужчин выполняют компании)? Ладно, звиняюсь что туплю, но я не могу понять точно не разобравшись в вопросе:
Чем паросочитание:
Intel-Mike
Microsoft - Vasya
Ibm - John
лучше или хуже например такого
Intel - Mike
Microsoft - Lenia
Ibm - John
? точнее интересует, по какому формальному критерию сравнивается оптимальность паросочитания? Какая характеристика должна быть лучше?

[michael]

оптимальное это - даже если студент последний в списке компании и эта же компания последняя в списке студента, но не возможно найти сочетания где эта компания хотела бы другово студента и тот студент тоже хотел бы её то связь называется "прочной" т.е. оптимальной