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

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

Система работает так: определены к праздничных периодов (Рождественская неделя, выходные Дня независимости, выходные Дня благодарения, ...), каждый из которых занимает несколько смежных дней. Пусть D — множество дней, включен- ных в -й праздничный период; объединение всех этих дней U D будет называться множеством всех праздничных дней.

В больнице работают n врачей, за каждым врачом i закреплено множество праздничных дней S, когда он может выйти на работу. (В это множество может входить лишь часть дней из некоторых праздничных периодов; например, врач может работать в пятницу, субботу и воскресенье в период Дня благодарения, но не в четверг.)

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

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

♦ Для каждого праздничного периода j каждый врач может быть назначен на работу не более чем в один из дней множества D. (Например, хотя конкретный врач может работать в несколько праздничных дней в течение года, он не может работать более одного дня в выходные Дня благодарения, более одного дня в выходные Дня независимости и т. д.)

Алгоритм должен либо возвращать распределение, удовлетворяющее этим ограничениям, либо (обоснованно) сообщать о том, что такое распределение не существует.

Решение

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

Для начала посмотрим, как бы решалась эта задача без такого требования — в упрощенном случае, когда у каждого врача i имеется множество Si дней, когда он может работать, и каждый врач должен работать не более c дней. Схема изо- бражена на рис. 7.23(a). Узлы и представляют врачей, и связываются с узлами v, представляющими дни, когда они могут выйти на работу; ребро имеет пропускную способность 1. Суперисточник 5 связывается с каждым узлом врача и ребром с про- пускной способностью с, и каждый узел дня v связывается с суперстоком t ребром, верхняя и нижняя границы которого равны 1. В этом случае назначенные дни «пе- реходят» по врачам на дни, в которые те могут работать, а нижние границы ребер от дней до стока гарантируют, что каждый день будет обеспечен врачом. Наконец, предположим, что общее количество праздничных дней равно d; мы назначаем стоку уровень потребления +d, источнику — уровень потребления -d, а затем ищем действительную циркуляцию. (Вспомните, что после введения нижних границ для некоторых ребер алгоритмы формулируются в терминологии циркуляции с по- треблением, а не максимального потока.)

Праздники


Ъ

Рис. 7.23. a — врачи связываются с выходными днями без ограничения того, сколько дней за один праздничный период может отработать врач; b — потоковая сеть дополняется «регуляторами», не позволяющими врачу работать более одного дня в каждый праздничный период. Множества, выделенные серым цветом, соответствуют разным праздничным периодам


Но мы должны обеспечить выполнение дополнительного требования: что каж- дый врач может отработать не более одного дня за каждый праздничный период. Для этого берется каждая пара (i, j), состоящая из врача i и праздничного периодаj, и добавляется «регулятор» — новый узел w.. с входящим ребром с пропускной способностью 1 от узла врача и,, и выходящими ребрами с пропускной способно-

стью 1 к каждому дню праздничного периода j, когда врач i доступен для работы. Регулятор «сужает» поток от и к дням праздничного периодаj, чтобы к ним могла проходить максимум одна единица потока. Схема изображена на рис. 7.23, b. Как и прежде, мы назначаем для стока уровень потребления +d, для источника — уро- вень потребления -d, и ищем действительную циркуляцию. Общее время выпол- нения соответствует времени построения графа, которое равно O(nd), плюс время поиска одной действительной циркуляции в этом графе.

Правильность алгоритма следует из следующего утверждения.

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

Доказательство. Во-первых, если вариант связывания врачей с праздничны- ми днями с соблюдением всех ограничений существует, то мы можем построить следующую циркуляцию. Если врач i работает в день l праздничного периодаj, мы передаем одну единицу потока по пути s, и, Wj, v, t; это делается для всех таких пар (i, l). Так как распределение врачей удовлетворяет всем ограничениям, полученная циркуляция соблюдает все пропускные способности; кроме того, она отправляет d единиц потока из s и доставляет его в t, а следовательно, соблюдает уровни по- требления.

И наоборот, предположим, что существует действительная циркуляция. В этом направлении доказательства мы покажем, как использовать циркуляцию для построения расписания для всех врачей. Прежде всего, согласно (7.52), существует действительная циркуляция, в которой все величины потоков яв- ляются целыми числами. Теперь мы построим расписание следующим образом: если ребро (Wij, vl) передает единицу потока, то врач i работает в день l. Из-за пропускных способностей в полученном расписании каждый врач работает не более c дней, не более одного в каждом праздничном периоде, и в каждый день работает один врач. ■

Упражнения

1. (a) Перечислите все минимальные разрезы s-t в потоковой сети, изображен- ной на рис. 7.24. Рядом с каждым ребром на схеме обозначена его пропускная способность.

(b) Какова минимальная пропускная способность разреза s-t в потоковой сети на рис. 7.25? Как и в предыдущем случае, пропускная способность каждого ребра обозначена рядом с ним.

2. На рис. 7.26 изображена потоковая сеть с вычисленным потоком s-t. Рядом с каждым ребром на схеме обозначена его пропускная способность, а числа в прямоугольниках задают величину потока, передаваемого по каждому ребру. (Ребра без чисел в прямоугольниках — а именно четыре ребра с пропускной способностью 3 — не передают поток.)

(a) Какова величина этого потока? Является ли он максимальным потоком (s, t) в этом графе?

(b) Найдите минимальный разрез s-t в потоковой сети, изображенной на рис. 7.26. Укажите, чему равна его пропускная способность.

Рис. 7.24. Найдите минимальные разрезы s-t в этой потоковой сети


Рис. 7.25. Определите минимальную пропускную способность разреза s-t в этой потоковой сети


Рис. 7.26. Найдите величину изображенного потока. Является ли он максимальным? Найдите минимальный разрез


3. На рис. 7.27 изображена потоковая сеть с вычисленным потоком s-t. Рядом с каждым ребром на схеме обозначена его пропускная способность, а числа в прямоугольниках задают величину потока, передаваемого по каждому ребру. (Ребра без чисел в прямоугольниках не передают поток.)

(a) Какова величина этого потока? Является ли он максимальным потоком (s, t) в этом графе?

(b) Найдите минимальный разрез s-t в потоковой сети, изображенной на рис. 7.27. Укажите, чему равна его пропускная способность.

Рис. 7.27. Найдите величину изображенного потока. Является ли он максимальным? Найдите минимальный разрез


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

Пусть G — произвольная потоковая сеть с источником s, стоком t и положи- тельной целочисленной пропускной способностью ce для каждого ребра e. Если f — максимальный поток s-t в G, то f насыщает каждое ребро, выходящее из s (то есть для всех ребер e, выходящих из s, выполняется условие f(e) = ce).

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

Пусть G — произвольная потоковая сеть с источником s, стоком t и положи- тельной целочисленной пропускной способностью ce для каждого ребра e; пусть (A, B) — минимальный разрез s-t для этих пропускных способностей {ce : e E}. Предположим, каждая пропускная способность увеличивается на 1; в этом случае (A, B) останется минимальным разрезом s-t для новых пропускных спо- собностей {1 + ce : e E}.

6. Представители Комиссии по архитектурной эргономике обратились к вам за консультацией.

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


Иногда это возможно, иногда нет. Возьмем два простых плана домов на рис. 7.28; на них размещены три светильника (а, b, с) и три выключателя (1, 2, 3). На рис. 7.28, a выключатели можно связать со светильниками так, чтобы от каждого выключателя проходила линия видимости к светильнику, но на рис. 7.28, b это невозможно.

Рис. 7.28. План (a) эргономичен, потому что выключатели можно связать со светильниками так, что каждый светильник будет виден от управляющего им выключателя. (Выключатель 1 связывается с а, выключатель 2 с b, а выключатель 3 с с). План (b) не эргономичен, потому что такое связывание невозможно

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

Предложите алгоритм, который будет решать, является ли заданный план эргономичным. Время выполнения алгоритма должно быть полиномиальным по m и n. Считайте, что у вас имеется процедура с временем выполнения 0(1), которая получает два отрезка и проверяет, пересекаются ли они на плоскости.

7. Рассмотрим группу клиентов мобильных устройств, которые должны быть под- ключены к одной из нескольких возможных базовых станций. Всего клиентов n, позиция каждого клиента задается координатами (х, у) на плоскости. Также существуют к базовых станций; их позиции тоже заданы координатами (х, у). Требуется, чтобы каждый клиент подключался ровно к одной станции. Выбор вариантов подключения ограничивается парой факторов.

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

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

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

Как известно, в крови каждого человека присутствуют определенные антиге- ны (своего рода молекулярная сигнатура); пациенту нельзя переливать кровь с определенным антигеном, если этот антиген отсутствует в его крови. А если говорить конкретнее, в соответствии с этим правилом кровь делится на четыре группы: A, B, AB и O. Кровь группы A содержит антиген A, кровь группы B — антиген B, кровь группы AB содержит оба антигена, и кровь группы O не содер- жит ни одного. Таким образом, пациентам с группой крови A при переливании могут получать только кровь групп A и O, пациентам с группой B — только B и O, пациентам с группой O — только O, и пациенты с группой крови AB могут получать кровь любой группы[12].

(a) Пусть sO, sA, sB и s — запасы крови разных групп. Известны про- гнозируемые потребности в крови всех четырех групп dO, dA, dB и dAB на следующую неделю. Предложите алгоритм с полиномиальным временем для определения достаточности имеющихся запасов при прогнозируемой потребности.

(b) Рассмотрим следующий пример: ожидается, что за следующую неделю потребуется не более 100 единиц крови. Типичное распределение крови по группам среди пациентов в США выглядит так: примерно 45 % — группа O, 42 % — группа A, 10 % — группа B, и 3 % — группа AB. Больница хочет знать, хватит ли имеющегося запаса при поступлении 100 пациентов с ожидаемым распределением групп. Всего на складе доступно 105 единиц. В следующей таблице приведена сводка прогнозируемой потребности и имеющихся за- пасов.


Достаточно ли имеющихся 105 единиц для потребности в 100 единиц? Найдите распределение, удовлетворяющее максимально возможное количество паци- ентов. Чтобы показать, почему не все пациенты смогут получить донорскую кровь, воспользуйтесь аргументом, основанным на разрезе с минимальной пропускной способностью. Также приведите объяснение этого факта, понятное администрации больницы, не искушенной в алгоритмах (соответственно, в этом объяснении не должны встречаться слова «поток», «разрез» или «граф» в том смысле, в котором они использовались в книге).

9. Алгоритмы потоков в сети часто встречаются при организации работ в зоне при- родных катастроф и других экстренных ситуациях, так как крупные непредви- денные события часто требуют перемещения и эвакуации большого количества людей за короткое время.

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

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

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

10. Имеется направленный граф G = (V, E) с положительной целочисленной про- пускной способностью ce каждого ребра e, источником 5 V и стоком t V.

Также задан максимальный поток s-t в G, определяемый величиной потока f по каждому ребру e. Поток f является ациклическим: в G не существует цикла, в котором по всем ребрам передается положительный поток. Поток f также является целочисленным.

Допустим, мы выбираем некоторое ребро e* E и уменьшаем его пропускную способность на одну единицу. Покажите, как найти максимальный поток в по- лученном графе за время O(m + n), где m — количество ребер в G, а n — коли- чество узлов.

11. Ваши знакомые программисты написали очень быстрый код нахождения мак- симального потока, основанный на многократном нахождении увеличивающих путей (как описано в разделе 7.1). Однако просматривая результаты выполне- ния, вы обнаруживаете, что алгоритм не всегда находит поток с максимальной величиной. Ошибка обнаруживается очень быстро; ваши знакомые не разо- брались в проблеме обратных ребер, и их реализация строит остаточный граф, который включает только прямые ребра. Другими словами, она ищет пути s-t в графе Gr , состоящем только из ребер е, для которых f(е) < ce, и завершается при отсутствии улучшающего пути, состоящего только из таких ребер. Назовем эту реализацию «алгоритмом с прямыми ребрами». (Обратите внимание: мы не пытаемся указывать, как этот алгоритм выбирает свои пути с прямыми ребра- ми; он может выбирать их так, как считает нужным, при условии, что его вы- полнение будет завершено только при отсутствии путей с прямыми ребрами.) Вам будет нелегко убедить своих знакомых, что код придется переписывать. Они утверждают, что алгоритм не только быстро работает, но и никогда не воз- вращает поток, величина которого меньше фиксированной части оптимального. А вы этому верите? Суть их утверждений можно выразить следующим образом. Существует такая абсолютная константа b > 1 (не зависящая от конкретной входной потоковой сети), что для каждого экземпляра задачи максимального потока алгоритм с прямыми ребрами гарантированно находит поток с величи- ной не менее 1/b величины максимального потока (независимо от того, как он выбирает свои пути).

Решите, является ли это утверждение истинным или ложным. Приведите до- казательство или опровержение.

12. Имеется потоковая сеть с ребрами единичной пропусной способности: она со- стоит из направленного графа G = (V, E), источника 5 Vи стока t V; ce = 1 для

всех e E. Также задан параметр к. Требуется удалить к ребер таким образом, чтобы максимальный поток s-t в G сократился как можно сильнее. Другими сло- вами, нужно найти множество ребер F ίΞ E, для которого \F | = к, а максимальный поток s-t в G' = (V, E-F) был как можно меньше.

Предложите алгоритм с полиномиальным временем для решения этой задачи.

13. В стандартной задаче о максимальном потоке s-t предполагается, что ребра

имеют пропускные способности, а величина потока, проходящего через узел, не ограничена. В этой задаче рассматривается разновидность задач о макси- мальном потоке и минимальном разрезе с пропускными способностями узлов. Пусть G = (V, E) — направленный граф с источником 5 V, и стоком t V и не- отрицательными пропускными способностями узлов {cv > 0} для всех v V. Для

потокаf в этом графе поток через узел v определяется какfn(v). Поток называет- ся действительным, если он удовлетворяет обычным ограничениям сохранения потока и ограничениям пропускной способности узлов: fn(v) < cv для всех узлов. Предложите алгоритм с полиномиальным временем для нахождения макси- мального потока s-t в такой сети, определяющей пропускные способности для узлов. Определите разрез s-t для сетей с пропускными способностями узлов и покажите, что аналогия теоремы о максимальном потоке и минимальном разрезе остается истинной.

14. Задача о выходе определяется следующим образом. Имеется направленный граф G = (V, E) (схема дорожной сети). Узлы некоторой совокупности X с V называются населенными, а узлы другой совокупности S с V называются без- опасными. (Предполагается, что X и S не пересекаются.) При возникновении чрезвычайной ситуации требуется найти эвакуационные пути из населенных узлов в безопасные. Множество эвакуационных путей определяется как мно- жество таких путей в G, что (i) каждый узел вX является начальным для одного пути, (ii) последний узел каждого пути принадлежит S, и (iii) пути не имеют пересекающихся ребер. Такой набор путей позволяет «вывести» обитателей населенных узлов в S без чрезмерной перегрузки ребер G.

(a) Для заданных G, X и S покажите, как за полиномиальное время принять решение о том, существует ли множество эвакуационных путей.

(b) Предположим, поставлена та же задача, что в (a), но мы хотим обеспе- чить еще более сильную версию запрета на перегрузку (iii). Таким образом, формулировка (iii) приводится к виду «пути не имеют общих узлов».

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

Также приведите пример с теми же G, X и S, для которых на (a) дается положи- тельный ответ, а на (b) — отрицательный.

15. Предположим, вы и ваша знакомая Аланис проживаете в студенческой коммуне с n - 2 другими людьми. За следующие n дней каждый жилец квартиры должен приготовить ужин ровно один раз, так что ежедневно кто-то занимается при- готовлением пищи.

Конечно, у каждого жильца имеются свои планы на некоторые дни (экзамены, концерты и т. д.), поэтому решить, кто должен готовить в тот или иной вечер, будет непросто. Для конкретности обозначим жильцов {pv ..., pn}, а дни {d1, ..., dn}; для человека p существует множество дней S с {d1, ..., dn}, в которые они не могут заниматься приготовлением ужина.

Действительным расписанием называется такое распределение жильцов комму- ны по дням, чтобы каждый жилец готовил ровно в один день, ежедневно кто-то готовил, и если жилецp. готовит в день d, то d. ⅜ S..

(a) Опишите такой двудольный граф G, в котором идеальное паросочетание существует в том и только том случае, если существует действительное рас- писание приготовления обедов.

(b) Ваша знакомая Аланис берется за составление действительного расписа- ния. После значительных усилий она строит то, что по ее мнению является действительным расписанием, и уходит на лекции. К сожалению, заглянув в составленное ей расписание, вы замечаете серьезную проблему. n - 2 жильцов распределены в разные дни, в которые они свободны; здесь проблем нет. Но внезапно выясняется, что для двух других людей p. и p, и двух дней dk и d, оба человека были назначены на день dk, а в день d никто не готовит.

Вы хотите исправить ошибку Аланис — но так, чтобы расписание не пришлось строить заново. Покажите, что при наличии такого «почти правильного» расписания можно за время O(n2) решить, существует ли действительное расписание для текущих исходных данных. (А если расписание существует, выведите его.)

16. На заре существования Всемирной паутины часто говорили, что большая часть огромного потенциала таких компаний, как Yahoo!, кроется в «зрачках пользователя» — то есть в том простом факте, что миллионы людей ежегодно просматривают их страницы. Кроме того, убеждая пользователей сообщать личные данные при регистрации, такой сайт, как Yahoo!, может выводить целенаправленную рекламу при каждом посещении — возможность, недо- ступная для телевизионных сетей или журналов. Скажем, если пользователь сообщает Yahoo!, что он — 20-летний студент Корнелльского университета, то сайт выводит баннер с рекламой квартир в Итаке (штат Нью-Йорк); если же пользователь является 50-летним финансовым брокером из Гринвича (штат Коннектикут), сайт выводит рекламу автосалона по продаже «Линкольнов». Но чтобы решить, какую рекламу показывать тем или иным пользователям, необходимо провести достаточно серьезные вычисления. Предположим, менед- жеры популярного сайта выявили к разных демографических групп G1, G2, ..., Gk. (Группы могут перекрываться; например, группа G1 может состоять из всех жителей штата Нью-Йорк, а группа G2 — из обладателей ученой степени по ин- форматике.) Сайт заключил контракты с m разными рекламодателями на показ определенного количества копий рекламы на сайте. Контракт с i-м рекламода- телем формулируется примерно так:

• Имеется подмножество X. Л {G1, ..., Gk} демографических групп; рекламода- тель i хочет, чтобы его реклама выводилась только у пользователей, принад- лежащих хотя бы к одной из демографических групп множества Xi.

• Для заданного числа r. рекламодатель i хочет, чтобы его реклама выводилась минимум r. пользователям в минуту.

Рассмотрим задачу планирования хорошей рекламной политики — способа по- каза одной рекламы для одного пользователя сайта. Предположим, в некоторую минуту с сайтом работают n пользователей. Так как у нас имеется регистраци- онная информация о каждом пользователем, мы знаем, что пользователь j (для j = 1, 2, ..., n) принадлежит подмножеству U Л {G1, ..., Gk} демографических групп. Задача формулируется так: существует ли способ вывода одной рекламы для каждого пользователя, чтобы выполнить контракты сайта с m рекламо- дателями за данную минуту (то есть для всех i = 1, 2, ..., m можно ли показать по крайней мере r из n пользователей, каждый из которых принадлежит по крайней мере одной демографической группе из Xi, рекламу, предоставленную рекламодателем i?)

Предложите эффективный алгоритм, который решает, возможно ли это, и если возможно — выбирает рекламу, выводимую для каждого пользователя.

17. Администраторы сети обратились к вам за помощью в диагностике. Сеть спро- ектирована для передачи трафика из источника 5 в приемник t, поэтому для ее моделирования можно использовать направленный граф G = (V, E), в котором пропускная способность каждого ребра равна 1, а каждый узел лежит по край- ней мере на одном пути от 5 до t.

Когда в сети все работает нормально, максимальный поток s-t в G имеет величи- ну к. Однако хакерская атака уничтожила некоторые ребра, и среди оставшихся ребер не осталось пути из s в t. По причинам, в которые мы не будем углублять- ся, администраторы полагают, что уничтожено только к ребер — минимальное количество, необходимое для отделения s от i (то есть размер минимального разреза s-t); будем считать, что их оценка верна.

На узле s работает контрольная программа. Если передать ей команду ping(v) (для некоторого узла v), программа сообщает, доступен ли в настоящее время путь из s в v. (Таким образом, вызов ping(t) сообщит, что путь в настоящее время недоступен; с другой стороны, вызов ping(s) всегда сообщает о наличии пути от s до s.) Проверять все ребра в сети было бы непрактично, поэтому админи- страторы хотя определить размер сбоя при помощи этой программы и разумного применения команды ping.

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

Предложите алгоритм, который решает эту задачу с использованием всего О(к log n) проверок.

18. Рассмотрим задачу о двудольном паросочетании для двудольного графа G = (V, E). Как обычно, мы говорим, что множество Vразбито на множестваX и Y, один конец каждого ребра принадлежит X, а другой принадлежит Y.

Если M — паросочетание в G, говорят, что M покрывает узел у, если y является концом одного из ребер в M.

(a) Рассмотрим следующую задачу: имеется граф G и паросочетаниеMв G. Для заданного числа к требуется решить, существует ли в G паросочетание M, для которого:

(i) M' содержит на к больше ребер, чем M, и

(ii) Каждый узел y Y, покрываемый M, также покрывается M'.

Эта задача называется задачей расширения покрытия с входными значениями G, M и к, а M' называется решением экземпляра задачи.

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

Примечание: возможно, часть (b) поможет вам в поиске решения.

Пример. Рассмотрим граф на рис. 7.29; допустим, M — паросочетание, состоящее из ребра (x1, y2). Приведенный выше вопрос задается для к = 1.

Рис. 7.29. Экземпляр расширения покрытия


В этом случае ответ на задачу расширения покрытия будет положительным. В качестве M' можно выбрать (например) паросочетание из двух ребер (x1, y2) и (x2, y4); M' содержит на одно ребро больше, чем M, и узел y2 также покрыва- ется M'.

(b) Приведите экземпляр задачи расширения покрытия, заданный параметра- ми G, M и к, для следующей ситуации.

У экземпляра есть решение, но в любом решении M ребра M не образуют под- множество ребер M'.

(c) Пусть G — двудольный граф, а M — произвольное паросочетание в G. Рас- смотрим следующие две характеристики.

• K1 — размер наибольшего паросочетания M', для которого каждый узел у, покрываемый M, также покрывается M'.

• K2 — размер наибольшего паросочетания M" в G.

Очевидно, K1 < K2, так как K2 определяется по всем возможным паросочетаниям в G.

Докажите, что K1 = K2; а именно, что максимальное паросочетание может быть получено даже в том случае, если ограничиться покрытием всех узлов, покры- ваемых исходным паросочетанием M.

19. Местная больница, которой вы уже помогали по разным вопросам планиро- вания, обратилась с новой задачей. Для каждого из следующих n дней было определено количество необходимых врачей; таким образом, в день i должны присутствовать ровно р врачей.

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

Ваша система должна учесть все списки и попытаться вернуть для каждого врача j список Lj, обладающий следующими свойствами:

(A) Lj является подмножеством L, то есть врач j работает только в те дни, кото- рые он считает приемлемыми.

(B) По всему множеству списков L'1, ..., L’k в день i присутствуют ровнор. врачей (для i = 1, 2, ..., n).

(a) Опишите алгоритм с полиномиальным временем выполнения, реализу- ющий эту систему. А конкретно предложите алгоритм с полиномиальным временем, который получает числа p1, p2, ..., p, и списки L1, ..., Lk, и делает одно из двух:

• Возвращает списки L\, L'2, ..., L'k, удовлетворяющие свойствам (A) и (B); или

• Сообщает (обоснованно) о том, что множество списков L'l, ..., L'k, удов- летворяющее свойствам (A) и (B), не существует.

(b) Руководство больницы обнаружило, что списки, полученные от врачей, слишком ограничены, и система слишком часто сообщает об отсутствии допустимого множества списков L'v L'2, ..., L'k (сообщает правильно, но не вовремя).

По этой причине требования немного ослабляются. Добавляется новый пара- метр c > 0; система должна попытаться вернуть для каждого врача j список Lj, обладающий следующими свойствами.

(A*) Lj содержит не более c дней, не входящих в список L..

(B) (То же) По всему множеству списков L'l, ..., L'k в день i присутствуют ровнор врачей (для i = 1, 2, ..., n).

Опишите алгоритм с полиномиальным временем выполнения, реализующий измененную систему. Алгоритм получает числаp1, p2, ..., р , списки L1, ..., Lk и па- раметр c > 0, и делает одно из двух:

• Возвращает списки L'1, L'2, ..., L'k, удовлетворяющие свойствам (A*) и (B*); или

• Сообщает (обоснованно) о том, что множество списков L'1, ..., L'k, удовлетво- ряющее свойствам (A*) и (B*), не существует.

20. Ваши знакомые участвуют в крупномасштабном эксперименте по изучению атмосферы. Они хотят получить измерения по множеству S из n разных ат- мосферных характеристик (например, концентрации озона в разных местах); они располагают m зондами, которые запускаются для проведения измерений. Каждый зонд может провести не более двух измерений.

К сожалению, не все зонды способны измерять все условия, поэтому для каж- дого зонда i = 1, ..., m имеется множество S. характеристик, которые могут из- меряться этим зондом. Наконец, чтобы результаты были более надежными, они планируют провести каждое измерение минимум с k разных зондов. (Обратите внимание: один зонд не может измерять одну характеристику дважды.) Теперь нужно рассчитать, какие характеристики должны измеряться тем или иным зондом.

Пример. Допустим, k = 2, существуют n = 4 условий c1, c2, c3, c4, и имеются m = 4 зонда для измерения характеристик; при этом действуют ограничения S1 = S2 = {c1, c2, c3}, и S3 = S4 = {c1, c3, c4}. Один из возможных способов гарантиро- вать, что каждая характеристика будет измерена не менее k = 2 раз, выглядит так:

• зонд 1 измеряет условия c1, c2,

• зонд 2 измеряет условия c2, c3,

• зонд 3 измеряет условия c3, c4,

• зонд 4 измеряет условия c1, c4.

(a) Предложите алгоритм с полиномиальным временем, который получает входные данные экземпляра задачи (n характеристик, множества S. для каждого из m зондов, параметр к) и решает, возможно ли измерить каждую характеристику с к разных зондов при том, что каждый зонд может измерять не более двух характеристик.

(b) Вы показываете своим знакомым решение, вычисленное алгоритмом

из пункта (a) — но к вашему изумлению, слышите: «Не годится — одна из характеристик измеряется только зондами одного поставщика». Но до этого о поставщиках вы ничего не слышали; кажется, в задаче появился дополни- тельный нюанс, о котором забыли упомянуть..............

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

Допустим, зонд 1 выпущен первым поставщиком, зонды 2 и 3 — вторым, а зонд 4 — третьим. Тогда предыдущее решение уже не работает, так как оба измерения c3 выполнены зондами второго поставщика. С другой стороны, мы можем использовать зонды 1 и 2 для измерения характеристик c1, c2, а зон- ды 3 и 4 — для измерения характеристик c3, c4.

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

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

В настоящее время планшеты хаотично распределены по всему городку; план- шет l нахоится в зоне действия множества S' точек доступа. Будем считать, что каждый планшет находится в зоне действия по крайней мере одной точки доступа (так что множества S' не пусты); также предполагается, что в зоне действия каждой точки доступа p находится по крайней мере один планшет. Для нормальной работы программ беспроводной связи необходимо постарать- ся связать планшеты с точками доступа так, чтобы каждый планшет и каждая точка доступа были задействованы минимум в одном подключении. Тестовым множеством T будет называться совокупность упорядоченных пар вида (l, p) для планшета l и точки доступа p, обладающих следующими свойствами:

(i) Если (l, p) e T, то l находится в зоне действияp (то естьp 0. Множество чеков будет называться расчетом, если для каждого жильца i общая сумма чеков, полученных i, за вычетом общей суммы чеков, выписанных i, равна дисбалансу i. Наконец, все жильцы чувствуют, что для i было бы неправильно выписывать чек j, если i на самом деле не задолжал j, поэтому расчет называ- ется корректным, если при выписывании i чека j выполняется условие a.. > 0. Покажите, что для любого множества a.. всегда существует корректный расчет, при котором выписываются не более n-1 чека; для этого приведите алгоритм с полиномиальным временем для вычисления такого расчета.

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

Известны позиции нескольких базовых станций n, заданных точками b1, ..., bn на плоскости. Также известны позиции n сотовых телефонов, заданных точками p1, ..., pn. Наконец, задан еще один параметр — зона действия Δ > 0. Множество сотовых телефонов будет называться полностью связным, если каждый телефон можно связать с базовой станцией с выполнением следующих условий:

• Все телефоны подключены к разным базовым станциям, и

• Если телефон в точкеp подключен к базовой станции в точке b., то расстоя- ние по прямой между точками p и b. не превышает Δ.

Предположим, владелец сотового телефона в точке p1 отправляется в поездку, перемещаясь на z единиц расстояния на восток. При перемещении сотового телефона придется обновлять его подключение к базовой станции (возможно, несколько раз), чтобы множество телефонов оставалось полностью связным. Предложите алгоритм с полиномиальным временем, который будет принимать решение о том, возможно ли сохранять полную связность множества телефо- нов во время перемещения одного сотового телефона (предполагается, что все остальные телефоны при этом остаются неподвижными). Если это возможно, выведите последовательность подключений телефонов к базовым станциям, достаточную для сохранения полной связности; если это невозможно, выве- дите точку на пути перемещающегося телефона, в которой сохранение полной связности становится невозможным. Алгоритм должен выполняться за время O(n3), если это возможно.

Пример. Допустим, телефоны находятся в точках pl = (0, 0) и p2 = (2, 1); ба- зовые станции расположены в точках b1 = (1, 1) и b2 = (3,1); и Δ = 2. Телефон из точки p1 перемещается на восток на расстояние 4 единицы, завершая свое движение в точке (4, 0). В этом случае можно сохранить полную связность множества телефонов во время перемещения: сначала p1 подключается к b1, аp2 к b2, а затем во время перемещенияp1 переподключается к b2, аp2 к b1 (на- пример, при прохождении p1 точки (2, 0)).

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

Рассмотрим один из способов определения «справедливости». Допустим, люди обозначаются S = {pp ...,pk}. Общим обязательствомРj по множеству дней является ожидаемое количество раз, в течение которых Рj пришлось бы вести машину, если бы водитель выбирался случайным образом среди тех, кто едет на работу каждый день. А конкретнее, предположим, что план совместных поездок рассчитан на d дней, и в /-й день на работу едет подмножество людей S. Т S. Тогда приведенное выше определение обязательства Аj для р. может

г J

. В идеале хотелось бы потребовать, что

Рj ведет машину не более Δj раз; к сожалению, Δj может не быть целым числом. Планом совместных поездок назовем выбор водителя на каждый день — то есть последовательность , pt. prj, где р Έ S, а справедливым планом назовем

план, в котором каждый участник р выбирается водителем не более чем для |М дней.

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

(b) Предложите алгоритм для вычисления справедливого плана совместных поездок с временем выполнения, полиномиальным по k и d.

28. Группа студентов решила добавить новые функции в компьютерную систему подготовки учебных курсов для отработки аспектов планирования, в настоящее время не поддерживаемых программой. Работа начинается с модуля, который помогает планировать учебное время в начале семестра. Прототип работает по следующим правилам: прежде всего расписание остается постоянным, поэтому задачу планирования достаточно решить для одной недели. Администратор вводит набор неперекрывающихся одночасовых интервалов I1, I2, ..., Ik, в которые занятия могут проводиться ассистентами; итоговое расписание представляет собой подмножество (как правило, неполное) этих интервалов. Затем каждый ассистент вводит свое расписание на неделю с временем, в которое он будет свободен для проведения занятий.

Наконец, администратор указывает параметры а, b и с: каждому ассистенту было бы желательно выделить от а до b учебных часов в неделю, а количество учебных часов в неделю составляет ровно с.

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

Пример. Допустим, имеются пять временных интервалов:

IY = Понедельник 15-16; I2 = Вторник 13-14; I3 = Среда 10-11; I4 = Среда 15-16; I5 = Четверг 10-11.

Есть два ассистента; первый может работать в любое время в понедельник и среду во второй половине дня, а второй — в любое время во вторник, среду и четверг. (В общем случе правила доступности ассистентов могут быть более сложными, но мы не будем усложнять пример.) Наконец, каждому ассистенту должно быть выделено от a = 1 до b = 2 учебных часов, а общее количество учеб- ных часов за неделю должно быть равно c = 3.

В одном из возможных решений первому ассистенту выделяются учебные часы из интервала I1, а второму — часы из интервалов I2 и I5.

(a) Предложите алгоритм с полиномимальным временем, который полу- чает входные данные экземпляра этой задачи (интервалы, свободное время ассистентов и параметры a, b и c) и делает одно из двух:

• Стоит действительное расписание с указанием того, какому ассистенту выделяются те или иные интервалы, или

• Сообщает (обоснованно) о том, что требуемый способ распределения учебных часов не существует.

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

Администрация хочет иметь возможность задать новый параметр — «плот- ность» учебных часов для каждого дня недели: число d означает, что в задан- ный день недели i должно быть назначено не менее d. учебных часов. Допустим, в предыдущем примере добавляется ограничение, согласно кото- рому в среду и четверг должно быть проведено по крайней мере по одному учебному часу. В этом случае приведенное выше решение не работает; но существует возможное решение, в котором первому ассистенту выделяются учебные часы в интервале I1, а второму — часы в интервалах I3 и I5. (Другое решение — первому ассистенту выделяются часы в интервалах I1 и I4, а второ- му — в интервале I5.)

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

29. Ваши знакомые открыли небольшую компанию — в настоящее время они заня- ли под офис родительский гараж в Санта-Кларе. Сейчас компания занимается портированием своего программного обеспечения со старой на новую, более мощную платформу; сейчас она столкнулась со следующей проблемой. Имеется набор из n приложений {1, 2, ..., n}, работающих в старой системе; не- которые из этих приложений нужно портировать в новую систему. Ожидается, что портирование приложения i в новую систему принесет чистую (денежную) прибыль b. > 0. Приложения взаимодействуют друг с другом; если только одно из двух активно взаимодействующих приложений i и j было перенесено на но- вую платформу, компания несет потери Хj > 0.

Если бы все было настолько просто, ваши знакомые портировали бы все n при- ложений с получением общей прибыли ΕΛ К сожалению, возникает одна проблема...

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

Итак, какие же приложения следует портировать на новую платформу (если они есть, конечно)? Предложите алгоритм с полиномиальным временем для нахождения множества S !Ξ {2, 3, ..., n}, для которого сумма прибылей от пор- тирования приложений S на новую платформу с вычетом расходов будет мак- симальной.

30. Рассмотрим модификацию следующей задачи. В новой ситуации портировать- ся может любое приложение, но некоторые прибыли b при портировании на новую платформу оказываются отрицательными: если b < 0, то приложение i предпочтительно (на величину, определяемую i) оставить на старой платформе. Предоставьте алгоритм с полиномиальным временем для нахождения множе- ства S !Ξ {1, 2, ..., n}, для которого сумма прибылей от портирования приложений S на новую платформу с вычетом расходов будет максимальной.

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

Несколько дней назад поступила партия мониторов в больших коробках; мони- торы разные, поэтому и коробки имеют разные размеры. Работники компании с утра пытаются придумать, как бы их разместить для хранения. Разумеется, для экономии места часть коробок можно хранить внутри других коробок. Предположим, каждая коробка i представляет собой прямоугольный параллеле- пипед с длинами сторон (i1, i2, i3); каждая длина стороны лежит строго в диапа- зоне от 0,5 метра до 1 метра. С геометрической точки зрения размещение одной коробки внутри другой означает, что меньшую коробку можно повернуть так, чтобы она помещалась внутри большей коробки по каждому измерению. Фор- мально можно сказать, что коробка i с размерами (i1, i2, i3) помещается внутри коробкиj с размерами (j 1, j2, j3), если существует перестановка a, b, c измерений {1, 2, 3}, при которой ia < j1, ib < j2 и ic < j3. Конечно, вложение рекурсивно: если i находится внутри j, а j находится внутри к, то из всех трех коробок видна только коробка к. Мы будем называть вложением для множества из n коробок после- довательность операций, при которой коробка i размещается внутри коробки j; а если внутри i уже лежат другие коробки, они также оказываются внутри j. (Также обратите внимание на следующее: так как каждая из сторон i имеет дли- ну более 0,5 метра, а каждая из сторон j имеет длину меньше 1 метра, коробка i
занимает более половины размера по каждому измерению j, и после того, как коробка i окажется внутри j, ничего больше в j положить уже не удастся.) Ко- робка к во вложении называется видимой, если в результате последовательности операций она не вкладывается в другую коробку.

А теперь задача, с которой столкнулись в фирме Web-Exodus: так как место занимают только видимые коробки, как выбрать вложение, минимизирующее количество видимых коробок?

Предложите алгоритм с полиномиальным временем для решения этой задачи. Пример. Имеются три коробки с размерами (0,6, 0,6, 0,6), (0,75, 0,75, 0,75) и (0,9, 0,7, 0,7). Первую коробку можно положить как во вторую, так и в тре- тью; но в любом вложении как вторая, так и третья коротка будут видимы. Следовательно, минимально возможное количество видимых коробок равно 2, а придти к нему можно только одним способом — положив первую коробку во вторую.

32. Для заданного графа G = (F, Е) и натурального числа к можно определить отно- ■— для пар вершин G следующим образом: если х,v ^ V, мы говорим,

— у, если в G существуют к путей из х в у, взаимно непересекающихся по ребрам. Можно ли утверждать, что для всех G и всех к > 0 отношение ———* транзитивно? Иначе говоря, если х ———* у и у —■

33. Имеется направленный граф G = (V, E); предположим, для каждого узла v коли- чество ребер, входящих в v, равно количеству ребер, выходящих из v. Другими словами, для всех v

|{(u, v) : (u, v) е E}| = |{(v, w) : (v, w) е E}|

Пусть X, у — два узла G, и существуют к путей из x в у, взаимно непересекающих- ся по ребрам. В такой ситуации можно ли утверждать, что существуют к путей из у в x, взаимно непересекающихся по ребрам? Приведите доказательство или контрпример с объяснением.

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

Обратите внимание: речь идет об (a) относительно недорогих устройствах, которые (b) сбрасываются с самолета в (c) аварийную зону; с учетом всей ком- бинации факторов необходимо предусмотреть возможность обработки отказов на разумном количестве узлов.

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

(a) Имеется множество из n беспроводных устройств, позиции которых представлены парами координат (x, y). Разработайте алгоритм, который определяет, возможно ли выбрать резервное множество для каждого устройства (то есть к других устройств, каждое из которых удалено не бо- лее чем на d метров) с тем дополнительным свойством, что для некоторого параметра b никакое устройство не входит в резервное множества более чем b других устройств. Алгоритм должен выводить сами резервные множества, если их удастся найти.

(b) Представление о том, что для каждой пары устройств v и w существует четкая дихотомия между понятиями «в зоне действия» и «вне зоны дей- ствия» — всего лишь упрощенная абстракция. В более точном представ- лении существует функция снижениям мощности f( ), которая для пары устройств на расстоянии δ определяет мощность сигнала f(δ) на беспровод- ном подключении между этими устройствами. (Предполагается, что f (δ) убывает с возрастанием δ).

Это представление хотелось бы встроить в концепцию резервных множеств: среди к устройств резервного множества v должно быть как минимум одно, с которым возможна связь с очень высокой мощностью сигнала; по крайней мере одно устройство, доступное с умеренно высокой мощностью сигнала, и т. д. А конкретнее, имеются такие значенияp1 >p2 > ... >pk, что если резервное множество v состоит из устройств на расстояниях d1 < d2 < ... < dk, должно вы- полняться условие f (d.) >р. для всех j.

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

35. Вы разрабатываете интерактивную программу сегментации изображений, которая работает следующим образом: в исходном состоянии используется конфигурация, описанная в разделе 7.10, с n пикселами, множеством соседних пар, параметрами {a.}, {b.} и р}. Относительно этого экземпляра делаются два предположения. Во-первых, каждый из параметров {a.}, {b.} и {рявляется неотрицательным целым числом в диапазоне от 0 до d для некоторого чис- ла d. Во-вторых, предполагается, что соседские отношения между пикселами обладают тем свойством, что каждый пиксел является соседом не более чем четырех других пикселов (в полученном графе из каждого узла выходит не более четырех ребер).

Сначала выполняется исходная сегментация (A0, B0), максимизирующая вели- чину q(A0, B0). В результате исходной сегментации некоторые пикселы могут быть отнесены к фону, хотя пользователь знает, что они должны принадлежать переднему плану. Увидев эту сегментацию на экране, пользователь может щел- кнуть мышью на конкретном пикселе v1, переводя его на передний план. Но программа не ограничивается простым переносом пиксела: вместо этого она должна вычислять сегментацию (Av Bl), максимизирующую величину q(A1, Bl) с учетом того, что v1 принадлежит переднему плану. (Как это может пригодиться на практике? Допустим, при сегментации фотографии группы людей кто-то держит сумку, которая была ошибочно отнесена к фону. Если щелкнуть на од- ном пикселе, принадлежащем сумке, и пересчитать оптимальную сегментацию с учетом нового условия, вся сумка станет частью переднего плана).

Система должна дать возможность пользователю провести серию таких щелч- ков vv v2, ..., v^, после щелчка vt система проводит сегментацию (A., B), мак- симизирующую величину q(A, B) в соответствии с условием, что v1, v2, ..., vt находятся на переднем плане.

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

(Примечание: Упражнение с решением 1 из этой главы служит полезным при- митивом для этого упражнения. Кроме того, симметричная операция перевода пиксела в фон выполняется аналогично, но здесь вам это делать не нужно.)

36. Рассмотрим еще одну разновидность задачи сегментации изображений из раз- дела 7.10. Мы разработаем решение задачи разметки изображения, в которой каждый пиксел помечается приблизительной оценкой расстояния от него до камеры (вместо простой разметки «фон/передний план», использованной в тексте). Допустимые значения меток для каждого пиксела равны 0, 1, 2, ..., M для некоторого целого M.

Пусть G = (V, E) — граф, узлы которого соответствуют пикселам, а ребра обо- значают соседние пары пикселов. Разметкой пикселов называется разбиение V на множестваA0, A1, ..., AM, гдеAk — множество пикселов, помечаемых расстояни- ем к для к = 0, ..., M. Мы займемся поиском разметки с минимальной стоимостью; стоимость определяется двумя факторами. По аналогии с задачей сегментации «передний план/фон», имеется стоимость назначения: для каждого пиксела i и метки к стоимость a.k определяет стоимость назначения метки к пикселу i. Затем, если двум соседним пикселам (i, j) E назначаются разные метки,

также действует штраф за разделение. В разделе 7.10 использовался штраф за разделение рj в текущей задаче штраф за разделение также зависит от того, на какое расстояние удаляются пикселы: он пропорционален разности значений двух меток. Таким образом, общая стоимость q' разметки определяется следу- ющим образом:

\f

ч\\..... +∑ ∑ tf-⅛v

l-Ф⅛il k h(v) > h. Изменением меток про- пусков называется процесс изменения высот всех узлов в A так, чтобы они были равны n. Докажите, что алгоритм проталкивания предпотока с интер- вальным изменением меток является действительным алгоритмом макси- мального потока. Заметьте, что единственный новый факт, который нужно доказать — что интервальное изменение меток сохраняет приведенный выше инвариант: h(v) < h(w) + 1 для всех ребер (v, w) в остаточном графе.

(c) В разделе 7.4 мы доказали, что h(v) < 2n - 1 на протяжении алгоритма. В этой модификации выполняется условие h(v) < n. Идея заключается в том, что мы «замораживаем» все узлы при достижении высоты n; другими слова- ми, узлы на высоте n перестают считаться активными, и поэтому не использу- ются для операций push и relabel. В этом случае в конце алгоритма мы имеем функцию предпотока и высоты, которая удовлетворяет приведенному выше инварианту, так что весь избыточный поток находится на высоте n. Пусть B — множество узлов v, для которых существует путь от v к t в остаточном графе текущего предпотока, а A = V — B. Докажите, что в конце алгоритма (A, B) является разрезом s-t с минимальной пропускной способностью.

(d) Алгоритм в части (c) вычисляет минимальный разрез s-t, но не находит максимальный поток (так как завершается на предпотоке, содержащем из- быточные потоки). Предложите алгоритм, который получает предпоток f в конце алгоритма из части (c), и преобразует его в максимальный поток за время, не превышающее O(mn). (Подсказка: рассмотрите узлы с избыточным потоком, и попробуйте отправить избыточный поток обратно к s, используя только те ребра, по которым поток поступил.)

48. В разделе 7.4 мы рассмотрели алгоритм проталкивания предпотока, а также обсудили одно конкретное правило выбора вершин. Сейчас будет рассмотрено другое правило выбора. Мы также рассмотрим варианты алгоритма с ранним завершением (и наайдем разрез, близкий к минимально возможному).

(a) Пусть f — любой предпоток. Так как f не обязательно является действи- тельным потоком, может оказаться, что величина f out(s) намного выше величины максимального потока в G. Покажите, что f m(t) является нижней границей для величины максимального потока.

(b)


Рассмотрим предпоток f и совместимую разметку h. Вспомните, что множества A = {v : существует путь s—v в остаточном графе G } и B = V — A определяют разрез s-t для любого предпотокаf имеющего совместимую разметку h. Покажите, что пропускная способность разреза (А, В) равна

Объединение (a) и (b) позволяет алгоритму завершиться на ранней стадии и вернуть (A, B) как разрез с «приближенно-минимальной» пропускной способностью в предположении, что значение c(A, B) - fn(t) достаточно мало. Далее мы рассмотрим реализацию, которая стремится сократить это значение, пытаясь протолкнуть поток из узлов с большим количеством из- быточного потока.

(c) Версия алгоритма проталкивания предпотока с масштабированием поддерживает параметр масштабирования Δ. Изначально Δ присваивается большая степень 2. На каждом шаге алгоритм выбирает узел, у которого избыточный поток не менее Δ, при минимально возможной высоте. Если узлов (кроме t) с избыточным потоком не менее Δ не осталось, алгоритм делит Δ на 2 и продолжает. Обратите внимание: этот алгоритм является действительной реализацией обобщенного алгоритма проталкивания пред- потока. Алгоритм выполняется по фазам. Одна фаза продолжается до тех пор, пока значение Δ остается неизменным. В начале алгоритма Δ имеет максимальную пропускную способность, а при его завершении Δ = 1. Сле- довательно, в ходе выполнения количество фаз масштабирования не пре- вышает О(log C). Покажите, как реализовать эту разновидность алгоритма так, чтобы время выполнения было ограничено O(mn + n log C + K), если алгоритм использует K ненасыщающих операций push.

(d) Покажите, что количество ненасыщающих операций push в предыдущем

алгоритме не превышает O(n2 log C). Вспомните, что количество фаз масшта- бирования имеет границу О(log C). Чтобы определить границу количества ненасыщающих операций push в одной фазе масштабирования, рассмотрите потенциальную функцию ф = ^ ,. (v)/Δ ∙ Как ненасыщающая опера-

ция push влияет на ф? Какие операции могут привести к увеличениюФ?

49. Рассмотрим задачу о распределении: имеется множество из n станций, способ- ных выполнять некую работу, и множество из к заявок на обслуживание (напри- мер, станции — вышки сотовой связи, а запросы — сотовые телефоны). Каждый запрос может обслуживаться заданным множеством станций. Задача в таком виде может быть представлена двудольным графом G: одна сторона для станций, другая для клиентов, и клиент х соединяется со станцией у ребром (x, y), если клиент х может обслуживаться станцией у. Будем считать, что каждая станция способна обслуживать не более одного клиента. Используя метод вычисления максимального потока, можно решить, возможно или нет обслужить всех кли- ентов, или же получить распределение подмножества клиентов по станциям, максимизирующее количество обслуженных клиентов.

В этой задаче рассматривается разновидность задачи с дополнительным услож- нением: клиенты предлагают разные суммы денег за обслуживание. Пусть U — множество клиентов, а клиент х U готов заплатить yr > 0. Требуется найти подмножество Л'с [/.максимизирующее ^ χντ — такое, что существует распределение клиентов из X между станциями.

Рассмотрим следующий жадный метод: клиенты обрабатываются в порядке убывания «ценности» (с произвольной разбивкой «ничьих»). При рассмотре- нии клиента x алгоритм либо «обещает» обслуживание х, либо отвергает x по следующему жадному правилу: х добавляется в множество Л' в том и только в том случае, если существует распределение Хu{*[ по станциям; в против- ном случае х отвергается. Помните, что отвергнутые клиенты не будут рас- сматриваться позднее. (Если уж приходится отвергнуть высокооплачиваемого клиента, по крайней мере ему можно сказать об этом сразу.) При этом распре- деление принятых клиентов по обслуживающим станциям не осуществляется по жадному принципу: распределение фиксируется только после фиксации множества принятых клиентов. Приведет ли этот жадный подход к оптималь- ному множеству клиентов? Докажите, что это так, или приведите контрпример.

50. Рассмотрим следующую задачу планирования. Имеются m машин, каждая из которых может обрабатывать задания. Требуется распределить задания между машинами (каждое задание должно быть назначено ровно одной машине) и упо- рядочить задания на машинах так, чтобы минимизировать функцию стоимости. Машины работают с разной скоростью, но потребности в вычислительных ресурсах у всех заданий одинаковы. В более формальном выражении с каждой машиной i связывается параметр f,, и выполнение каждого задания потребует времени f , если оно будет назначено на машину i.

Количество заданий равно n; все задания требуют одинаковых затрат вычис- лительных ресурсов, но имеют разные уровни срочности. Для каждого задания j определена функция стоимости c(t), которая определяет стоимость выпол- нения задания j за время t. Предполагается, что стоимости неотрицательны и монотонны по t.

Расписание представляет собой распределение заданий по машинам, и для каждой машины оно определяет порядок выполнения заданий. Задание, назна- ченное на машину i первым, завершается за время , второе задание — за время f, и т. д. Пусть для расписания S время завершения задания / в этом расписании обозначается tS(j). Стоимость такого расписания равна Предложите алгоритм с полиномиальным временем для нахождения расписа- ния с минимальной стоимостью.

51. Вашим друзьям надоела игра «Шесть шагов до Кевина Бэйкона»[13] (в конце концов, разве это не обычный поиск в ширину?), и они решили изобрести не- что более содержательное с алгоритмической точки зрения. Вот как работает их система.

Все начинается с множества X из n актрис, множества Y из n актеров, и двух игроков P0 и P1. Игрок P0 называет актрису x1 X; игрок P1 называет актераy1, снимавшегося в одном фильме с хр игрок P0 называет актрису x2, снимавшуюся в одном фильме с y1, и т. д. Таким образом, P0 и P1 совместно строят последо- вательность x1, y1, x2, y2, ..., в которой каждый актер/актриса снимается в одном
фильме со своим непосредственным предшественником. Игрок P. (i = 0,1) про- игрывает, если в свой ход он не может назвать ни один элемент своего множе- ства, не называвшийся ранее.

Допустим, имеется конкретная пара таких множеств X и Y, с полной инфор- мацией: кто, с кем, в каких фильмах снимался. Стратегией для игрока P в нашей задаче называется алгоритм, который получает текущую последовательность x1, y1, x2, y2, ... и генерирует действительный следующий ход для P (предполагается, что сейчас ход P ). Предложите алгоритм с полиномиальным временем, который решает, какой из двух игроков может обеспечить себе победу в конкретном экзем- пляре игры.

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

Еще по теме Упражнение с решением 2:

  1. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  2. РЕШЕНИЕ
  3. РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
  4. ПРИНЯТИЕ РЕШЕНИЙ
  5. РЕШЕНИЯ КСУ
  6. Не избегайте принятия решений
  7. ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
  8. ЗАДАЧА: РЕШЕНИЕ
  9. Принять решение
  10. Управленческие решения
  11. Решение проблем
  12. КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.
  13. Убеждения и решения
  14. Убеждения и решения
  15. НАЙДИТЕ РЕШЕНИЕ
  16. НАЧНИТЕ С ПРИНЯТИЯ РЕШЕНИЯ
  17. Получение информации и принятие решений
  18. Решение измениться