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

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

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

'''Теорема 2. Для заданного экземпляра задачи HR'''