<<
>>

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

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

В главе 4 было показано, что алгоритм не всегда строит множество максималь- ного размера с неперекрывающимися интервалами. Однако, как выясняется, он предоставляет интересную гарантию аппроксимации. Если 5* — максимальный размер множества неперекрывающихся интервалов, а 5 — размер множества, про- изведенного этим алгоритмом, то s > L*^ (то есть алгоритм выбора кратчайшего

интервала является 2-аппроксимацией).

Докажите этот факт.

Решение

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

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

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

Интуитивно кажется, что единственная ситуация, в которой это может произойти, — если один из интервалов i в оптимальном решении полностью укладывается в один из интервалов j, выбираемых алгоритмом выбора кратчайшего пути. Однако это противоречит поведению алгоритма: почему он не выбрал более короткий интер- вал i, вложенный в j?

Посмотрим, удастся ли точно сформулировать этот аргумент. Пусть A — мно- жество интервалов, выбираемых алгоритмом, а O — оптимальное множество интервалов. Для каждого интервала j A рассмотрим множество интервалов в O, с которыми он конфликтует.

(11.41) Каждый интервал j A конфликтует не более чем с двумя интервала- ми в O.

Доказательство. Действуя от обратного, предположим, что в j 0. Требуется найти множество представителей Н Т А с минимально возможным общим весом элементов Н — то есть ^ g⅛, . (Как и в упраж- нении 5 главы 8, множеством представителей называется такое множество H, что H ∩ B. не пусто для всех i.) Обозначим b = maxjBj максимальный размер множеств B1, B2, ..., Bm. Предложите аппроксимирующий алгоритм с полино- миальным временем для нахождения множества представителей, общий вес которого не более чем в b раз превышает минимально возможный.

5. Вы работаете на фирму, клиенты которой ежедневно предоставляют задания для обработки. Каждое задание характеризуется временем обработки t, из- вестным при поступлении задания. Компания располагает парком из 10 машин, и каждое задание может быть выполнено на любой машине.

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

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

месяца, и период обработки ни разу не превысил среднюю нагрузку более чем на 20 %.

Чтобы понять, почему «удвоенное» поведение не проявляется в работе, вы собираете информацию о типичных заданиях и нагрузках. Как выясняется, размеры заданий лежат в диапазоне от 1 до 50, то есть 1 < i. < 50 для всех за- даний У; а ежедневная общая нагрузка ^ t, достаточно высока: она не бывает ниже 3000.

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

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

Все эти проблемы продемонстрированы в следующей базовой модели. До- пустим, имеется система, состоящая из m медленных и k быстрых машин. Бы- стрые машины могут выполнять за единицу времени вдвое больше работы, чем медленные. Имеется множество из n заданий; выполнение задания У занимает

время t. на медленной машине и время 1 f на быстрой машине.

1 2 '

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

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

Вы консультируете коммерческий сайт, который ежедневно получает большое количество посещений. Каждому посетителю i, где i {1,2, ..., n}, сайт назначает значение vi, представляющее ожидаемый доход, который может быть получен о данного клиента.

Каждому посетителю i при входе на сайт показывается одна из m возможных реклам A1, A2, ..., Am. Нужно выбрать по одной рекламе для каждого посетителя, чтобы каждая реклама была показана в сумме множеству клиентов с достаточно большим общим весом. Таким образом, для заданного выбора одной рекламы на посетителя охват этой выборки определяется как минимум по 1, 2, ..., m общего веса всех клиентов, которым была показана реклама A..

Пример. Допустим, имеются шесть посетителей со значениями 3, 4, 12, 2, 4, 6 и m = 3 реклам. Тогда в этом экземпляре задачи можно обеспечить охват 9, по- казав рекламу A1 посетителям 1, 2, 4, рекламу A2 — посетителю 3 и рекламу A3 — посетителям 5 и 6.

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

(a) Предоставьте алгоритм с полиномиальным временем, аппроксимиру- ющий максимальный охват в пределах множителя 2. Иначе говоря, если максимальный охват равен s, то ваш алгоритм должен выдавать подборку ре- кламы с охватом не менее s/2. При разработке алгоритма можно считать, что в ней нет посетителей, значение которых значительно превышает среднее;

а именно: если обозначить ν' = ^ общее значение по всем посетителям, можно считать, что нет посетителя со значением, превышающим v/(2т).

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

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

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

Немного поворчав, ваши друзья выдвигают альтернативную идею. Допустим, они могут написать маленький фрагмент кода, который получает описание

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

Ваших друзей интересует: всегда ли это возможно? Они предлагают следую- щую гипотезу.

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

Решите, истинна ли эта гипотеза или ложна; приведите доказательство или контрпример.

9. Рассмотрим следующую максимизирующую версию задачи о трехмерном со- четании.

Для заданных непересекающихся множеств X, Y и Z, а также множе- ства T !Ξ X X Y X Z упорядоченных триплетов подмножество M !Ξ T называется трехмерным сочетанием, если каждый элемент X U Y U Z содержится не более чем в одном из этих триплетов. В максимальной задаче о трехмерном сочетании требуется найти трехмерное сочетание M с максимальным размером. (Размер сочетания, как обычно, определяется количеством содержащихся в нем трипле- тов. Если хотите, считайте, что | X | = | Y | = | Z |.)

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

10. Предположим, имеется решетчатый граф G с размерами n χ n (рис. 11.13).

Рис. 11.13. Решетчатый граф

С каждым узлом v связывается вес w(v) — неотрицательное целое число. Счи- тайте, что веса всех узлов различны. Требуется найти такое независимое множе- ство S узлов решетки, чтобы сумма весов узлов S была как можно выше. (Далее сумма весов узлов множества S будет называться его общим весом.) Рассмотрим следующий жадный алгоритм для решения этой задачи.

Жадный алгоритм «выбора узла с наибольшим весом»: Начать с пустого множества S Пока в G остаются узлы

Выберите узел v с максимальным весом Добавить v в S

Удалить v и его соседей из G Конец Пока Вернуть S

(a) Пусть S — независимое множество, возвращаемое жадным алгоритмом выбора узла с наибольшим весом, а T — любое независимое множество в G. Покажите, что для каждого узла v T либо v S, либо существует такой узел v’ S, что w(v) < w(v) и (v, v') является ребром G.

(b) Покажите, что жадный алгоритм выбора узла с наибольшим весом воз-

вращает независимое множество с общим весом не менее

ного общего веса любого независимого множества в решетчатом графе G.

11. Вспомните, что в задаче о рюкзаке имеются n предметов, каждый из которых обладает весом w и значением v.. Также определяется предельный вес W; задача состоит в нахождении множества предметов S с наибольшим возможным значе- нием при условии, что общий вес не превышает W, то есть < W. Один из

подходов к рассмотрению аппроксимирующих алгоритмов может быть таким:

если существует подмножество О, общий вес которого равен i⅞ < W, а общее

значение У)f 0Vt = V для некоторого V, то наш аппроксимирующий алгоритм найдет множество А с общим весом < W и общим значением не менее

Таким образом, алгоритм аппроксимирует лучшее значение,

удерживая веса строго ниже W. (Конечно, возвращение множества O всегда является действительным решением, но так как задача является ЖР-полной, не стоит рассчитывать, что нам всегда удастся найти само множество O; граница аппроксимации 1 + е означает, что другие множестваA, обладающие чуть мень- шим значением, также могут быть действительными ответами.)

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

Допустим, как и прежде, даны n предметов с весами и значениями, а также параметрами W и V; вам сообщают, что существует подмножество О, общий

вес которого равен Е i}Wt < tУ, а общее значение равно Е ,\) — У для не- которого V. Для заданного фиксированного е > 0 разработайте алгоритм с по- линомиальным временем, который находит подмножество таких элементов А,

что EЛV$0 + e) и У,^v,>V

Другими словами, подмножество A должно достигать общего значения, не меньшего заданной границы V, но допускается превышение границы веса W на коэффициент 1 + е.

Пример. Допустим, имеются четыре предмета со следующими весами и значе- ниями:

(wj, Vj) = (5, 3), (w2, v2) = (4, 6) (w3, V3) = (1, 4), (W4, V4) = (6, 11)

Также заданы границы W = 10 и V = 13 (так как подмножество, состоящее из первых трех элементов, имеет общий вес 10 и значение 13). Наконец, е = 0,1. Это означает, что нужно найти (при помощи аппроксимирующего алгоритма) подмножество с весом не более (1 + 0,1) * 10 = 11 и значением не менее 13. Одним из действительных решений станет подмножество, состоящее из перво- го и четвертого предметов, со значением 14 > 13. (Обратите внимание: в этом случае достигается значение строго большее V, так как допускается легкое пере- полнение рюкзака.)

12. Рассмотрим следующую задачу. Имеется множество U из n узлов, которые могут рассматриваться как пользователи (например, пользователи, обращаю- щиеся к веб-серверу или иному виду сервиса). Серверы должны размещаться в разных местах. Предположим, имеется множество из S возможных мест, подходящих для размещения серверов. Для каждого места 5 S определяется плата за размещение установки сервера в этом месте f > 0. Ваша цель — обе- спечить аппроксимированную минимизацию стоимости при предоставлении сервиса каждому пользователю. Пока что все очень похоже на задачу о покры- тии множества: места 5 соответствуют множествам, вес множества 5 равен f, требуется выбрать совокупность множеств, покрывающую всех пользователей. Тем не менее существует один нюанс: пользователи и ^ Uмогут обслуживать- ся из разных мест, но за обслуживание пользователя и из места 5 взимается стоимость d . При очень высоком значении d обслуживание пользователя и с сервера в месте 5 нежелательно; в общем случае затраты dи5 должны поощрять обслуживание пользователей с «ближних» серверов, насколько это возможно. Итак, вопрос, который мы назовем «задачей о размещении серверов»: для за- данных множеств U и S, а также цен ∕и d требуется выбрать подмножество

мест А !Ξ S для размещения серверов (со стоимостью E,t ⅜/, ) и закрепить за каждым пользователем активный сервер, на котором его обслуживание обой-

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

дется дешевле всего: miп i/ Целью является минимизация общих затрат У~ ,Х+2ц. < шіq, j ⅛∙ Предложите Я^(w)-аппроксимацию для этой задачи. (Если все значения ds равны 0 или бесконечны, то задача в точности соответ- ствует задаче покрытия множеств:f — стоимость множества s, а ds = 0, если узел и принадлежит множеству s, и бесконечность в противном случае).

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

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

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