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

Перейти к навигации Перейти к поиску
Строка 22: Строка 22:


==Основные результаты==
==Основные результаты==
Впервые задача 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. Этот алгоритм получил название ''алгоритма Гэйла-Шепли''.
Впервые задача 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 := \empty</math>
   <math>M := \empty</math>
Строка 47: Строка 47:




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




Строка 54: Строка 54:




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




Источник — http://pco.iis.nsk.su/wega/index.php/Задача_о_больницах_и_резидентах