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

Пара (ri, hj) 2 AnM блокирует паросочетание M (или является блокирующей парой для M), если относительно M выполняются следующие условия:

1. резидент <math>r_i</math> не назначен или предпочитает M(ri) больницу <math>h_j</math>;

2. больница недоукомплектована или предпочитает резидента <math>r_i</math> хотя бы одному члену M(hj) (или обоим).

Паросочетание M называется устойчивым, если оно не допускает ни одной блокирующей пары. Пусть дан экземпляр <math>I</math> из HR; задача заключается в том, чтобы найти устойчивое паросочетание в I.

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