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

Экземпляр 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 =

Обозначим за 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, соответственно.

Паросочетанием 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).

1. резидент ri не назначен или предпочитает M(ri) больницу <math>h_j</math>;

2. больница недоукомплектована или предпочитает резидента ri хотя бы одному члену M(hj) (или обоим).

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

Расширенная версия алгоритма Гэйла/Шепли для задачи 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 и наоборот.