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

Впервые задача 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 допускает по крайней мере одно устойчивое паросочетание. Доказательство этого результата носит конструктивный характер, то есть описывается алгоритм нахождения устойчивого паросочетания в <math>I</math>. Этот алгоритм получил название ''алгоритма Гэйла-Шепли'' [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].

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

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