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

Впервые задача HR была определена Гэйлом и Шепли [5] под названием «Задача о поступлении в колледж». В своей основополагающей статье авторы рассматривают классическую задачу о стабильных браках (SM; см. Стабильный брак и Оптимальный стабильный брак), которая является частным случаем HR, в котором n = m, A = R x H, и cj = 1 для всех hj 2 H; в этом частном случае резиденты и больницы называются мужчинами и женщинами, соответственно. Гэйл и Шепли показали, что каждый экземпляр <math>I</math> задачи HR допускает по крайней мере одно устойчивое паросочетание. Доказательство этого результата носит конструктивный характер, то есть описывается алгоритм нахождения устойчивого паросочетания в I. Этот алгоритм получил название алгоритма Гэйла-Шепли.