Упражнения 1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

♦ Неустойчивость первого типа: имеются студенты 5 и 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) женщина может сказать, что ml находится на первом месте; второе место делят m2 и m3, а последнее место занимает m4. Мы говорим, что 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. действует следующее жесткое тре- бование:

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

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

Существует только один вариант выбора сокращенных расписаний — первый корабль остается в порту P2, начиная с дня 3, а второй корабль остается в пор- ту P1, начиная с дня 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) и выполнением алгоритма с ложным списком предпочтений w окажется в паре с мужчиной т”, которого она в действительности предпочитает как т, так и т'? (Тот же вопрос можно задать и для мужчин, но в контексте нашего упражнения мы ограничимся женщинами.)

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

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

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

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

Еще по теме Упражнения 1.:

  1. УПРАЖНЕНИЕ
  2. Приведем список всех упражнений и их номера:
  3. 5.4. Планирование упражнений
  4. Упражнение 2
  5. Упражнение 3
  6. Упражнение 4
  7. Упражнение 5
  8. Упражнение 6
  9. Упражнение 7
  10. Упражнение 8
  11. Упражнение 9
  12. Упражнение 10