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

Впервые задача 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].

       <math>M := M \sub \{ (r_k, h_j) \} </math>;  

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

Поскольку вышеописанный алгоритм предполагает подачу резидентами заявок в больницы, он стал известен как ''алгоритм Гэйла-Шепли, ориентированный на резидентов'', или алгоритм 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) строит уникальное устойчивое паросочетание, в котором каждый назначенный резидент получает лучшую больницу, которую он мог бы получить в любом устойчивом паросочетании, в то время как каждый не назначенный резидент не назначен в каждом устойчивом паросочетании.'''