Задача о больницах и резидентах: различия между версиями

Перейти к навигации Перейти к поиску
Нет описания правки
Метка: visualeditor-switched
Нет описания правки
Метка: visualeditor-switched
Строка 3: Строка 3:


== Постановка задачи ==
== Постановка задачи ==
Экземпляр I задачи о больницах и резидентах (HR) [5, 6, 14] включает множество <math>R = \{ r_1, ..., r_n \}</math> ''резидентов'' и множество <math>H = \{ h_1, ..., h_m \} </math> ''больниц''. Каждая больница <math>h_j \in H<nowiki></math></nowiki> имеет ''кадровый потенциал'' в виде целого положительного числа, обозначаемый <math>c_j</math>. Также каждый резидент <math>r_i \in R</math> имеет ''список предпочтений'', в котором он ранжирует подмножество H в строгом порядке. Пара <math>(r_i, h_j) \in R \times H</math> называется ''приемлемой'', если <math>h_j</math> содержится в списке предпочтений ri; в этом случае говорят, что ri считает <math>h_j</math> приемлемой. Аналогично, каждая больница hj 2 H имеет список предпочтений, в котором она располагает в строгом порядке тех резидентов, которые считают эту больницу приемлемой. Пусть имеются три любых агента x, y, z 2 R[H; можно сказать, что x предпочитает агента y агенту z, если x находит приемлемым их обоих и y предшествует z в списке предпочтений x. Пусть C =
Экземпляр I задачи о больницах и резидентах (HR) [5, 6, 14] включает множество <math>R = \{ r_1, ..., r_n \}</math> ''резидентов'' и множество <math>H = \{ h_1, ..., h_m \} </math> ''больниц''. Каждая больница <math>h_j \in H<nowiki></math></nowiki> имеет ''кадровый потенциал'' в виде целого положительного числа, обозначаемый <math>c_j</math>. Также каждый резидент <math>r_i \in R</math> имеет ''список предпочтений'', в котором он ранжирует подмножество H в строгом порядке. Пара <math>(r_i, h_j) \in R \times H</math> называется ''приемлемой'', если <math>h_j</math> содержится в списке предпочтений <math>r_i</math>; в этом случае говорят, что <math>r_i</math> считает <math>h_j</math> приемлемой. Аналогично, каждая больница <math>h_j \in H</math> имеет список предпочтений, в котором она располагает в строгом порядке тех резидентов, которые считают эту больницу приемлемой. Пусть имеются три любых агента <math>x, y, z \in R \cup H</math>; можно сказать, что x ''предпочитает'' агента y агенту z, если x находит приемлемым их обоих и y предшествует z в списке предпочтений x. Пусть <math>C = \sum_{h_j \in H} c_j</math>.




Обозначим за A множество допустимых пар в I, L = jAj. Назначение M является подмножеством A. Если (ri ;hj) 2 M, то считается, что резидент ri назначен больнице <math>h_j</math>, а больница <math>h_j</math> – резиденту ri. Для каждого q 2 R [ H множество назначенных q в M обозначается M(q). Если ri 2 R и M(ri) = ;, то считается, что ri не назначен, в противном случае ri назначен. Аналогично, любая больница hj 2 H является недоукомплектованной, полной или переукомплектованной, если jM(hj)j меньше, равна или больше cj, соответственно.
Обозначим за A множество допустимых пар в I, L = jAj. Назначение M является подмножеством A. Если <math>(r_i, h_j) \in M</math>, то говорят, что резидент <math>r_i</math> назначен больнице <math>h_j</math>, а больница <math>h_j</math> – резиденту <math>r_i</math>. Для каждого q 2 R [ H множество назначенных q в M обозначается M(q). Если ri 2 R и M(ri) = ;, то считается, что <math>r_i</math> не назначен, в противном случае <math>r_i</math> назначен. Аналогично, любая больница hj 2 H является недоукомплектованной, полной или переукомплектованной, если jM(hj)j меньше, равна или больше cj, соответственно.




Паросочетанием M называется назначение, такое, что jM(ri)j < 1 для каждого ri 2 R и jM(hj)j < cj для каждого hj 2 H (т. е. ни один резидент не назначен в неподходящую больницу, каждый резидент назначен не более чем в одну больницу и ни одна больница не переукомплектована). Для удобства обозначений, если даны паросочетание M и резидент ri 2 R такой, что M(ri) ф ;, то в случаях, когда это не вызывает двусмысленности, обозначение M(ri) также используется для обозначения единственного члена M(ri).
Паросочетанием M называется назначение, такое, что <math>|M(r_i) < 1</math> для каждого <math>r_i \in R</math> и jM(hj)j < cj для каждого hj 2 H (т. е. ни один резидент не назначен в неподходящую больницу, каждый резидент назначен не более чем в одну больницу и ни одна больница не переукомплектована). Для удобства обозначений, если даны паросочетание M и резидент ri 2 R такой, что M(ri) ф ;, то в случаях, когда это не вызывает двусмысленности, обозначение <math>M(r_i)</math> также используется для обозначения единственного члена <math>M(r_i)</math>.




Пара (ri, hj) 2 AnM блокирует паросочетание M (или является блокирующей парой для M), если относительно M выполняются следующие условия:
Пара (ri, hj) 2 AnM блокирует паросочетание M (или является блокирующей парой для M), если относительно M выполняются следующие условия:
1. резидент ri не назначен или предпочитает M(ri) больницу <math>h_j</math>;
1. резидент <math>r_i</math> не назначен или предпочитает M(ri) больницу <math>h_j</math>;
2. больница недоукомплектована или предпочитает резидента ri хотя бы одному члену M(hj) (или обоим).
2. больница недоукомплектована или предпочитает резидента <math>r_i</math> хотя бы одному члену M(hj) (или обоим).
   
   


Строка 23: Строка 23:


M :=  
M :=  
while (некоторый резидент ri не назначен и ri имеет непустой список) { <math>h_j</math> := первая больница в списке ri; /* ri применяется к hj */ M:=M[f(ri;hj)g; if(hj is переукомплектована) {
while (некоторый резидент <math>r_i</math> не назначен и <math>r_i</math> имеет непустой список) { <math>h_j</math> := первая больница в списке <math>r_i</math>; /* <math>r_i</math> подает заявку в hj */ M:=M[f(ri;hj)g; if(hj is переукомплектована) {
rk := худший резидент в M(hj) согласно списку <math>h_j</math>; M:=Mnf(rk;hj)g; } if (hj полна) {
rk := худший резидент в M(hj) согласно списку <math>h_j</math>; M:=Mnf(rk;hj)g; } if (hj полна) {
rk := худший резидент в M(hj) согласно списку <math>h_j</math>; для (каждого преемника rl из rk в списке <math>h_j</math>) удалить пару (rl ; hj)
rk := худший резидент в M(hj) согласно списку <math>h_j</math>; для (каждого преемника rl из rk в списке <math>h_j</math>) удалить пару (rl ; hj)
Строка 30: Строка 30:




Расширенная версия алгоритма Гэйла/Шепли для задачи HR показана на рис. 1. Алгоритм включает в себя последовательность операций apply (подать заявку) и delete (удалить). На каждой итерации цикла while некоторый не назначенный резидент ri с непустым списком предпочтений подает заявку в первую больницу <math>h_j</math> в его списке и становится временно назначенным в <math>h_j</math> (впоследствии это назначение может быть отменено). Если в результате этого назначения больница <math>h_j</math> становится переукомплектованной, то она отказывается от худшего из назначенных резидентов rk. Далее, если больница <math>h_j</math> полна (независимо от того, была ли она переукомплектована ранее на той же итерации цикла), то для каждого резидента rl, которого <math>h_j</math> считает менее желательным, чем его худший резидент rk, алгоритм удаляет пару (rl,hj), что включает удаление <math>h_j</math> из списка предпочтений rl и наоборот.
Расширенная версия алгоритма Гэйла/Шепли для задачи HR показана на рис. 1. Алгоритм включает в себя последовательность операций apply (подать заявку) и delete (удалить). На каждой итерации цикла while некоторый не назначенный резидент <math>r_i</math> с непустым списком предпочтений подает заявку в первую больницу <math>h_j</math> в его списке и становится временно назначенным в <math>h_j</math> (впоследствии это назначение может быть отменено). Если в результате этого назначения больница <math>h_j</math> становится переукомплектованной, то она отказывается от худшего из назначенных резидентов rk. Далее, если больница <math>h_j</math> полна (независимо от того, была ли она переукомплектована ранее на той же итерации цикла), то для каждого резидента rl, которого <math>h_j</math> считает менее желательным, чем его худший резидент rk, алгоритм удаляет пару (rl,hj), что включает удаление <math>h_j</math> из списка предпочтений rl и наоборот.




Источник — http://pco.iis.nsk.su/wega/index.php/Задача_о_больницах_и_резидентах