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

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

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

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

 

'''• во всех устойчивых паросочетаниях назначаются одни и те же резиденты;'''

 

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

 

'''• любой больнице, оставшейся недоукомплектованной в одном устойчивом паросочетании, назначается одно и то же количество резидентов во всех устойчивых паросочетаниях.'''