Анализ алгоритма

Для начала рассмотрим ситуацию с точки зрения женщины w во время выпол- нения алгоритма. Какое-то время она не получает предложений и остается сво- бодной. Потом мужчина m может сделать ей предложение, и она становится помолвленной.
Со временем она может получить дополнительные предложения и принять те из них, в которых повышается оценка ее партнера. Итак, мы приходим к следующим выводам:

(1.1) Женщина w остается помолвленной с момента получения первого предложе- ния; партнеры, с которыми она вступает в помолвку, становятся все лучше и лучше (в контексте ее списка предпочтении).

С точки зрения мужчины m, во время выполнения алгоритма все происходит иначе. Он остается свободным до тех пор, пока не сделает предложение женщине

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

(1.2) Последовательность женщин, которым m делает предложение, постоянно ухудшается (в контексте его списка предпочтений).

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

(1.3) Алгоритм Гейла-Шепли завершается после выполнения максимум n2 итераций цикла «Пока».

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

В рассматриваемом алгоритме каждая итерация состоит из предложения, ко- торое некий мужчина делает (не более одного раза) женщине, к которой он еще не обращался ранее. Итак, если обозначить P(t) множество пар (m, w), в которых мужчина m делал предложение w к моменту завершения итерации t, мы видим, что для всех t размер P(t + 1) строго больше размера P(t). Однако всего существует только n2 возможных пар, так что за время выполнения алгоритма значение P() может возрасти не более n2 раз. Следовательно, выполнение алгоритма может по- требовать не более n2 итераций. ■

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

Теперь докажем, что множество S, возвращаемое при завершении алгоритма, действительно является идеальным паросочетанием. Почему это не очевидно? По сути, нужно показать, что ни один мужчина не остановится в конце своего списка предпочтений; выход из цикла возможен только в том случае, если ни одного сво- бодного мужчины не осталось. В этом случае набор помолвленных пар действи- тельно будет идеальным паросочетанием.

Итак, необходимо доказать следующее:

(1.4) Если мужчина m свободен в какой-то точке выполнения алгоритма, то существует женщина, которой он еще не делал предложение.

Доказательство. Предположим, существует точка, в которой мужчина m свобо- ден, но уже сделал предложение всем женщинам. Тогда из (1.1) следует, что каждая

из n женщин на этот момент уже помолвлена. Так как набор помолвленных пар образует паросочетание, при этом также должно быть n помолвленных мужчин. Но мужчин всего n, а согласно исходному предположению, m не помолвлен; воз- никает противоречие. ■

(1.5) Множество S, возвращаемое при завершении, является идеальным паро- сочетанием.

Доказательство. Множество помолвленных пар всегда образует паросочета- ние. Предположим, что алгоритм завершается со свободным мужчиной m. При завершении m должен был уже сделать предложение всем женщинам, в противном случае цикл бы не завершился. Но это противоречит положению (1.4), согласно которому не может быть свободного мужчины, который уже сделал предложение всем женщинам. ■

Наконец, мы доказали главное свойство алгоритма, а именно то, что он приво- дит к устойчивому паросочетанию.

(1.6) Возьмем выполнение алгоритма Гейла-Шепли, возвращающее множество пар S. Это множество S является устойчивым паросочетанием.

Доказательство. Из (1.5) мы уже знаем, что S является идеальным паросочета- нием. Таким образом, чтобы доказать, что S является устойчивым паросочетанием, мы предположим, что существует неустойчивость по отношению к S, и придем к противоречию. Согласно приведенному ранее определению, при такой неустой- чивости S будет содержать две пары (m, w) и (m', w'), в которых:

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

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

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

Следовательно, S является устойчивым паросочетанием. ■

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

Еще по теме Анализ алгоритма:

  1. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  4. АЛГОРИТМ
  5. АЛГОРИТМ УДАЧИ
  6. Алгоритм исцеления:
  7. Алгоритм избавления от боли
  8. 2. Специфика и алгоритмы работы с источниками.
  9. Алгоритм обработки результатов.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
  12. Принципы анализа происшествия.
  13. АНАЛИЗ
  14. АНАЛИЗ КОРОТКИЙ
  15. КОНТЕНТ - АНАЛИЗ
  16. Анализ документов
  17. МЕТОД АНАЛИЗА ЖИЗНИ