Изменения

Перейти к: навигация, поиск

Задача об устойчивом паросочетании

1131 байт убрано, 14:26, 12 января 2018
→‎Описание в псевдокоде
=== Описание в псевдокоде ===
<!---Здесь мы воспользуемся вспомогательной константой <tex>\Omega</tex>, которая будет означать худший выбор для всех женщин, очень нежелательного мужчину (и̶з̶в̶р̶а̶щ̶е̶н̶е̶ц̶ ̶т̶у̶п̶о̶й̶). Изначально все женщины помолвлены с <tex>\Omega</tex>. По завершении алгоритма все мужчины будут заняты, поэтому каждая женщина будет замужем не за <tex>\Omega</tex>.---
k ← 0; {все женщины (временно) помолвлены с Ω}
while k < n do
begin X ← (k + 1)-ый мужчина;
while X 6= Ω do
begin x ← лучшая кандидатура из текущего списка предпочтений
мужчины X;
if x предпочитает мужчину X своему жениху then
begin
помолвка X и x;
X ← предыдущий жених женщины x
end;
if X 6= Ω then
вычёркиваем x из текущего списка предпочтений мужчины X;
end;
k ← k + 1
end;
--->
 
 
<font color="green">// Изначально все мужчины не женаты и все женщины незамужние.</font>
'''while''' Существует существует свободный мужчина M <- некоторый свободный мужчина
w <- первая женщина из текущего списка M
'''if''' w свободна
помечаем M и w помолвленными
'''else if''' w предпочитает M своему "текущему" жениху M'
помечаем M и w помолвленными
помечаем M' свободным
'''else'''
вычёркиваем w отказывает из списка предпочтений M
Время работы алгоритма {{---}} <tex>O(n^2)</tex>, так как количество итераций цикла <tex>\mathrm {while}</tex> не превосходит <tex>O(n^2)</tex>.
I am dark black
693
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/63456»

Навигация