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

Перейти к навигации Перейти к поиску
Строка 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> не назначен и <math>r_i</math> имеет непустой список) { <math>h_j</math> := первая больница в списке <math>r_i</math>; /* <math>r_i</math> подает заявку в hj */ M:=M[f(ri;hj)g; if(hj is переукомплектована) {
  '''while''' (некоторый резидент <math>r_i</math> не назначен '''and''' <math>r_i</math> имеет непустой список) {  
rk := худший резидент в M(hj) согласно списку <math>h_j</math>; M:=Mnf(rk;hj)g; } if (hj полна) {
    <math>h_j</math> := первая больница в списке <math>r_i</math>;  
rk := худший резидент в M(hj) согласно списку <math>h_j</math>; для (каждого преемника rl из rk в списке <math>h_j</math>) удалить пару (rl ; hj)
    /* <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
Источник — http://pco.iis.nsk.su/wega/index.php/Задача_о_больницах_и_резидентах