|
Проблема стабільних шлюбівПроблема стабільних шлюбів (англ. Stable Matching Problem або SMP) — математична задача знаходження стабільної відповідності між членами двох множин елементів згідно з їхніми перевагами для кожного елемента. Відповідності — це поєднання елементів однієї множини з елементами іншої. Відповідності є стабільним, коли не існує жодної альтернативи спаровування (A, B). Тобто, нема інших елементів, які б краще підійшли до елементів А і В. ФормулюванняПроблема стабільного шлюбу зазвичай сформулюється так: Уявимо, що існує n чоловіків та n жінок, і кожна людина ранжує всіх членів протилежної статі унікальним номером від 1 до N в порядку надання переваг. Якщо одружуються чоловіки і жінки разом так, що немає двох людей протилежної статі, які б були кращі одне для одного, ніж їхні нинішні партнери, то всі шлюби «стабільний». Стабільне одруження називається оптимальним по відношенню до чоловіків, якщо не існує іншого такого стабільного одруження, в якому якомусь чоловікові відповідала жінка, якій він надавав би більше переваг, ніж та, яка присвоєна йому на початку. Алгоритми пошуку вирішення проблеми стабільного шлюбу застосовується в різних реальних ситуаціях, мабуть, найвідомішим з яких є в розподіл випускників медичних закладів та їхніх перших лікарень.[1] Розв'язанняУ 1962 році Девід Гейл і Ллойда Шеплі довели, що для будь-якої рівної кількості чоловіків і жінок завжди можна вирішити задачу SMP і зробити всі шлюби стабільними. Вони представили алгоритм для цього.[2][3] Алгоритм Гейл-Шеплі включає в себе ряд «раундів» (або «ітерацій»), де кожний чоловік не пов'язаний зобов'язанням «робити пропозицію» найбільш привабливій жінці, якій він ще не пропонував. Кожна жінка після обмірковування пропозицій всіх її женихів говорить одному, кому найбільше віддає перевагу «Може бути», а всім іншим — «Ні». У цей час вона віддає перевагу одному найкращому на її погляд нареченому, а наречений у цей час найбільше віддає перевагу нареченій. У першому раунді:
У наступному раунді:
Тимчасовий характер зобов'язань зберігає право вже зайнятій жінці шукати кращого партнера. Цей алгоритм гарантує, що:
Алгоритмfunction stableMatching {
Initialize all m ∈ M and w ∈ W to free
while ∃ free man m who still has a woman w to propose to {
w = m's highest ranked such woman to whom he has not yet proposed
if w is free
(m, w) become engaged
else some pair (m', w) already exists
if w prefers m to m'
(m, w) become engaged
m' becomes free
else
(m', w) remain engaged
}
}
Оптимальність рішенняУ той час як рішення стійке, воно не обов'язково оптимальне з точки зору всіх осіб. Традиційна форма алгоритму є оптимальною для ініціатора пропозиції. Оптимальне рішення ініціатора може бути або може не бути оптимальним для рецензента пропозиції. Як приклад можна розглянути наступну ситуацію:
A: YXZ B: ZYX C: XZY X: BAC Y: CBA Z: ACB Існує 3 стабільні рішення для цієї ситуації:
Всі три поєднання є стабільними, оскільки нестабільність вимагає, щоб учасники були щасливішими з альтернативними партнерами. Обрання ініціаторами найкращих на їхній погляд альтернатив гарантує, що поєднання є стабільними, тому що вони були б незадоволені будь-якою іншою пропонованою альтернативою. Якщо надається перевага другій найкращій альтернативі, це гарантує, що будь-яке інше поєднання не буде подобатись одній зі сторін. Алгоритм сходиться в єдиному раунді, тому що кожен рецензент отримує рівно одну пропозицію, і тому обирає, що пропозиція є його найкращим вибором. Ця асиметрія оптимальності спричиняється тим фактом, що у ініціаторів є весь набір, щоб вибрати, а рецензенти пропозиції вибирають з обмеженого набору женихів в будь-який момент часу. Реалізація алгоритмуРеалізація мовою Scala: /**
* Problem description
*
* Given an equal number of men and women to be paired for marriage,
* each man ranks all the women in order of his preference and each women ranks all the men in order of her preference.
*
* A stable set of engagements for marriage is one where no man prefers a women over the one he is engaged to,
* where that other woman also prefers that man over the one she is engaged to. I.e. with consulting marriages,
* there would be no reason for the engagements between the people to change.
*
* @author Oleksandr KOL Kucher
*/
object Marriage {
/**
* solves Marriage problem
* @param boyPrefers - map of all Boys and their prefers
* @param girlPrefers - map of all Girls and their prefers
* @return list of couples
*/
def solve(boyPrefers: Map[String, Array[String]], girlPrefers: Map[String, Array[String]]): List[Couple] = {
val (boys, girls) = mapsToPersons(boyPrefers, girlPrefers)
searchCouples(boys, girls)
}
/**
* verifies if created couples stable
* @param boyPrefers - map of all Boys and their prefers
* @param girlPrefers - map of all Girls and their prefers
* @param couples - list of created couples
* @return true or false
*/
def isStable(boyPrefers: Map[String, Array[String]], girlPrefers: Map[String, Array[String]], couples: List[Couple]): Boolean = {
val (boys, girls) = mapsToPersons(boyPrefers, girlPrefers)
val boyCouple: Map[String, Girl] = couples.map(c => c.boy.name -> c.girl).toMap
val girlCouple: Map[String, Boy] = couples.map(c => c.girl.name -> c.boy).toMap
boys.foreach(b => b.fiance = boyCouple(b.name))
girls.foreach(g => g.fiance = girlCouple(g.name))
for(boy <- boys){
for(girl <- girls){
if(boy.isPrefers(girl) && girl.isPrefers(boy)){
return false
}
}
}
true
}
/**
* gets two maps with names and prefers (one for boys and one for girls)
* and create for each person his/her own object with his/her own prefers
*
* @param boyPrefers - map with all boys' prefers
* @param girlPrefers - map with all girls' prefers
* @return tuple with list of Boy and list of Girl that have all their prefers
*/
private def mapsToPersons(boyPrefers: Map[String, Array[String]], girlPrefers: Map[String, Array[String]]): (List[Boy], List[Girl]) = {
val (boyNames, girlNames) = (boyPrefers.keySet.toList, girlPrefers.keySet.toList)
val (boysMap, girlsMap) = (boyNames.map(name=> name -> new Boy(name)).toMap, girlNames.map(name => name -> new Girl(name)).toMap)
boyNames.foreach(name => boysMap(name).prefers = boyPrefers(name).map(gName => girlsMap(gName)))
girlNames.foreach(name => girlsMap(name).prefers = girlPrefers(name).map(gName => boysMap(gName)))
(boysMap.values.toList, girlsMap.values.toList)
}
/**
* Searches all couples and return list of them
* @param boys - list of all Boys
* @param girls - list of all Girls
*/
private def searchCouples(boys: List[Boy], girls: List[Girl]): List[Couple] = {
/**
* makes couples from Boys and Girls with using Girls' boyfriends
* @param girls - list of Girls
* @param couples - list of created couples
*/
def toCouples(girls: List[Girl], couples: List[Couple]): List[Couple] = {
if(girls.isEmpty) couples
else toCouples(girls.tail, couples ::: List(new Couple(girls.head.fiance, girls.head)))
}
iterateBoys(boys)
toCouples(girls, List())
}
/**
* gets all free boys and runs for each of them function `@link project.marriageProblem.Marriage.iterateBoyPrefers`
* @param freeBoys - list of Boys which has not a couple yet
*/
private def iterateBoys(freeBoys: List[Boy]): Unit = {
if(freeBoys.nonEmpty) iterateBoys(iterateBoyPrefers(freeBoys.head, freeBoys.head.prefers, freeBoys.tail))
}
/**
*
* @param boy - current free Boy
* @param girls - prefers of current free Boy
* @param freeBoys - rest free Boys
* @return new list of free boys
* it can be:
* 1. empty
* 2. contains rest free boys
* 3. contains rest free boys with one boy which has couple and was replaced by current boy
*/
private def iterateBoyPrefers(boy: Boy, girls: Array[Girl], freeBoys: List[Boy]): List[Boy] = {
if(girls.isEmpty) freeBoys
else if(null == girls.head.fiance){
girls.head.fiance = boy
boy.fiance = girls.head
boy.prefers = girls.tail
freeBoys
} else if(girls.head.prefers.indexOf(girls.head.fiance) > girls.head.prefers.indexOf(boy)){
val boyfriend: Boy = girls.head.fiance
girls.head.fiance = boy
boy.fiance = girls.head
boy.prefers = girls.tail
freeBoys ::: List(boyfriend)
} else {
boy.prefers = girls.tail
iterateBoyPrefers(boy, girls.tail, freeBoys)
}
}
}
/**
* Class represents Girl
* @param name - name of Girl
* @param fiance - Girl's boyfriend
* @param prefers - Girl's prefers
*/
class Girl(val name: String, var fiance: Boy, var prefers: Array[Boy]) {
def this(name: String, prefers: Array[Boy]) = this(name, null, prefers)
def this(name: String) = this(name, null, null)
override def toString: String = name
def isPrefers(other: Boy): Boolean =
prefers.indexWhere(p => p.name == other.name) < prefers.indexWhere(p => p.name == fiance.name)
}
/**
* Class represents Boy
* @param name - name of Boy
* @param fiance - Boy's girlfriend
* @param prefers - Boy's prefers
*/
class Boy(val name: String, var fiance: Girl, var prefers: Array[Girl]) {
def this(name: String, prefers: Array[Girl]) = this(name, null, prefers)
def this(name: String) = this(name, null)
override def toString: String = name
def isPrefers(other: Girl): Boolean =
prefers.indexWhere(p => p.name == other.name) < prefers.indexWhere(p => p.name == fiance.name)
}
class Couple(val boy: Boy, val girl: Girl){
override def toString: String = boy.name + " -> " + girl.name
}
object Test extends App {
val boyPrefers: Map[String, Array[String]] = Map(
"abe" -> Array("abi", "eve", "cath", "ivy", "jan", "dee", "fay", "bea", "hope", "gay"),
"bob" -> Array("cath", "hope", "abi", "dee", "eve", "fay", "bea", "jan", "ivy", "gay"),
"col" -> Array("hope", "eve", "abi", "dee", "bea", "fay", "ivy", "gay", "cath", "jan"),
"dan" -> Array("ivy", "fay", "dee", "gay", "hope", "eve", "jan", "bea", "cath", "abi"),
"ed" -> Array("jan", "dee", "bea", "cath", "fay", "eve", "abi", "ivy", "hope", "gay"),
"fred" -> Array("bea", "abi", "dee", "gay", "eve", "ivy", "cath", "jan", "hope", "fay"),
"gav" -> Array("gay", "eve", "ivy", "bea", "cath", "abi", "dee", "hope", "jan", "fay"),
"hal" -> Array("abi", "eve", "hope", "fay", "ivy", "cath", "jan", "bea", "gay", "dee"),
"ian" -> Array("hope", "cath", "dee", "gay", "bea", "abi", "fay", "ivy", "jan", "eve"),
"jon" -> Array("abi", "fay", "jan", "gay", "eve", "bea", "dee", "cath", "ivy", "hope")
)
val girlPrefers: Map[String, Array[String]] = Map(
"abi" -> Array("bob", "fred", "jon", "gav", "ian", "abe", "dan", "ed", "col", "hal"),
"bea" -> Array("bob", "abe", "col", "fred", "gav", "dan", "ian", "ed", "jon", "hal"),
"cath" -> Array("fred", "bob", "ed", "gav", "hal", "col", "ian", "abe", "dan", "jon"),
"dee" -> Array("fred", "jon", "col", "abe", "ian", "hal", "gav", "dan", "bob", "ed"),
"eve" -> Array("jon", "hal", "fred", "dan", "abe", "gav", "col", "ed", "ian", "bob"),
"fay" -> Array("bob", "abe", "ed", "ian", "jon", "dan", "fred", "gav", "col", "hal"),
"gay" -> Array("jon", "gav", "hal", "fred", "bob", "abe", "col", "ed", "dan", "ian"),
"hope" -> Array("gav", "jon", "bob", "abe", "ian", "dan", "hal", "ed", "col", "fred"),
"ivy" -> Array("ian", "col", "hal", "gav", "fred", "bob", "abe", "ed", "jon", "dan"),
"jan" -> Array("ed", "hal", "gav", "abe", "bob", "jon", "col", "ian", "fred", "dan")
)
println("Test Solving Marriage Problem:")
val couples: List[Couple] = Marriage.solve(boyPrefers, girlPrefers).sortBy(_.boy.name)
couples.foreach(println)
println("Stable = " + Marriage.isStable(boyPrefers, girlPrefers, couples) + "\n")
println("Switching fred & jon's partners")
val (fred, jon) = (couples(5), couples(9))
val switchedCouples: List[Couple] = couples.updated(5, new Couple(fred.boy, jon.girl)).updated(9, new Couple(jon.boy, fred.girl))
switchedCouples.foreach(println)
println("Stable = " + Marriage.isStable(boyPrefers, girlPrefers, switchedCouples))
}
Результат: Solving Marriage Problem: abe -> ivy bob -> cath col -> dee dan -> fay ed -> jan fred -> bea gav -> gay hal -> eve ian -> hope jon -> abi Stable = true Switching fred & jon's partners abe -> ivy bob -> cath col -> dee dan -> fay ed -> jan fred -> abi gav -> gay hal -> eve ian -> hope jon -> bea Stable = false Див. також
Посилання
Джерела
Посилання
|
