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

Экземпляр <math>I</math> задачи о больницах и резидентах (HR) [5, 6, 14] включает множество <math>R = \{ r_1, ..., r_n \}</math> ''резидентов'' и множество <math>H = \{ h_1, ..., h_m \} </math> ''больниц''. Каждая больница <math>h_j \in H</math> имеет ''кадровый потенциал'' в виде целого положительного числа, обозначаемый <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> содержится в списке предпочтений <math>r_i</math>; в этом случае говорят, что <math>r_i</math> считает <math>h_j</math> приемлемой. Аналогично, каждая больница <math>h_j \in H</math> имеет список предпочтений, в котором она располагает в строгом порядке тех резидентов, которые считают эту больницу приемлемой. Пусть имеются три любых агента <math>x, y, z \in R \cup H</math>; можно сказать, что x ''предпочитает'' агента y агенту z, если x находит приемлемым их обоих и y предшествует z в списке предпочтений x. Пусть <math>C = \sum_{h_j \in H} c_j</math>.