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

Экземпляр 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. Если <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 называется назначение, такое, что <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 выполняются следующие условия:

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

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

Паросочетание M называется устойчивым, если оно не допускает ни одной блокирующей пары. Пусть дан экземпляр I из HR; задача заключается в том, чтобы найти устойчивое паросочетание в I.

Впервые задача HR была определена Гэйлом и Шепли [ ] под названием «задача о поступлении в колледж». В своей основополагающей статье авторы рассматривают классическую задачу о стабильных браках (SM; см. Стабильный брак и Оптимальный стабильный брак), которая является частным случаем HR, в котором n = m, A = R x H, и cj = 1 для всех hj 2 H; в этом частном случае резиденты и больницы называются мужчинами и женщинами, соответственно. Гэйл и Шепли показали, что каждый экземпляр I задачи HR допускает по крайней мере одно устойчивое паросочетание. Доказательство этого результата носит конструктивный характер, то есть описывается алгоритм нахождения устойчивого паросочетания в I. Этот алгоритм получил название алгоритма Гэйла-Шепли.

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

Поскольку вышеописанный алгоритм предполагает подачу резидентами заявок в больницы, он стал известен как алгоритм Гэйла-Шепли, ориентированный на резидентов, или алгоритм RGS [6, раздел 1.6.3]. Алгоритм RGS завершается нахождением устойчивого паросочетания для заданного экземпляра задачи HR [5, 6, теорема 1.6.2]. При подходящем выборе структур данных (расширяя те, что были описаны в работе [6, раздел алгоритм RGS может быть реализован за время O(L). Он позволяет получить устойчивое паросочетание, которое одновременно является наилучшим для всех резидентов [5,6, теорема 1.6.2]. Эти наблюдения можно обобщить следующим образом.

Теорема 1. Для заданного экземпляра задачи HR алгоритм RGS за время O(L) строит уникальное устойчивое паросочетание, в котором каждый назначенный резидент получает лучшую больницу, которую он мог бы получить в любом устойчивом паросочетании, в то время как каждый не назначенный резидент не назначен в каждом устойчивом паросочетании.

Аналог алгоритма RGS, носящий название ориентированного на больницы алгоритма Гэйла-Шепли, или сокращенно HGS-алгоритм [6, раздел 1.6.2], позволяет получить единственное устойчивое паросочетание, которое аналогичным образом удовлетворяет свойству оптимальности для больниц [6, теорема 1.6.1].

Хотя для заданного экземпляра I задачи HR может существовать несколько устойчивых паросочетаний, для всех устойчивых паросочетаний в I сохраняются некоторые ключевые структурные свойства, касающиеся неназначенных резидентов и недоукомплектованных больниц.

• во всех устойчивых паросочетаниях каждой больнице назначается одно и то же количество резидентов;

Практические приложения задачи HR широко распространены. В первую очередь они возникают в контексте централизованных автоматизированных схем подбора кандидатов на должности (например, студентов-медиков в больницы, выпускников школ в университеты, учеников начальных школ в средние школы). Возможно, самым известным примером такой схемы является Национальная программа подбора резидентов (National Resident Matching Program, NRMP) в США [16], которая ежегодно распределяет около 31 000 студентов-медиков (называемых резидентами) на их первые должности в больницах, учитывая предпочтения резидентов по отношению к больницам и наоборот, а также кадровый потенциал больниц. Аналоги программы NRMP существуют и в других странах, включая Канаду [17], Шотландию [ ] и Японию [ ]. Эти схемы подбора в основном используют расширения алгоритма RGS для задачи HR.

 

Одно из ключевых расширений HR, имеющее большое практическое значение, возникает в том случае, когда экземпляр задачи может включать в себя набор пар, каждая из которых представляет совместный список предпочтений по парам больниц (например, для того, чтобы члены данной пары могли быть расположены географически близко друг к другу). Расширение HR, в котором могут участвовать пары, обозначается HRC; определение стабильности в HRC является естественным расширением определения стабильности в HR (формальное определение HRC см. в [6, раздел 1.6.6]). Известно, что экземпляр задачи HRC не обязательно может выдавать устойчивое паросочетание (см. [6, раздел 1.6.6] и [14, раздел 5.4.3]). Более того, проблема решения вопроса о том, допускает ли экземпляр HRC устойчивое паросочетание, является NP-полной [13].

HR можно рассматривать как обобщение задачи SM вида «от многих к одному». Дальнейшим обобщением SM является задача нахождения устойчивого паросочетания в модели «от многих к многим», в которой резиденты и больницы могут получать множественные назначения с учетом ограничений на кадровый потенциал. В этом случае резиденты и больницы чаще всего называются работниками и фирмами соответственно. Существуют две основные вариации задачи нахождения устойчивого паросочетания «от многих к многим», в которых либо (1) работники ранжируют приемлемые фирмы в порядке предпочтения и наоборот, либо (2) работники ранжируют приемлемые подмножества фирм в порядке предпочтения и наоборот. Предыдущие работы, относящиеся к обеим моделям, рассмотрены в [4].

Другие варианты задачи HR возникают в случаях, если списки предпочтений включают связи. Это расширение также очень важно с практической точки зрения, поскольку может быть нереалистично ожидать, что популярная больница расположит большое количество претендентов в строгом порядке, особенно если она не учитывает группы претендентов. Расширение задачи HR, в котором списки предпочтений могут включать связи, обозначается HRT. В этом контексте возникают три естественных определения устойчивости, так называемые слабая устойчивость, сильная устойчивость и сверхустойчивость (формальные определения этих понятий см. в [8]). Известно, что слабоустойчивые паросочетания в экземпляре I задачи HRT могут иметь различные размеры, и проблема нахождения слабоустойчивого паросочетания максимальной мощности является NP-полной (подробнее об этом см. Устойчивое бракосочетание со связями и неполными списками). С другой стороны, в отличие от случая слабой устойчивости, сверхустойчивое паросочетание не обязательно должно существовать в I, хотя существует алгоритм O(L) для поиска такого паросочетания в случае, если таковое существует. Аналогичные результаты имеют место и в случае сильной устойчивости – в этом случае алгоритм O(L2) [8] был улучшен алгоритмом O(CL) [ ] и распространен на случай «от многих к многим» [ ]. Кроме того, аналоги теоремы о сельских больницах справедливы для HRT при каждом из критериев сверхустойчивости и сильной устойчивости [7, 15].

Дальнейшее обобщение задачи HR возникает в случае, когда каждая больница может быть разделена на несколько отделений, каждое из которых имеет свой кадровый потенциал, а резиденты ранжируют отдельные отделения в порядке предпочтения. Этот вариант моделируется задачей распределения студентов по проектам [ ]. Наконец, задача об устойчивых объектах [ ] является недвухсторонним расширением HR, в котором существует единственный набор агентов, каждый из которых имеет собственную емкость (кадровый потенциал) и ранжирует подмножество других в порядке предпочтения.

Было сформулировано несколько приближенных алгоритмов поиска слабоустойчивого паросочетания максимальной мощности для экземпляра HRT, в котором каждая больница имеет кадровый потенциал 1 (подробнее об этом см. Устойчивое бракосочетание со связями и неполными списками). Остается открытым вопрос о расширении этих алгоритмов или о формулировании эффективных эвристик для случая HRT с произвольными значениями кадрового потенциала. Эта задача особенно актуальна с практической точки зрения, поскольку, как уже отмечалось в разделе «Применение», больницы могут захотеть включить связи в свои списки предпочтений. В этом случае слабая устойчивость является наиболее часто используемым критерием устойчивости, поскольку гарантируется существование такого паросочетания. Попытка обеспечить совпадение для как можно большего числа резидентов мотивирует на поиск больших слабоустойчивых паросочетаний.

*[[Оптимальное устойчивое бракосочетание]]

*[[Устойчивое бракосочетание]]

*[[Устойчивое бракосочетание и дискретный выпуклый анализ]]

*[[Устойчивое бракосочетание со связями и неполными списками]]