Страница 1 из 1
Stable marriage (matching)
Добавлено: 20 мар 2005, 13:25
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'?
Добавлено: 20 мар 2005, 20:42
Vovik
Слушай, а можно более подробно, что нужно сделать? А то я так и не понял, это типа паросочитания или как?
Добавлено: 21 мар 2005, 16:12
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
Но мне нужно разроботать алгоритм где количество женщин больше количества мужшин или в моём случае количество студентов больше чем количество компаний, поэтому и прошу помощи так как сам пока не додумался. Как вы видели каждая компания может выбирать из большого количества студентов, но студенты могут выбирать из более ограниченного списка
Добавлено: 21 мар 2005, 22:33
Vovik
По какому критерию оптимальное? Компании расположены у студентов в порядке предпочтения?
Короче какой параметр, кроме количества пар, нужно оптимизировать. Что означает "w prefers m to her fiancé m'"
Добавлено: 21 мар 2005, 23:22
michael
Извини- ты конечно прав я исходил из того что это довольно известный алгоритм. Объяснение-
Каждый муж. имеет список придпочтений жен. также как и жен. имеют список предпочитаемых муж.
Муж предлагает себя жен. Если та свободна она всегда соглашается. Если жен. не свободна но муж. предлагаюший ей себя стоит на более высоком месте в её приорететах (т.е. сейчас она с муж. номер 2 , а ей себя предлагает муж. номер 1) она бросает своего "жениха" ради более высокого приоритета. В другом случае жен. отвергает муж. Как результат после выполнения алгоритма создаются "прочные связи". Т.е. не возможно найти более удачного сочетания пар. Короче все счастливы и "я там был мёд пиво пил...." да не о том сказка. Дело в том , что счастливы они по той самой причине , что количество муж.=количество жен. В моей же проблеме количество жен. больше чем муж. Значит не все будут счастливы. Надо разработать алгоритм который для моего случая (компании студенты) тоже дал бы "прочные связи". (оптимальные если уж так хочется)
Добавлено: 22 мар 2005, 01:27
Vovik
OK. Теперь почти понятно. А почему твой алгоритм не работает, когда m<n? В таоем примере получается
Intel - Mike
Microsoft - Vasya
Ipm - John
все получили что хотели.
Добавлено: 22 мар 2005, 02:12
Oscar
Vovik, как видно - не все.
Лёню и Петю явно обидели.
Добавлено: 22 мар 2005, 09:23
michael
mne nujno 4to bi bili s4astlivi studenti a ne kompanii
Добавлено: 23 мар 2005, 00:46
Vovik
Тогда за чем было писать, что оптимальный для мужчин (ведь роль мужчин выполняют компании)? Ладно, звиняюсь что туплю, но я не могу понять точно не разобравшись в вопросе:
Чем паросочитание:
Intel-Mike
Microsoft - Vasya
Ibm - John
лучше или хуже например такого
Intel - Mike
Microsoft - Lenia
Ibm - John
? точнее интересует, по какому формальному критерию сравнивается оптимальность паросочитания? Какая характеристика должна быть лучше?
Добавлено: 23 мар 2005, 12:05
michael
оптимальное это - даже если студент последний в списке компании и эта же компания последняя в списке студента, но не возможно найти сочетания где эта компания хотела бы другово студента и тот студент тоже хотел бы её то связь называется "прочной" т.е. оптимальной