Расширения

Мы начали с определения устойчивого паросочетания и только что доказали, что алгоритм Гейла-Шепли действительно строит его. Теперь будут рассмотрены неко- торые дополнительные вопросы относительно поведения алгоритма Гейла-Шепли и его связи со свойствами различных устойчивых паросочетаний.

Прежде всего вернемся к тому, что было продемонстрировано в одном из пре- дыдущих примеров с несколькими устойчивыми паросочетаниями.

Вспомните, что списки предпочтений в этом примере выглядели так:

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

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

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

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

Теперь при любом выполнении алгоритма Гейла-Шепли m будет помолвлен с w, m’ будет помолвлен с w’ (возможно, в обратном порядке), и на этом все остановится. Следовательно, другое устойчивое паросочетание, состоящее из пар (m’, w) и (m, w’), недостижимо при выполнении алгоритма Гейла-Шепли, в котором мужчины делают предложение. С другой стороны, оно станет достижимым при выполнении версии алгоритма, в которой предложение делают женщины. А в более крупных примерах, в которых с каждой стороны задействовано более двух участников, может существовать еще большее количество возможных устойчивых паросоче- таний, многие из которых не могут быть сгенерированы никаким естественным алгоритмом.

Этот пример демонстрирует некоторую «несправедливость» алгоритма Гейла- Шепли, «подыгрывающего» мужчинам. Если предпочтения мужчин идеально рас- пределены (то есть все они ставят на первое место разных женщин), то при любом выполнении алгоритма Гейла-Шепли каждый мужчина окажется в паре со своей главной кандидатурой независимо от предпочтений женщин. Если же предпочте- ния женщин полностью расходятся с предпочтениями мужчин (как в приведенном примере), то полученное устойчивое паросочетание будет насколько возможно плохим для женщин.

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

Давайте проанализируем алгоритм Гейла-Шепли более подробно и попробуем понять, насколько общий характер имеет эта «несправедливость».

Прежде всего, наш пример подчеркивает то обстоятельство, что формулировка алгоритма Гейла-Шепли не является полностью детерминированной: каждый раз, когда имеется свободный мужчина, можно выбрать любого свободного мужчину, который сделает следующее предложение. Различные варианты выбора приводят к разным путям выполнения алгоритма; вот почему в формулировке (1.6) исполь- зуется осторожное «Возьмем выполнение алгоритма Гейла-Шепли, возвращающее множество пар S», а не «Возьмем множество пар S, возвращаемое алгоритмом Гейла-Шепли».

Возникает другой, тоже очень естественный вопрос: приводят ли все выполне- ния алгоритма Гейла-Шепли к одному паросочетанию? Вопросы такого рода воз- никают во многих областях теории обработки данных: имеется алгоритм, который работает асинхронно, с множеством независимых компонентов, которые выпол- няют операции с возможностью сложных взаимодействий. Требуется определить, какую изменчивость вносит такая асинхронность в окончательный результат.

Или совершенно другой пример: независимыми компонентами могут быть не мужчины и женщины, а электронные устройства, активизирующие части крыла самолета; последствия асинхронности в их поведении могут быть очень серьезными.

В текущем контексте ответ на этот вопрос оказывается на удивление простым: все выполнения алгоритма Гейла-Шепли приводят к одному паросочетанию. Докажем это утверждение.

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

Еще по теме Расширения:

  1. ВАРИКОЗНОЕ РАСШИРЕНИЕ ВЕН
  2. Расширение графического метода
  3. Самовоспитание как "расширение" сознания
  4. 3.1. РАСШИРЕНИЕ НЕЙРОЛОГИЧЕСКОГО КОНТАКТА
  5. 3.12.2. Техника расширенного восприятия
  6. Расширение внутреннего кругозора
  7. 7.2.2. Расширение полноты ответа
  8. 7.2.2. Расширение полноты ответа
  9. Метод расширения сознания
  10. 2. Расширение круга наследников по закону в российском наследственном праве
  11. 2. Расширение сети вольной русской прессы в 1860-е годы
  12. Развивающие вопросы призваны способствовать расширению поля беседы в сторону уточнения деталей, эмоциональных переживаний героя, включая ее в более широкий контекст.
  13. VC16 - расположена на уровне 5-го межреберья.
  14. Успех
  15. Линия 5-7 (Юпитер-Сатурн)
  16. § 2. Полномочия главы государства
  17. Линия свободы достижения цели 4-5-6
  18. ДИСКРИМИНАЦИЯ
  19. Концентрация ? медитация