Примеры

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

Для начала допустим, что имеется множество из двух мужчин {m, m'} и множе- ство из двух женщин {w, w' }.

Списки предпочтений выглядят так:

♦ m предпочитает w женщине w';

♦ m' предпочитает w женщине w';

♦ w предпочитает m мужчине m';

♦ w' предпочитает m мужчине m'.

Если рассматривать этот набор списков предпочтений на интуитивном уров- не, он представляет ситуацию полного согласия: мужчины сходятся во мнениях относительно порядка женщин, а женщины — относительно порядка мужчин. В такой ситуации существует уникальное устойчивое паросочетание, состоящее из пар (m, w) и (m', w'). Другое идеальное паросочетание, состоящее из пар (m', w) и (m, w'), не является устойчивым, потому что пара (m, w) образует неустойчивость по отношению к этому паросочетанию. (Как m, так и w предпочли бы бросить своих партнеров и образовать новую пару.)

В следующем примере ситуация немного усложняется. Предположим, действу- ют следующие предпочтения:

♦ m предпочитает w женщине w';

♦ m' предпочитает w'женщине w;

♦ w предпочитает m'мужчине m;

♦ w' предпочитает m мужчине m'.

Что же происходит на этот раз? Предпочтения двух мужчин противоположны (они ставят на первое место разных женщин); то же самое можно сказать и о пред- почтениях двух женщин. Однако предпочтения мужчин полностью противоречат предпочтениям женщин.

Во втором примере существуют два разных устойчивых паросочетания. Со- четание, состоящее из пар (m, w) и (m', w'), является устойчивым — оба мужчины довольны, насколько это возможно, и ни один из них не покинет своего партнера. Однако паросочетание из пар (m', w) и (m, w') тоже устойчиво, так как обе женщи- ны довольны, насколько это возможно. Запомните этот важный момент, прежде чем двигаться дальше, — в заданной ситуации может существовать более одного устойчивого паросочетания.

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

Еще по теме Примеры:

  1. Примеры жестокости по отношению к другим (эти примеры более всего относятся к семейной жизни):
  2. ПРИМЕР 2
  3. Пример 1.
  4. ПРИМЕР 2
  5. Пример 2.
  6. Пример 2.
  7. Пример 2.
  8. Пример.
  9. ПРИМЕР
  10. Действенность примеров
  11. ПРИМЕР 2
  12. Пример 4.
  13. Заключение по примерам
  14. Пример «чуда».
  15. Пример «чуда».