4551
правка
Задача о больницах и резидентах: различия между версиями
Материал из WEGA
Задача о больницах и резидентах (посмотреть исходный код)
Версия от 21:35, 8 декабря 2023
, 8 декабря 2023нет описания правки
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) Нет описания правки Метка: визуальный редактор отключён |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Экземпляр I задачи о больницах и резидентах (HR) [5, 6, 14] включает множество <math>R = \{ r_1, ..., r_n \}</math> ''резидентов' и множество <math>H = \{ h_1, ..., h_m \} </math> ''больниц''. Каждая больница | Экземпляр I задачи о больницах и резидентах (HR) [5, 6, 14] включает множество <math>R = \{ r_1, ..., r_n \}</math> ''резидентов'' и множество <math>H = \{ h_1, ..., h_m \} </math> ''больниц''. Каждая больница <math>h_j \in H<nowiki></math></nowiki> имеет ''кадровый потенциал'' в виде целого положительного числа, обозначаемый <math>c_j</math>. Также каждый резидент <math>r_i \in R</math> имеет ''список предпочтений'', в котором он ранжирует подмножество H в строгом порядке. Пара <math>(r_i, h_j) \in R \times H</math> называется ''приемлемой'', если <math>h_j</math> содержится в списке предпочтений ri; в этом случае говорят, что ri считает <math>h_j</math> приемлемой. Аналогично, каждая больница hj 2 H имеет список предпочтений, в котором она располагает в строгом порядке тех резидентов, которые считают эту больницу приемлемой. Пусть имеются три любых агента x, y, z 2 R[H; можно сказать, что x предпочитает агента y агенту z, если x находит приемлемым их обоих и y предшествует z в списке предпочтений x. Пусть C = | ||
Обозначим за A множество допустимых пар в I, L = jAj. Назначение M является подмножеством A. Если (ri ;hj) 2 M, то считается, что резидент ri назначен | Обозначим за A множество допустимых пар в I, L = jAj. Назначение M является подмножеством A. Если (ri ;hj) 2 M, то считается, что резидент ri назначен больнице <math>h_j</math>, а больница <math>h_j</math> – резиденту ri. Для каждого q 2 R [ H множество назначенных q в M обозначается M(q). Если ri 2 R и M(ri) = ;, то считается, что ri не назначен, в противном случае ri назначен. Аналогично, любая больница hj 2 H является недоукомплектованной, полной или переукомплектованной, если jM(hj)j меньше, равна или больше cj, соответственно. | ||
| Строка 13: | Строка 13: | ||
Пара (ri, hj) 2 AnM блокирует паросочетание M (или является блокирующей парой для M), если относительно M выполняются следующие условия: | Пара (ri, hj) 2 AnM блокирует паросочетание M (или является блокирующей парой для M), если относительно M выполняются следующие условия: | ||
1. резидент ri не назначен или предпочитает M(ri) больницу | 1. резидент ri не назначен или предпочитает M(ri) больницу <math>h_j</math>; | ||
2. больница недоукомплектована или предпочитает резидента ri хотя бы одному члену M(hj) (или обоим). | 2. больница недоукомплектована или предпочитает резидента ri хотя бы одному члену M(hj) (или обоим). | ||
| Строка 23: | Строка 23: | ||
M := | M := | ||
while (некоторый резидент ri не назначен и ri имеет непустой список) { | while (некоторый резидент ri не назначен и ri имеет непустой список) { <math>h_j</math> := первая больница в списке ri; /* ri применяется к hj */ M:=M[f(ri;hj)g; if(hj is переукомплектована) { | ||
rk := худший резидент в M(hj) согласно списку | rk := худший резидент в M(hj) согласно списку <math>h_j</math>; M:=Mnf(rk;hj)g; } if (hj полна) { | ||
rk := худший резидент в M(hj) согласно списку | rk := худший резидент в M(hj) согласно списку <math>h_j</math>; для (каждого преемника rl из rk в списке <math>h_j</math>) удалить пару (rl ; hj) | ||
Рисунок 1. Алгоритм Гэйла-Шепли для задачи HR | Рисунок 1. Алгоритм Гэйла-Шепли для задачи HR | ||
Расширенная версия алгоритма Гэйла/Шепли для задачи HR показана на рис. 1. Алгоритм включает в себя последовательность операций apply (подать заявку) и delete (удалить). На каждой итерации цикла while некоторый не назначенный резидент ri с непустым списком предпочтений подает заявку в первую больницу | Расширенная версия алгоритма Гэйла/Шепли для задачи HR показана на рис. 1. Алгоритм включает в себя последовательность операций apply (подать заявку) и delete (удалить). На каждой итерации цикла while некоторый не назначенный резидент ri с непустым списком предпочтений подает заявку в первую больницу <math>h_j</math> в его списке и становится временно назначенным в <math>h_j</math> (впоследствии это назначение может быть отменено). Если в результате этого назначения больница <math>h_j</math> становится переукомплектованной, то она отказывается от худшего из назначенных резидентов rk. Далее, если больница <math>h_j</math> полна (независимо от того, была ли она переукомплектована ранее на той же итерации цикла), то для каждого резидента rl, которого <math>h_j</math> считает менее желательным, чем его худший резидент rk, алгоритм удаляет пару (rl,hj), что включает удаление <math>h_j</math> из списка предпочтений rl и наоборот. | ||
| Строка 59: | Строка 59: | ||
==Расширения задачи HR== | ==Расширения задачи HR == | ||
Одно из ключевых расширений HR, имеющее большое практическое значение, возникает в том случае, когда экземпляр задачи может включать в себя набор пар, каждая из которых представляет совместный список предпочтений по парам больниц (например, для того, чтобы члены данной пары могли быть расположены географически близко друг к другу). Расширение HR, в котором могут участвовать пары, обозначается HRC; определение стабильности в HRC является естественным расширением определения стабильности в HR (формальное определение HRC см. в [6, раздел 1.6.6]). Известно, что экземпляр задачи HRC не обязательно может выдавать устойчивое паросочетание (см. [6, раздел 1.6.6] и [14, раздел 5.4.3]). Более того, проблема решения вопроса о том, допускает ли экземпляр HRC устойчивое паросочетание, является NP-полной [13]. | Одно из ключевых расширений HR, имеющее большое практическое значение, возникает в том случае, когда экземпляр задачи может включать в себя набор пар, каждая из которых представляет совместный список предпочтений по парам больниц (например, для того, чтобы члены данной пары могли быть расположены географически близко друг к другу). Расширение HR, в котором могут участвовать пары, обозначается HRC; определение стабильности в HRC является естественным расширением определения стабильности в HR (формальное определение HRC см. в [6, раздел 1.6.6]). Известно, что экземпляр задачи HRC не обязательно может выдавать устойчивое паросочетание (см. [6, раздел 1.6.6] и [14, раздел 5.4.3]). Более того, проблема решения вопроса о том, допускает ли экземпляр HRC устойчивое паросочетание, является NP-полной [13]. | ||
| Строка 74: | Строка 74: | ||
Было сформулировано несколько приближенных алгоритмов поиска слабоустойчивого паросочетания максимальной мощности для экземпляра HRT, в котором каждая больница имеет кадровый потенциал 1 (подробнее об этом см. Устойчивое бракосочетание со связями и неполными списками). Остается открытым вопрос о расширении этих алгоритмов или о формулировании эффективных эвристик для случая HRT с произвольными значениями кадрового потенциала. Эта задача особенно актуальна с практической точки зрения, поскольку, как уже отмечалось в разделе «Применение», больницы могут захотеть включить связи в свои списки предпочтений. В этом случае слабая устойчивость является наиболее часто используемым критерием устойчивости, поскольку гарантируется существование такого паросочетания. Попытка обеспечить совпадение для как можно большего числа резидентов мотивирует на поиск больших слабоустойчивых паросочетаний. | Было сформулировано несколько приближенных алгоритмов поиска слабоустойчивого паросочетания максимальной мощности для экземпляра HRT, в котором каждая больница имеет кадровый потенциал 1 (подробнее об этом см. Устойчивое бракосочетание со связями и неполными списками). Остается открытым вопрос о расширении этих алгоритмов или о формулировании эффективных эвристик для случая HRT с произвольными значениями кадрового потенциала. Эта задача особенно актуальна с практической точки зрения, поскольку, как уже отмечалось в разделе «Применение», больницы могут захотеть включить связи в свои списки предпочтений. В этом случае слабая устойчивость является наиболее часто используемым критерием устойчивости, поскольку гарантируется существование такого паросочетания. Попытка обеспечить совпадение для как можно большего числа резидентов мотивирует на поиск больших слабоустойчивых паросочетаний. | ||
==Ссылка на код == | ==Ссылка на код== | ||
Реализации алгоритмов RGS и HGS для задачи HR на языке Ada можно найти по следующему адресу: http://www.dcs.gla.ac.uk/research/algorithms/stable. | Реализации алгоритмов RGS и HGS для задачи HR на языке Ada можно найти по следующему адресу: http://www.dcs.gla.ac.uk/research/algorithms/stable. | ||
