Упражнение с решением 2

Можно рассмотреть обобщение задачи устойчивых паросочетаний, в котором какие-то пары «мужчина-женщина» явно запрещены. В случае с нанимателями и кандидатами можно представить, что у некоторых кандидатов отсутствуют не- обходимые сертификаты и их не примут на работу в некоторые компании, как бы перспективно они ни выглядели.
В аналогии с браком имеется множество M из n мужчин, множество W из n женщин и множество F ίΞ M χ W пар, брак между которыми попросту запрещен. Каждый мужчина m определяет оценки для всех женщин w, для которых (m, w) ⅜ F, и каждая женщина w' определяет оценки для всех мужчин m', для которых (m', w') ⅜ F.

В этой более общей постановке задачи паросочетание S называется устойчивым, если в нем не проявляются никакие из следующих признаков неустойчивости:

1. В S присутствуют две пары (m, w) и (m', w'), у которых (m, w') ⅜ F, m предпо- читает w' женщине w, а w' предпочитает m мужчине m' (обычная разновидность нестабильности).

2. Существует пара (m, w) Sи мужчина m', такие что m’ не входит ни в одну пару в сочетании, (m', w) ⅜ F и w предпочитает m' мужчине m. (Одинокий мужчина, более предпочтительный и не запрещенный.)

3. Существует пара (m, w) Sи женщина w', такие что w'не входит ни в одну пару в сочетании, (m, w') ⅜ F и m предпочитает w' женщине w. (Одинокая женщина, более предпочтительная и не запрещенная.)

4. Существует мужчина m и женщина w, ни один из которых не входит ни в одну пару в паросочетании, так что (m, w) ⅜ F. (Существуют два одиноких человека, которым ничто не мешает вступить в брак друг с другом.)

Обратите внимание: по этим более общим определениям устойчивое паросоче- тание не обязано быть идеальным.

Теперь можно задать вопрос: всегда ли существует устойчивое паросочетание для каждого множества списков предпочтений и каждого множества запрещен- ных пар? Чтобы ответить на этот вопрос, можно пойти по одному из двух путей: 1) предоставить алгоритм, который для любого множества списков предпочтений и запрещенных пар будет создавать устойчивое паросочетание, или 2) привести пример множества списков предпочтений и запрещенных пар, для которых не существует устойчивого паросочетания.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Упражнение с решением 2:

  1. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  2. РЕШЕНИЕ
  3. РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
  4. ПРИНЯТИЕ РЕШЕНИЙ
  5. РЕШЕНИЯ КСУ
  6. Не избегайте принятия решений
  7. ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
  8. ЗАДАЧА: РЕШЕНИЕ
  9. Принять решение
  10. Управленческие решения
  11. Решение проблем
  12. КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.
  13. Убеждения и решения
  14. Убеждения и решения
  15. НАЙДИТЕ РЕШЕНИЕ
  16. НАЧНИТЕ С ПРИНЯТИЯ РЕШЕНИЯ