Упражнения с решениями - Введение: некоторые типичные задачи

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

Имеется город, в котором n мужчин и n женщин пытаются вступить в брак. У каждого мужчины имеется список предпочтений, содержащий оценки всех женщин, а у каждой женщины — список предпочтений с оценками всех мужчин.

Множество всех 2n людей разделено на две категории: хорошие люди и плохие люди. Предположим, для некоторого числа к (1 ≤ k ≤ n - 1) имеются k хороших мужчин и k хороших женщин; следовательно, существует n - k плохих мужчин и n - k плохих женщин.

Каждый участник предпочитает любого хорошего человека любому плохому человеку. Формально каждый список предпочтений обладает тем свойством, что оценка любого хорошего человека противоположного пола выше оценки любого плохого человека противоположного пола: первые k позиций в нем занимают хорошие люди (противоположного пола) в некотором порядке, а затем идут n - k плохих людей (противоположного пола) в некотором порядке.

Покажите, что в каждом устойчивом паросочетании каждый хороший мужчина вступает в брак с хорошей женщиной.

Решение

Естественный подход к подобным задачам — предположить, что утверждение ложно, и попытаться прийти к противоречию. Что будет означать ложность исходной предпосылки в данном случае? Что существует некоторое устойчивое паросочетание M, в котором хороший мужчина m находится в паре с плохой женщиной w.

Теперь нужно понять, как выглядят остальные пары из M. Всего есть k хороших мужчин и k хороших женщин. Может ли при этом каждая хорошая женщина находиться в паре с хорошим мужчиной в этом паросочетании M? Нет: один из хороших мужчин (а именно m) уже выбрал плохую женщину, поэтому осталось всего k - 1 других хороших мужчин. Следовательно, даже если все остальные находятся в паре с хорошими женщинами, все равно остается некоторая плохая женщина, которая находится в паре с плохим мужчиной.

Обозначим ее w'. Теперь в M легко выявляется неустойчивость: возьмем пару (m, w'). Каждый из ее участников хорош, но находится в паре с плохим партнером. Получается, что каждый из участников потенциальной пары m и w' предпочитает другого своему текущему партнеру, а следовательно, пара (m, w') создает неустойчивость. Это противоречит исходному допущению об устойчивости M, что и требовалось доказать. ■

Упражнение с решением 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) привести пример множества списков предпочтений и запрещенных пар, для которых не существует устойчивого паросочетания.

Решение

Алгоритм Гейла-Шепли в высшей степени надежен по отношению к вариациям задачи устойчивого паросочетания. Итак, если вы имеете дело с новой разновидностью задачи и не можете найти контрпример для устойчивости, часто бывает полезно проверить, действительно ли прямая адаптация алгоритма Гейла-Шепли породит устойчивое паросочетание.

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

не сработает; m не должен делать предложение женщине w, для которой пара (m, w) является запрещенной.

Рассмотрим модификацию алгоритма Гейла-Шепли, в которую будет внесено только одно изменение: мы изменим условие цикла Пока и приведем его к виду:

А теперь приведем полный алгоритм:

Сейчас мы докажем, что этот алгоритм дает устойчивое паросочетание в соответствии с новым определением устойчивости.

Прежде всего, утверждения (1.1), (1.2) и (1.3) из текста остаются истинными (в частности, завершение алгоритма потребует не более n² итераций). Кроме того, нам не нужно доказывать, что полученное паросочетание S идеально (на самом деле оно может таковым не быть). Также следует обратить внимание на дополнительные факты. Если m — мужчина, который не входит в пару из S, то m должен был сделать предложение всем не запрещенным женщинам; и если w — женщина, которая не входит в пару из S, то из этого следует, что ни один мужчина не делал ей предложение.

Наконец, осталось доказать последнее утверждение:

(1.9) В отношении возвращаемого паросочетания S не существует неустойчивости.

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

Для начала предположим, что существует неустойчивость типа (1), состоящая из пар (m, w) и (m', w') в S и обладающая тем свойством, что (m, w') ∉ F, m предпочитает w' женщине w, а w' предпочитает m мужчине m'. Из этого следует, что m должен был сделать предложение w'; получается, что w' ему отказала, а значит, она предпочитает своего окончательного партнера m — противоречие.

Далее предположим, что существует неустойчивость типа (1), состоящая из пары (m, w) ∈ S и мужчины m' и обладающая тем свойством, что m' не входит ни в одну пару, (m', w) ∉ F и wпредпочитает m' мужчине m. Из этого следует, что m' должен был сделать предложение w и получить отказ; и снова это означает, что w предпочитает своего окончательного партнера m' — противоречие.

Если существует неустойчивость типа (3), состоящая из пары (m, w) ∈ S и женщины w' и обладающая тем свойством, что w' не входит ни в одну пару, (m, w') ∉ F и m предпочитает w' женщине w. В этом случае ни один мужчина вообще не делал предложения w'; в частности, m не делал предложения w', поэтому он должен предпочитать w женщине w' — противоречие.

Наконец, предположим, что существует неустойчивость типа (4), состоящая из мужчины m и женщины w, ни один из которых не является частью ни одной пары в паросочетании, так что (m, w') ∉ F. Но чтобы m не имел пары, он должен был сделать предложение каждой женщине, брак с которой ему не запрещен; в частности, он должен был сделать предложение w, но тогда она не была бы одинока — противоречие. ■

Упражнения

1. Решите, является ли приведенное ниже утверждение истинным или ложным. Если оно истинно, приведите короткое объяснение; если ложно — приведите контрпример.

Истинно или ложно? В любой конфигурации задачи устойчивых паросочетаний существует устойчивое паросочетание, содержащее пару (m, w), в котором m находится на первом месте в списке предпочтений w, а w находится на первом месте в списке предпочтений m.

2. Решите, является ли приведенное ниже утверждение истинным или ложным. Если оно истинно, приведите короткое объяснение; если ложно — приведите контрпример.

Истинно или ложно? Допустим, имеется конфигурация задачи устойчивых паросочетаний с мужчиной m и женщиной w, для которых m находится на первом месте в списке предпочтений w, а wнаходится на первом месте в списке предпочтений m. В этом случае в каждом устойчивом паросочетании S для этой конфигурации пара (m, w) принадлежит S.

3. Существует много других ситуаций, в которых можно задавать вопросы, относящиеся к некой разновидности принципа “устойчивости”. В следующем примере используется формулировка, основанная на конкуренции между двумя компаниями.

Допустим, имеются две телевизионные сети; назовем их A и В. Также доступны n программных окон в течение времени массового просмотра, а каждая сеть проводит n телевизионных передач. Каждая сеть хочет создать расписание — схему распределения передач по разным окнам, чтобы обеспечить себе как можно большую долю рынка.

Следующий способ поможет сравнить, насколько хорошо две сети справляются со своей задачей, исходя из их расписания. У каждой передачи имеется фиксированный рейтинг, основанный на количестве людей, посмотревших передачу в прошлом году; будем считать, что рейтинги двух передач никогда не совпадают. Сеть выигрывает заданное окно, если передача, которую она ставит в это окно, обладает более высоким рейтингом, чем передача в расписании других сетей для этого окна. Цель каждой сети — захватить как можно больше окон. Допустим, в первую неделю осеннего сезона сеть A публикует расписание S, а сеть В — расписание T. На основе этой пары расписаний каждая сеть захватывает некоторые окна в соответствии с приведенным выше правилом. Пара расписаний (S, T) будет называться устойчивой, если ни одна из сетей не может в одностороннем порядке изменить свое расписание и получить дополнительные окна. Иначе говоря, не существует расписания S' такого, что сеть Л с парой (S', T) получит больше окон, чем с парой (S, T). По соображениям симметрии также не существует расписания T', с которым сеть В со своей парой (S, T') захватит больше окон, чем с парой (S, T). Аналогия вопроса Гейла и Шепли для подобной устойчивости выглядит так: можно ли утверждать, что для каждого множества телепередач и оценок всегда существует устойчивая пара расписаний? Чтобы ответить на этот вопрос, сделайте одно из двух:

(а) приведите алгоритм, который для любого множества передач и связанных с ними оценок строит устойчивую пару расписаний; или

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

4. Гейл и Шепли опубликовали свою статью о задаче устойчивых паросочетаний в 1962 году; однако разновидность их алгоритма к тому времени уже почти 10 лет использовалась Национальной программой распределения студентов-медиков по больницам.

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

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

Распределение студентов по больницам называется устойчивым, если не встречается ни одна из следующих ситуаций:

♦ Неустойчивость первого типа: имеются студенты s и s', а также больница h, для которых:

• s назначается в h,

• s' не назначается ни в одну больницу,

• h предпочитает s' студенту s.

♦ Неустойчивость второго типа: имеются студенты s и s', а также больницы h и h', для которых:

• s назначается в h,

• s' назначается в h',

• h предпочитает s' студенту s,

• s предпочитает h студенту h'.

Фактически ситуация повторяет задачу устойчивых паросочетания, если не считать того, что 1) в больницах обычно открыто более одной вакансии и 2) студентов больше, чем вакансий.

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

5. Задача устойчивых паросочетаний в том виде, в каком она рассматривалась в тексте, подразумевает, что у всех мужчин и женщин имеются полностью упорядоченные списки предпочтений. В этом упражнении будет рассмотрена версия задачи, в которой мужчины и женщины могут считать некоторые варианты равноценными. Как и прежде, имеется множество M из n мужчин и множество W из n женщин. Допустим, каждый мужчина и каждая женщина оценивают представителей противоположного пола, но в списке предпочтений допускаются совпадения. Например (с n = 4) женщина может сказать, что m₁ находится на первом месте; второе место делят m₂ и m₃, а последнее место занимает m₄. Мы говорим, что w предпочитает m мужчине m', если mзанимает в ее списке предпочтений более высокое место, чем m' (при отсутствии равенства).

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

(a) Сильная неустойчивость в идеальном паросочетании S состоит из мужчины m и женщины w, каждый из которых предпочитает другого своему текущему партнеру в S. Всегда ли существует идеальное паросочетание без сильной неустойчивости? Либо приведите пример множества мужчин и женщин со списками предпочтений, в котором в каждом идеальном паросочетании имеется сильная неустойчивость, либо приведите алгоритм, который гарантированно находит идеальное паросочетание без сильной неустойчивости.

(b) Слабая неустойчивость в идеальном паросочетании S состоит из мужчины m и женщины w, находящихся в паре с w' и m' соответственно, при выполнении одного из следующих условий:

• m предпочитает w женщине w' и w либо предпочитает m мужчине m', либо считает эти варианты равноценными; или

• w предпочитает m женщине m' и m либо предпочитает w женщине w', либо считает эти варианты равноценными.

Другими словами, пара, в которой участвуют m и w, либо предпочтительно для обоих, либо предпочтительна для одного, тогда как другому все равно. Всегда ли существует идеальное паросочетание без слабой неустойчивости? Либо приведите пример множества мужчин и женщин со списками предпочтений, в котором в каждом идеальном паросочетании имеется слабая неустойчивость, либо приведите алгоритм, который гарантированно находит идеальное паросочетание без слабой неустойчивости.

6. Транспортной компании Peripatetic Shipping Lines, Inc., принадлежат n кораблей, которые обслуживают n портов. У каждого корабля имеется расписание, в котором для каждого дня месяца указано, в каком порту он стоит в настоящий момент (или находится в море). (Можно считать, что месяц состоит из m дней, m > n.) Каждый корабль посещает каждый порт ровно на один день в месяц. По соображениям безопасности в PSL Inc. действует следующее жесткое требование:

√ Никакие два корабля не могут находиться в одном порту в один день.

Компания хочет провести техническое обслуживание всех своих кораблей по следующей схеме. Расписание каждого корабля S_i сокращается: в какой-то день он прибывает в назначенный порт и остается здесь до конца месяца. Это означает, что корабль S_i в этом месяце не будет посещать остальные порты по расписанию, но это нормально. Итак, сокращенный вариант расписания S_iсостоит из исходного расписания до заданной даты, в которой корабль приходит в порт P; всю оставшуюся часть расписания он просто остается в порту P. Компания хочет получить ответ на следующий вопрос: Как при заданных расписаниях каждого корабля построить сокращенную версию каждого расписания, чтобы условие (√) продолжало выполняться: никакие два корабля никогда не должны оказываться в одном порту в один день. Покажите, что такое множество сокращений всегда может быть найдено, и приведите алгоритм для его построения.

Пример. Допустим, имеются два корабля и два порта и “месяц” состоит из четырех дней. Расписание первого корабля выглядит так:

порт Р₁; в море; порт P₂; в море

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

в море; порт P₁; в море; порт Р₂

Существует только один вариант выбора сокращенных расписаний — первый корабль остается в порту P₂, начиная с дня 3, а второй корабль остается в порту P₁, начиная с дня 2.

7. Ваши друзья работают в компании CluNet, занимающейся созданием крупных коммуникационных сетей. Им нужен алгоритм, управляющий работой конкретного типа коммутатора.

Существует n входных проводов и n выходных проводов, каждый из которых направлен от источника к приемнику данных. Каждый входной провод стыкуется с выходным через специальное устройство, называемом соединительным блоком. Точки на проводах естественным образом упорядочиваются в направлении от источника к приемнику; для двух разных точек x и у на одном проводе точка x расположена выше у, если x находится ближе к источнику, чем у. В противном случае говорят, что точка x находится ниже точки у. Порядок, в котором один входной провод контактирует с выходными проводами, не обязательно совпадает с порядком, в котором с ними контактирует другой входной провод. (Это относится и к порядку, в котором выходные провода контактируют со входными.) На рис. 1.8 приведен пример такой конфигурации входных и выходных проводов.

Рис. 1.8. Конфигурация с двумя входными и двумя выходными проводами.

Вход 1 контактирует с Выходом 2 выше контакта с Выходом 1; Вход 2 контактирует с Выходом 1 выше контакта с Выходом 2. Допустимым решением будет переключение потока данных Входа 1 на Выход 2, а потока данных Входа 2 — на Выход 1. С другой стороны, если переключить поток Входа 1 на Выход 1, а поток Входа 2 — на Выход 2, то оба потока будут проходить через соединительный блок в точке контакта Входа1 и Выхода 2 — а это недопустимо

А теперь перейдем собственно к коммутации. По каждому входному проводу передается свой поток данных, который должен быть передан на один из выходных проводов. Если поток Входа iпереключается на Выход j в соединительном блоке B, то этот поток проходит через все соединительные блоки, расположенные выше B на Входе i, затем через B и через все соединительные блоки, расположенные ниже B на Выходе j. Неважно, какой входной поток данных переключается на тот или иной выходной провод, но каждый входной поток должен быть подан на отдельный выходной провод. Кроме того — в этом-то вся сложность! — никакие два потока данных не могут проходить через один соединительный блок после операции переключения.

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

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

Чтобы ответить на этот вопрос, сделайте одно из двух:

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

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

Примечания и дополнительная литература

Задача устойчивых паросочетаний была впервые определена и проанализирована Гейлом и Шепли (Gale, Shapley, 1962); по словам Дэвида Гейла, побудительной причиной для анализа задачи стала история, прочитанная ими в еженедельнике “Нью-Йоркер” о сложностях организации вступительных экзаменов в колледжах (Gale, 2001). Поиск устойчивых паросочетаний превратился в самостоятельную область исследований, которая рассматривается в книгах Гасфилда и Ирвинга (Gusfield, Irving, 1989) и Кнута (Knuth, 1997c). Гасфилд и Ирвинг также предоставляют хороший обзор “параллельной” истории задачи устойчивых паросочетаний на примере механизма, который был разработан для подбора сочетаний кандидатов и нанимателей в медицине и других областях.

Как упоминалось в этой главе, наши пять типичных задач будут занимать центральное место в основных темах книги — а именно “жадных” алгоритмах, динамическом программировании, нахождении потока в сети, ЖР-полноте и PSPACE- полноте. Все эти задачи будут рассмотрены в указанных контекстах позднее в книге.

---

¹ Гейл и Шепли также рассматривали задачу однополых устойчивых паросочетаний. У нее тоже имеются свои практические применения, но на техническом уровне возникают достаточно заметные отличия. С учетом схемы “кандидат-наниматель”, которая здесь рассматривается, мы будем придерживаться версии с двумя полами.

² Также встречается термин “марьяж”. — Примеч. пер.

³ Для любознательных читателей заметим, что не каждая конфигурация задачи поиска независимых множеств может быть получена из задач интервального планирования или двудольных паросочетаний: полная задача независимых множеств является более общей. Граф на рис. 1.3, а не может быть сгенерирован как “граф конфликтов” в задаче интервального планирования, а граф на рис. 1.3, б — как граф конфликтов в задаче двудольных паросочетаний.