4551
правка
Задача о больницах и резидентах: различия между версиями
Перейти к навигации
Перейти к поиску
Задача о больницах и резидентах (посмотреть исходный код)
Версия от 18:05, 9 декабря 2023
, 9 декабря 2023→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 24: | Строка 24: | ||
Впервые задача 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. Этот алгоритм получил название ''алгоритма Гэйла-Шепли''. | ||
M := | <math>M := \empty</math> | ||
while (некоторый резидент <math>r_i</math> не назначен | '''while''' (некоторый резидент <math>r_i</math> не назначен '''and''' <math>r_i</math> имеет непустой список) { | ||
<math>h_j</math> := первая больница в списке <math>r_i</math>; | |||
/* <math>r_i</math> подает заявку в hj */ | |||
<math>M := M \cup \{ (r_i, h_j) \}</math>; | |||
'''if''' (<math>h_j</math> переукомплектована) { | |||
<math>r_k</math> := худший резидент в <math>M(h_j)</math> согласно списку <math>h_j</math>; | |||
<math>M := M \sub \{ (r_k, h_j) \} </math>; | |||
} | |||
'''if''' (<math>h_j</math> полна) { | |||
<math>r_k</math> := худший резидент в <math>M(h_j)</math> согласно списку <math>h_j</math>; | |||
'''for''' (каждого преемника <math>r_l</math> резидента <math>r_k</math> в списке <math>h_j</math>) | |||
удалить пару <math>(r_l, h_j)</math> | |||
Рисунок 1. Алгоритм Гэйла-Шепли для задачи HR | Рисунок 1. Алгоритм Гэйла-Шепли для задачи HR | ||