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

Обозначим за A множество приемлемых пар в <math>I</math>, L = |A|. ''Назначение'' 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>. Для каждого <math>q \in R \cup H</math> множество назначенных q в M обозначается M(q). Если <math>r_i \in R</math> и <math>M(r_i) = \empty</math>, то считается, что <math>r_i</math> ''не назначен'', в противном случае <math>r_i</math> назначен. Аналогично, любая больница <math>h_j \in H</math> является ''недоукомплектованной'', ''полной'' или ''переукомплектованной'', если <math>|M(h_j)|</math> меньше, равна или больше <math>c_j</math>, соответственно.

''Паросочетанием'' M называется назначение, такое, что <math>|M(r_i)| \le 1</math> для каждого <math>r_i \in R</math> и <math>|M(h_j)| \le c_j</math> для каждого <math>h_j \in H</math> (т. е. ни один резидент не назначен в неприемлемую больницу, каждый резидент назначен не более чем в одну больницу и ни одна больница не переукомплектована). Для удобства обозначений, если даны паросочетание M и резидент <math>r_i \in R</math> такой, что <math>M(r_i) \ne \empty</math>, то в случаях, когда это не вызывает двусмысленности, обозначение <math>M(r_i)</math> также используется для обозначения единственного члена <math>M(r_i)</math>.

Впервые задача HR была определена Гэйлом и Шепли [5] под названием «Задача о поступлении в колледж». В своей основополагающей статье авторы рассматривают классическую задачу о стабильных браках (SM; см. [[Стабильный брак]] и [[Оптимальный стабильный брак]]), представляющую собой частный случай HR, в котором <math>n = m, A = R \times H</math> и <math>c_j = 1</math> для всех <math>h_j \in H</math>; в этом частном случае вместо резидентов и больниц мы имеем дело с мужчинами и женщинами, соответственно. Гэйл и Шепли показали, что каждый экземпляр <math>I</math> задачи HR допускает по крайней мере одно устойчивое паросочетание. Доказательство этого результата носит конструктивный характер, то есть описывается алгоритм нахождения устойчивого паросочетания в I. Этот алгоритм получил название ''алгоритма Гэйла-Шепли'' [https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%93%D1%8D%D0%B9%D0%BB%D0%B0_%E2%80%94_%D0%A8%D0%B5%D0%BF%D0%BB%D0%B8].

Эти результаты известны под общим названием «Теорема о сельских больницах» (подробнее см. в [6, раздел 1.6.4]. Кроме того, множество устойчивых паросочетаний в <math>I</math> образует дистрибутивную решетку при естественном отношении доминирования [6, раздел 1.6.5].

Практические приложения задачи HR широко распространены. В первую очередь они возникают в контексте централизованных автоматизированных схем подбора кандидатов на должности (например, студентов-медиков в больницы, выпускников школ в университеты, учеников начальных школ в средние школы). Возможно, самым известным примером такой схемы является Национальная программа подбора резидентов (National Resident Matching Program, NRMP) в США [16], которая ежегодно распределяет около 31 000 студентов-медиков (называемых резидентами) на их первые должности в больницах, учитывая предпочтения резидентов по отношению к больницам и наоборот, а также кадровый потенциал больниц. Аналоги программы NRMP существуют и в других странах, включая Канаду [17], Шотландию [18] и Японию [19]. Эти схемы подбора в основном используют расширения алгоритма 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]). Известно, что слабоустойчивые паросочетания в экземпляре <math>I</math> задачи HRT могут иметь различные размеры, и проблема нахождения слабоустойчивого паросочетания максимальной мощности является NP-полной (подробнее об этом см. Устойчивое бракосочетание со связями и неполными списками). С другой стороны, в отличие от случая слабой устойчивости, сверхустойчивое паросочетание не обязательно должно существовать в I, хотя существует алгоритм с временем выполнения O(L) для поиска такого паросочетания в случае, если таковое существует. Аналогичные результаты имеют место и в случае сильной устойчивости – в этом случае алгоритм с временем выполнения <math>O(L^2)</math> [8] был улучшен алгоритмом с временем выполнения O(CL) [10] и распространен на случай «от многих к многим» [11]. Кроме того, аналоги теоремы о сельских больницах справедливы для HRT при каждом из критериев сверхустойчивости и сильной устойчивости [7, 15].

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

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

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

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

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