| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Задача об устойчивом бракосочетании. |
| Автор: mur88 26.3.2008, 01:41 |
| УСЛОВИЕ ЗАДАЧИ Задача об устойчивом бракосочетании. Пусть В — множе¬ство из п юношей, a G — множество из п девушек. Каждый юноша оценивает девушек числами от 1 до n, и каждая девушка оценивает юношей числами от 1 до п. Паросочетанием называется взаимно однозначное соответствие между юношами и девушками. Паросочетание устойчиво, если для любых двух юношей b1 и b2 и соответствующих им в этом паросочетании девушек g1 и g2 выполняются следующие два условия: 1) либо b1 оценивает g1 выше, чем g2, либо g2 оцениваеяет b2 выше,чем b1 ; 2) либо b2 оценивает g2 выше, чем g1, либо g1 оценивает b1 выше, чем b2 . Докажите, что устойчивое паросочетание всегда существует, и напишите алгоритм для нахождения одного из таких паросочетаний. КОНЕЦ Кто ни будь знает где можно достать описание этой задачи или что угодно связанное с ней !!!! Сам просмотрел кучу книг но увы не нашел ничего связочного с этой задачей :( |
| Автор: maxdiver 26.3.2008, 11:47 |
| http://en.wikipedia.org/wiki/Stable_marriage_problem |