4551
правка
Задача о больницах и резидентах: различия между версиями
Перейти к навигации
Перейти к поиску
м
Задача о больницах и резидентах (посмотреть исходный код)
Версия от 21:28, 8 декабря 2023
, 8 декабря 2023нет описания правки
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Задача о поступлении в колледж; задача о поступлении в университет; задача об устойчивых поступлениях; задача об устойчивых назначениях; задача об устойчивых b-паросочетаниях == Постановка задачи == Экземпляр I задачи о боль...») |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Экземпляр I задачи о больницах и резидентах (HR) [5,6,14] включает множество R = | Экземпляр I задачи о больницах и резидентах (HR) [5, 6, 14] включает множество <math>R = \{ r_1, ..., r_n \}</math> ''резидентов' и множество <math>H = \{ h_1, ..., h_m \} </math> ''больниц''. Каждая больница hj 2 H имеет кадровый потенциал в виде целого положительного числа, обозначаемый cj. Также каждый резидент ri 2 R имеет список предпочтений, в котором он ранжирует подмножество H в строгом порядке. Пара (ri, hj) 2 R x H считается приемлемой, если hj содержится в списке предпочтений ri; в этом случае говорят, что ri считает hj приемлемым. Аналогично, каждая больница hj 2 H имеет список предпочтений, в котором она располагает в строгом порядке тех резидентов, которые считают эту больницу приемлемой. Пусть имеются три любых агента x, y, z 2 R[H; можно сказать, что x предпочитает агента y агенту z, если x находит приемлемым их обоих и y предшествует z в списке предпочтений x. Пусть C ='' | ||
| Строка 19: | Строка 19: | ||
Паросочетание M называется устойчивым, если оно не допускает ни одной блокирующей пары. Пусть дан экземпляр I из HR; задача заключается в том, чтобы найти устойчивое паросочетание в I. | Паросочетание M называется устойчивым, если оно не допускает ни одной блокирующей пары. Пусть дан экземпляр I из HR; задача заключается в том, чтобы найти устойчивое паросочетание в I. | ||
== Основные результаты == | ==Основные результаты== | ||
Впервые задача HR была определена Гэйлом и Шепли [ ] под названием «задача о поступлении в колледж». В своей основополагающей статье авторы рассматривают классическую задачу о стабильных браках (SM; см. Стабильный брак и Оптимальный стабильный брак), которая является частным случаем HR, в котором n = m, A = R x H, и cj = 1 для всех hj 2 H; в этом частном случае резиденты и больницы называются мужчинами и женщинами, соответственно. Гэйл и Шепли показали, что каждый экземпляр I задачи HR допускает по крайней мере одно устойчивое паросочетание. Доказательство этого результата носит конструктивный характер, то есть описывается алгоритм нахождения устойчивого паросочетания в I. Этот алгоритм получил название алгоритма Гэйла-Шепли. | Впервые задача HR была определена Гэйлом и Шепли [ ] под названием «задача о поступлении в колледж». В своей основополагающей статье авторы рассматривают классическую задачу о стабильных браках (SM; см. Стабильный брак и Оптимальный стабильный брак), которая является частным случаем HR, в котором n = m, A = R x H, и cj = 1 для всех hj 2 H; в этом частном случае резиденты и больницы называются мужчинами и женщинами, соответственно. Гэйл и Шепли показали, что каждый экземпляр I задачи HR допускает по крайней мере одно устойчивое паросочетание. Доказательство этого результата носит конструктивный характер, то есть описывается алгоритм нахождения устойчивого паросочетания в I. Этот алгоритм получил название алгоритма Гэйла-Шепли. | ||
| Строка 52: | Строка 52: | ||
== Применение == | ==Применение== | ||
Практические приложения задачи HR широко распространены. В первую очередь они возникают в контексте централизованных автоматизированных схем подбора кандидатов на должности (например, студентов-медиков в больницы, выпускников школ в университеты, учеников начальных школ в средние школы). Возможно, самым известным примером такой схемы является Национальная программа подбора резидентов (National Resident Matching Program, NRMP) в США [16], которая ежегодно распределяет около 31 000 студентов-медиков (называемых резидентами) на их первые должности в больницах, учитывая предпочтения резидентов по отношению к больницам и наоборот, а также кадровый потенциал больниц. Аналоги программы NRMP существуют и в других странах, включая Канаду [17], Шотландию [ ] и Японию [ ]. Эти схемы подбора в основном используют расширения алгоритма RGS для задачи HR. | Практические приложения задачи HR широко распространены. В первую очередь они возникают в контексте централизованных автоматизированных схем подбора кандидатов на должности (например, студентов-медиков в больницы, выпускников школ в университеты, учеников начальных школ в средние школы). Возможно, самым известным примером такой схемы является Национальная программа подбора резидентов (National Resident Matching Program, NRMP) в США [16], которая ежегодно распределяет около 31 000 студентов-медиков (называемых резидентами) на их первые должности в больницах, учитывая предпочтения резидентов по отношению к больницам и наоборот, а также кадровый потенциал больниц. Аналоги программы NRMP существуют и в других странах, включая Канаду [17], Шотландию [ ] и Японию [ ]. Эти схемы подбора в основном используют расширения алгоритма RGS для задачи HR. | ||
| Строка 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]. | ||
| Строка 71: | Строка 71: | ||
Дальнейшее обобщение задачи HR возникает в случае, когда каждая больница может быть разделена на несколько отделений, каждое из которых имеет свой кадровый потенциал, а резиденты ранжируют отдельные отделения в порядке предпочтения. Этот вариант моделируется задачей распределения студентов по проектам [ ]. Наконец, задача об устойчивых объектах [ ] является недвухсторонним расширением HR, в котором существует единственный набор агентов, каждый из которых имеет собственную емкость (кадровый потенциал) и ранжирует подмножество других в порядке предпочтения. | Дальнейшее обобщение задачи HR возникает в случае, когда каждая больница может быть разделена на несколько отделений, каждое из которых имеет свой кадровый потенциал, а резиденты ранжируют отдельные отделения в порядке предпочтения. Этот вариант моделируется задачей распределения студентов по проектам [ ]. Наконец, задача об устойчивых объектах [ ] является недвухсторонним расширением HR, в котором существует единственный набор агентов, каждый из которых имеет собственную емкость (кадровый потенциал) и ранжирует подмножество других в порядке предпочтения. | ||
== Открытые вопросы == | ==Открытые вопросы== | ||
Было сформулировано несколько приближенных алгоритмов поиска слабоустойчивого паросочетания максимальной мощности для экземпляра 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. | ||
== См. также == | ==См. также== | ||
* [[Оптимальное устойчивое бракосочетание]] | *[[Оптимальное устойчивое бракосочетание]] | ||
* [[Ранжированное паросочетание]] | *[[Ранжированное паросочетание]] | ||
* [[Устойчивое бракосочетание]] | *[[Устойчивое бракосочетание]] | ||
* [[Устойчивое бракосочетание и дискретный выпуклый анализ]] | *[[Устойчивое бракосочетание и дискретный выпуклый анализ]] | ||
* [[Устойчивое бракосочетание со связями и неполными списками]] | *[[Устойчивое бракосочетание со связями и неполными списками]] | ||
* [[Задача об устойчивом разбиении]] | *[[Задача об устойчивом разбиении]] | ||
== Литература == | ==Литература== | ||
1. Abdulkadiroglu, A., Pathak, P.A., Roth, A.E.: The New York City high school match. Am. Economic. Rev. 95(2), 364-367 (2006) | 1. Abdulkadiroglu, A., Pathak, P.A., Roth, A.E.: The New York City high school match. Am. Economic. Rev. 95(2), 364-367 (2006) | ||