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

Вас приглашают для проведения консультаций в компанию Clones ‘R' Us (CRU), специализирующуюся на передовых исследованиях в области биотехнологий. Поначалу вы не уверены в том, что ваш опыт решения алгоритмических задач при- годится в такой области, но вскоре вы общаетесь с двумя подозрительно похожими инженерами, ломающими голову над нетривиальной задачей.

Эта задача основана на конкатенации последовательностей генетических мате- риалов. Если X и Y — строки с фиксированным алфавитом S, то запись XY обозна- чает строку, полученную в результате их конкатенации: содержимое X, за которым следует содержимое Y. Ученые выявили целевую последовательность A генетиче- ского материала, состоящую из m символов, и они хотят построить последователь- ность, как можно более близкую к A. Для этого была сформирована библиотека С, состоящая из к (более коротких) последовательностей, длина каждой из которых не превышает n. Ученые могут легко воспроизвести любую последовательность, состоящую из сцепленных копий строк из С (с возможными повторениями).

Конкатенацией по С называется любая последовательность в форме B1B2... B , в которой каждый элемент B. принадлежит множеству С. (Еще раз: повторения разрешены, так что B. и B. могут соответствовать одной строке в С для разных значений i и j). Требуется найти конкатенацию по {B.}, для которой стоимость вы- равнивания последовательностей будет минимальной. (Для вычисления стоимо- сти выравнивания последовательностей можно считать, что вам даны стоимости разрыва δ и несоответствия α для каждой парыр, q S.)

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

Решение

Эта задача отдаленно напоминает сегментированную задачу наименьших квадра- тов: имеется длинная последовательность «данных» (строкаA), которую требуется «аппроксимировать» более короткими сегментами (строки из С).

Если бы мы хотели развить эту аналогию, решение можно было бы искать следующим образом. Пусть B = B B2... B — конкатенация по С, которая как можно лучше совмещается с заданной строкой A. (Иначе говоря, B является оптимальным решением для входного экземпляра.) Рассмотрим оптимальное выравнивание M строки A с B; t — первая позиция в A, сопоставленная с некоторым символом в B , а A — подстрока A от позиции t до конца. (Иллюстрация для = 3 приведена на рис. 6.27.) В этом оптимальном выравниванииMподстрока A оптимально вырав- нивается с B ; действительно, если бы существовал лучший способ выравнивания A с B , мы могли бы подставить его в ту часть M, в которой A выравнивается с B , и улучшить общее выравнивание A с B.

Рис. 6.27. В оптимальной конкатенации строк для выравнивания с A существует завершающая строка (B3 на схеме), выравниваемая с подстрокой A (A3 на схеме), которая проходит от позиции t до конца


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

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

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

Итак, подготовим все необходимое для того, чтобы сделать возможным поиск A. Пусть A[x : у] — подстрока A, состоящая из символов от позиции x до позиции у включительно, а c(x, у) — стоимость оптимального выравнивания A[x : у] с любой строкой из С (иначе говоря, мы перебираем все строки из L и находим ту, которая лучше всего выравнивается с A[x : у]). Пусть OPTO') обозначает стоимость вырав- нивания оптимального решения для строки A[1 :j].

Из приведенных выше рассуждений следует, что оптимальное решение для A[1 :j] складывается из выявления итоговой «границы сегмента» t 1, и OPT(0) = 0.

Полный алгоритм состоит из вычисления величин c(t, j) для t < j и последую- щего построения значений OPT( j) в порядке возрастания j. Эти значения хранятся в массиве M.

Присвоить M[0] = 0 Для всех пар 1 < t < j < m

Вычислить стоимость c(t,j) следующим образом:

Для каждой строки B e L

Вычислить оптимальное выравнивание B с A[t : j]

Конец цикла

Выбрать B с лучшим выравниванием и использовать стоимость этого выравнивания как c(t, j)

Конец цикла

For j = 1, 2............... n

Использовать рекуррентное отношение (6.37) для вычисления M[j]

Конец For Вернуть M[n]

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

Рассмотрим время выполнения алгоритма. Во-первых, всего требуется вы- числить O(m2) значений c(t, j). Для каждого из них нужно проверить каждую из к строк B С и вычислить оптимальное выравнивание B с A[t :j] за вре- мя O(n( j - t)) = O(mn). Следовательно, общее время вычисления всех значений c(tj) составляет O(km3n).

Этот фактор доминирует над временем вычисления всех значений OPT: вычисле- ние OPT(j) использует рекуррентное отношение в (6.37), а это требует времени O(m) для вычисления минимума. Суммируя по всем вариантам j = 1, 2, ..., m, мы получаем время O(m2) для этой части алгоритма.

Упражнения

1. Имеется ненаправленный граф с n узлами G = (V, E). Напомним, что подмно- жество узлов называется независимым множеством, если никакие два узла не соединяются ребром. В общем виде задача нахождения большого независимого множества сложна, но при достаточно «простом» графе она имеет эффективное решение.

Назовем граф G = (V, E) путевым графом, если его узлы могут быть записаны в виде v1, v2, ..., vn, причем v. и v. соединяются ребром в том и только в том случае, если i и j различаются ровно на 1. С каждым узлом v. связывается положитель- ный целый вес w..

Для примера рассмотрим путевой граф из пяти узлов на рис. 6.28. Веса обозна- чены числами внутри узлов.

Рис. 6.28. Путевой граф с весами, обозначенными на узлах.

Максимальный вес независимого множества равен 14


Целью этого упражнения является решение следующей задачи:

Найдите в путевом графе G независимое множество с максимальным общим весом.

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

Жадный алгоритм «приоритетного выбора максимального веса»

Начать с S, равного пустому множеству Пока в G остаются узлы

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

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

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

Присвоить Sj множество всех v , для которых i нечетно Присвоить S2 множество всех v , для которых i четно (обратите внимание: S2 и S2 являются независимыми множествами)

Определить, какое из множеств S2 или S2 имеет больший общий вес, и вернуть его.

(c) Предложите алгоритм, который получает путевой граф G из n узлов с весами и возвращает независимое множество с максимальным общим весом. Время выполнения должно быть полиномиальным по n независимо от значений весов.

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

При выборе некритичного задания в неделю i вы получаете доход £. > 0 долла- ров; при выборе критичного задания доход составит h > 0 долларов. Проблема в том, что группа может взять критичное задание в неделю i только в том случае, если в неделю i - 1 она не выполняла вообще никакого задания (критичного или некритичного); для такой ответственной работы необходима целая неделя подготовки. С другой стороны, если группа выполняла задание (любого типа) в неделю i - 1, ничто не помешает ей выполнить некритичное задание в неделю i. Итак, для заданной последовательности из n недель план задается выбором «некритичное задание», «критичное задание» или «нет задания» для каждой из n недель с тем свойством, что при выборе «критичное задание» для недели i > 1 в неделе i - 1 должно быть выбрано задание i - 1. (Допускается выбор критичного задания в неделю 1.) Значение плана определяется следующим об- разом: для каждого i значение увеличивается на l, если в неделю i было выбрано «некритичное задание», и значение увеличивается на hi, если в неделю i было выбрано «критичное задание». (Если в неделю i не было выбрано никакое за- дание, значение увеличивается на 0.)

Задача. Для заданных множеств значений iv £2, ..., in и h1, h2, ..., hn найти план с максимальным значением (такой план будет называться оптимальным). Пример. Допустим, n = 4, а значения l. и h. задаются следующей таблицей. В этом случае план с максимальным значением достигается выбором «нет задания» в неделю 1, выбором критичного задания в неделю 2 и выбором некритичного задания в недели 3 и 4. Значение такого плана составит 0 + 50 + 10 + 10 = 70.


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

Для итераций с i = 1 до n Если h. + 1 > l + L·.

i i i+1

Вывести "Не брать задание в неделю i"

Вывести "Взять критичное задание в неделю i + 1"

Продолжить с итерации i + 2 Иначе

Вывести "Взять некритичное задание в неделю i"

Продолжить с итерации i+1 Конец Если Конец

Чтобы избежать проблем с выходом за границу массива, определим h. = l = 0 при i > n.

Также приведите правильный алгоритм и укажите, какой результат находит приведенный алгоритм.

(b) Предложите эффективный алгоритм, который получает значения l1, l2, ..., ln и h1, h2, ..., hn и возвращает значение оптимального плана.

3. Имеется направленный граф G = (V, E) с узлами v1, ..., vn. Граф G называется упорядоченным, если он обладает следующими свойствами:

(i) каждое ребро идет от узла с меньшим индексом к узлу с большим индек- сом. Иначе говоря, каждое направленное ребро имеет форму (v., v) c i < j;

(ii) из каждого узла, кроме vn, выходит минимум одно ребро, то есть для каждого узла v. с i = 1, 2, ..., n - 1 существует минимум одно ребро в фор- ме (v., v).

Длина пути определяется количеством ребер, входящих в этот путь. В этом упражнении решается следующая задача (пример представлен на рис. 6.29):

Рис. 6.29. Правильный ответ для этого упорядоченного графа равен 3: самый длинный путь из v1 в vn состоит из трех ребер (v1 ,v2),(v2,v4) и (v4,v5)


Для заданного графа G найдите длину самого длинного пути, который начина- ется в v и заканчивается в v .

1 n

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

Присвоить w = v1 Присвоить L = 0

Пока существует ребро, выходящее из узла w Выбрать ребро (w,vj)

с минимально возможным значением j Присвоить w = vj Увеличить L на 1 Конец Пока

Вернуть L как длину самого длинного пути

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

(b) Предложите эффективный алгоритм, который получает упорядоченный граф G и возвращает длину самого длинного пути, который начинается в v1 и заканчивается в vn. (Еще раз: под длиной понимается количество ребер в пути.)

4. Вы руководите небольшой фирмой — вы, двое сотрудников и арендованная тех- ника. Ваши клиенты распределены между Восточным и Западным побережьем. В каждом месяце вы можете вести дела из офиса в Нью-Йорке (NY) или из офиса в Сан-Франциско (SF). В месяце i текущие издержки составляют N, если дела ведутся из Нью-Йорка, или S, если дела ведутся из Сан-Франциско (величина зависит от потребностей клиентов в этом месяце).

Но если в месяце i вы ведете дела из одного города, а в месяце i + 1 — из другого города, затраты на перемещение составляют фиксированную величину M.

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

Задача. Для заданной стоимости перемещения M и последовательностей те- кущих издержек N1, ..., Nn и S1, ..., Sn найдите план с минимальной стоимостью (назовем такой план оптимальным).

Пример. Допустим, n = 4, M = 10, а текущие издержки задаются следующей таблицей.

В этом случае план с минимальной стоимостью будет представлять собой по- следовательность [NY, NY, SF, SF] с общей стоимостью 1 + 3 + 2 + 4 + 10 = 20 (последнее слагаемое 10 появляется из-за однократного перемещения).

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

For i = 1 To n Если N < S.

Вывести "NY в месяце i"

Иначе

Вывести "SF в месяце i"

Конец

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

(b) Приведите пример, в котором каждый оптимальный план требует не менее трех перемещений между городами.

Кратко объясните, почему ваш пример обладает таким свойством.

(c) Предложите эффективный алгоритм, который получает значения n, M и последовательности текущих издержек Nl, ..., Nn и Sl, ..., Sn и возвращает стоимость оптимального плана.

5. Как вам, вероятно, известно, в некоторых языках (включая китайский и япон- ский) слова не разделяются пробелами. По этой причине программы, работаю- щие с текстом, написанным на этих языках, должны решать проблему сегмен- тации слов, то есть вычисления вероятных границ между смежными словами в тексте. Представьте, что английский текст записывается без пробелов; вы получаете строку вида «meetateight» и решаете, что лучшим разбиением будет «meet at eight» (а не «me et at eight», «meet ateight» или какой-нибудь менее вероятный вариант). Как автоматизировать этот процесс?

Простой, но достаточно эффективный метод основан на поиске сегментации, которая максимизирует накапливаемое «качество» отдельных составляющих слов. Допустим, у вас есть «черный ящик», который для любой цепочки букв x = xx2 ... xk возвращает число quality(x). Это число может быть как положительным, так и отрицательным; большие числа соответствуют более вероятным англий- ским словам. (Значение quality("me") будет положительным, тогда как значение quality("ght") будет отрицательным).

Для длинной цепочки букв у = yy2... yn сегментация у представляет собой вари- ант разбиения последовательности на непрерывные блоки букв; каждый блок соответствует одному слову в сегментации. Общее качество сегментации вычис- ляется суммированием качества каждого блока. (Таким образом, правильный ответ для приводившейся выше строки будет получен при условии, что сумма quality("meet")+quality("at")+quality("eight") больше суммы любой другой сег- ментации строки.)

Предложите эффективный алгоритм, который получает строку y и вычисляет сегментацию с максимальным общим качеством. (Одно обращение к «черному ящику» для вычисления quality(x) считается одним вычислительным шагом.) (Последнее замечание, не обязательное для решения задачи: для повышения быстродействия программы сегментации на практике используют более слож- ную формулировку задачи: например, предполагается, что решение не только должно быть разумным на уровне слов, но и образовывать связные обороты и предложения. Например, строку «theyouthevent» можно как минимум тремя способами разбить на обычные английские слова, но один из вариантов дает намного более осмысленную фразу, чем два других. Если рассматривать проис- ходящее в терминологии формальных языков, расширенная задача напоминает поиск сегментации, которая также хорошо разбирается в соответствии с грам- матикой используемого языка. Но даже с этими дополнительными критериями и ограничениями в основе многих эффективных систем сегментации лежат методы динамического программирования.)

6. При форматировании текста часто встречается стандартная задача: взять текст с «рваным» правым краем:

Call me Ishmael.

Some years ago,

never mind how long precisely,

having little or no money in my purse,

and nothing particular to interest me on shore,

I thought I would sail about a little and see the watery part of the world.

и преобразовать его в текст, правый край которого «сглажен», насколько это возможно:

Call me Ishmael. Some years ago, never mind how long precisely, having little or no money in my purse, and nothing particular to interest me on shore, I thought I would sail about a little and see the watery part of the world.

Чтобы формализовать эту задачу и начать размышлять над реализацией, сна- чала нужно определить, что же понимать под «сглаженным» правым краем. До- пустим, текст состоит из последовательности слов W = {w1, w2, ..., wn}, а слово w состоит из с. символов. Максимальная длина строки равна L. Будем считать, что при выводе используется моноширинный шрифт, а знаки препинания и пере- носы не учитываются.

Форматирование W состоит из разбиения слов W на строки. В словах, назначен- ных одной строке, после каждого слова, кроме последнего, должен следовать пробел; соответственно если слова w,, wj+i, ..., wk назначены в одну строку, должно выполняться условие


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

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

7. В одном из упражнений с решениями главы 5 представлен алгоритм с временем выполнения O(n log n) для следующей задачи. Рассматриваются цены акций за n последовательных дней, пронумерованных i = 1, 2, ..., n. Для каждого дня i известна биржевая котировка этих акцийp(i) в этот день. (Для простоты будем считать, что в течение дня котировка не изменяется.) Вопрос: как выбрать день i для покупки акций и последующий день j для их продажи, чтобы получить максимальную прибыльp(j)-p(i)? (Если за эти n дней перепродажа с прибылью невозможна, алгоритм должен сообщить об этом.)

В приведенном решении показано, как найти оптимальную пару дней i и j за время O(n log n). Однако на самом деле можно найти еще более эффективный алгоритм. Покажите, как найти оптимальные числа i и j за время O(n).

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

Вот как проходит типичная атака:

• Рой машин прибывает в течение n секунд; на i-й секунде появляются x робо- тов. Благодаря системе раннего оповещения последовательность x1,x2, ..., xn известна заранее.

• В вашем распоряжении имеется электромагнитная пушка (ЭМП), которая может уничтожить часть роботов при появлении; мощность выстрела зави- сит от того, сколько времени заряжалась пушка. Или в более точной форму- лировке: имеется такая функция f (), что по прошествии j секунд с момента последнего выстрела ЭМП может уничтожить до f(j) роботов.

• Итак, если пушка использовалась на к-й секунде и с момента последнего вы- стрела прошло j секунд, она может уничтожить min(xk, f ( j)) роботов. (После использования пушка полностью разряжается).

• Также будем считать, что в исходном состоянии ЭМП полностью разряжена, поэтому если она впервые используется на j-й секунде, она может уничто- жить до f ( j) роботов.

Задача. Для заданной последовательности прибытия роботов x1, x2, ..., xn, и функции перезарядки f ( ) выберите моменты времени, в которые следует активировать ЭМП для уничтожения максимального количества роботов. Пример. Допустим, n = 4, а значения x. и f (i) задаются следующей таблицей.

В оптимальном решении ЭМП активируется на 3 и 4 секундах. На 3 секунде ЭМП прошла 3-секундную зарядку и поэтому уничтожает min(10,4) = 4 роботов; на 4 секунде с момента последнего выстрела прошла всего 1 секунда, поэтому уничтожается min(1,1) = 1 робот. В сумме получается 5.

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

Schedule-EMP(x... ..... x )

Присвоить j наименьшее число, для которого f(j) > xn (если такого числа не существует, присвоить j = n)

Активировать ЭМП на n-й секунде Если n - j > 1

Рекурсивно продолжить для данных x1........... xn_.

(то есть вызвать Schedule-EMP(x1................. xnj))

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

(b) Предложите эффективный алгоритм, который получает план прибытия роботов x1, x2, ..., xn и функцию перезарядки f ( ) и возвращает максимальное количество роботов, которые могут быть уничтожены серией активаций ЭМП.

9. Вы участвуете в администрировании высокопроизводительной компьютерной системы, способной обрабатывать несколько терабайт данных в день. В каждый из n дней поступает различный объем данных; в день i вы получаете x терабайт. За каждый обработанный терабайт ваша фирма получает фиксированную оплату, но все необработанные данные становятся недоступными в конце дня (то есть их обработку нельзя продолжить на следующий день).

Ежедневно обрабатывать все данные не удается из-за возможностей компью- терной системы, способной обрабатывать определенное количество терабайт в день. В системе работает уникальная программа — очень сложная, но не сто- процентно надежная, поэтому максимальный объем обрабатываемых данных убывает с каждым днем, прошедшим с момента последней перезагрузки. В пер- вый день после перезагрузки система может обработать s1 терабайт, во второй день — s2 терабайта и т. д. вплоть до sn; предполагается, что s1 > s2 > s3 > ... > sn > 0. (Конечно, в день i система может обработать не более x терабайт независимо от быстродействия вашей системы.) Чтобы вернуть систему к максимальной производительности, можно перезагрузить ее; однако в любой день, в который система будет перезагружаться, никакие данные вообще не обрабатываются. Задача. Для заданных объемов данных x1, x2, ..., xn на следующие n дней и про- филя системы, описанного серией s1, s2, ..., sn (начиная с только что перезагру- женной системы в день 1), выберите дни для проведения перезагрузки, чтобы максимизировать общий объем обрабатываемых данных.

Пример. Допустим, n = 4, а значения x. и s. задаются следующей таблицей.

В оптимальном решении перезагрузка выполняется только в день 2; в этом случае в день 1 обрабатываются 8 терабайт, затем 0 терабайт в день 2, 7 терабайт в день 3 и 4 терабайта в день 4, итого 19. (Обратите внимание: без перезагрузки

было бы обработано только 8 + 1 + 2 + 1 = 12 терабайт, а с другими стратегиями перезагрузки также получается менее 19 терабайт.)

(a) Приведите пример, обладающий следующими свойствами:

• Объем поставляемых данных превышает возможности обработки, то есть х. > s. для каждого i.

• В оптимальном решении система перезагружается минимум дважды.

Кроме примера, приведите оптимальное решение. Предоставлять доказа- тельства его оптимальности не обязательно.

(b) Предложите эффективный алгоритм, который получает значения x1, x2, ..., xn и s1, s2, ..., sn и возвращает общее количество терабайт, обрабатываемых оптимальным решением.

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

При этом вы сталкиваетесь с проблемой: в любую минуту задание может рабо- тать только на одной из этих машин. Для каждой из ближайших n минут досту- пен «профиль», который описывает свободные вычислительные мощности на каждой машине. В минуту i можно провести a. > 0 шагов моделирования, если задание выполняется на машине A, или b > 0 шагов, если задание выполняется на машине B. У вас также есть возможность передать задание с одной машины на другую, но передача занимает минуту времени, в течение которой задание не обрабатывается.

Итак, для заданной последовательности из n минут план определяется выбо- ром действия (A, B или переход) с тем свойством, что варианты A и B не могут следовать непосредственно друг за другом. Например, если в минуту i задание выполняется на машине A и вы хотите переключиться на машину B, то в мину- ту i + 1 должно быть выбрано действие перехода и только в минуту i + 2 можно будет выбрать B. Значение плана вычисляется как общее количество шагов мо- делирования, выполненных за n минут; таким образом, оно представляет собой сумму а. по всем минутам, в течение которых задание выполняется на машине A, вместе с суммой bi по всем минутам, в течение которых задание выполняется на машине B.

Задача. Для заданных значений a1, a2, ..., an и b1, b2, ..., bn найдите план с макси- мальным значением. (Такая стратегия будет называться оптимальной.) План может начинаться с любой из машин A и B в минуту 1.

Пример. Допустим, n = 4, а значения a1, a2, ..., an и b1, b2, ..., bn задаются следующей таблицей.

Минута 1 Минута 2 Минута 3 Минута 4

A 10 1 1 10

B 5 1 20 20

В плане с максимальным значением в минуту 1 задание выполняется на маши- не A, затем в минуту 2 происходит переход, а в минуты 3 и 4 задание выполня- ется на машине B. Значение этого плана составит 10 + 0 + 20 + 20 = 50.

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

В минуту 1 выбрать машину, на которой достигается большее значение из a1, b1 Присвоить i = 2 Пока i < n

Какой выбор был сделан в минуту i - 1?

Если A:

Если b.., > a+ а...

Выбрать переход в минуту i и B в минуту i + 1 Перейти к итерации i + 2 Иначе

Выбрать A в минуту i Перейти к итерации i + 1 Конец Если

Если B: действовать, как описано выше, со сменой ролей A и B Конец Пока

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

(b) Предложите эффективный алгоритм, который получает значения a1, a2, ..., an и b1, b2, ..., bn, и возвращает значение оптимального плана.

11. Вы работаете на компанию, которая производит компьютерное оборудование и рассылает его фирмам-дистрибьюторам по всей стране. Для каждой из следу- ющих n недель установлен запланированный объем поставки s. (в килограммах) оборудования, которое пересылается грузовым авиаперевозчиком.

• Грузы каждой недели могут перевозиться одной из двух фирм-перевозчиков, A или B. Компания A взимает фиксированную плату r за килограмм (так что стоимость еженедельной поставки составляет r · s).

• Компания B заключает контракты на фиксированную сумму c независимо от веса. При этом контракты с компанией B должны заключаться сразу на четыре недели подряд.

Назовем графиком выбор авиаперевозчика (A или B) для каждой из n недель — с тем ограничением, что компания B, когда она выбирается, должна выбираться на четыре недели подряд. Стоимость графика вычисляется как общая сумма, выплаченная компаниям A и B в соответствии с приведенным выше описанием.

Предложите алгоритм с полиномиальным временем, который получает после- довательность объемов поставок s1, s2, ..., sn и возвращает график с минимальной стоимостью.

Пример. Допустим, r = 1, с = 10, а серия поставок имеет вид 11, 9, 9, 12, 12, 12, 12, 9, 9, 11.

В этом случае в оптимальном графике компания A выбирается на первые три недели, затем компания B на четыре следующие недели и снова компания A на три последние недели.

12. Допустим, вы хотите реплицировать файл в группе из n серверов, обозначенных S1, S2, ..., Sn. За размещение копии файла на сервере S. вносится целочисленная оплата с. > 0.

г

Если пользователь запрашивает файл с сервера S., а копия файла на этом сер- вере отсутствует, система по порядку проверяет серверы S+1, S2, S 3,..., пока не найдет копию файла — например, на сервере S, где j > i. Передача файла с другого сервера требует оплаты в размере j-i. (Обратите внимание: серверы с меньшими индексами S._v S2, ... в поиск не включаются). Стоимость передачи равна 0, если копия файла доступна на сервере S. Копия файла обязательно размещается на сервере Sn, так что все операции поиска гарантированно за- вершатся на Sn.

Требуется разместить копии файлов на серверах так, чтобы сумма оплаты за размещение и передачу файлов была минимальной. Формально конфигурацией называется решение о том, должна ли размещаться копия файла на каждом сервере S. для i = 1, 2, ..., n - 1. (Еще раз напомним, что копия всегда размещается на сервере S.) Общая стоимость конфигурации вычисляется как сумма всех оплат за размещение на серверах с копией файла и сумма всех оплат за передачу файлов, связанных с n серверами.

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

13. Задача поиска циклов в графах естественным образом встречается в систе- мах электронной торговли. Допустим, фирма выполняет операции с акциями n разных компаний. Для каждой пары ί ф j поддерживается обменный курс г, который означает, что одна акция . обменивается на г. акцийj. Курс может быть

дробным: иначе говоря, r.. = 2/3 означает, что вы можете отдать три акции . для

j

получения двух акций j.

Обменный цикл для серии акций ϊ1, ϊ2, ..., .k состоит из последовательного обме- на акций компании .1 на акции компании .2, затем акций компании .2 на акции компании .3, и т. д.; в конечном итоге акции .k обмениваются на акции .1. После такой серии обменов фирма получает акции той же компании .1, с которой все начиналось. Циклические операции обычно нежелательны, поскольку, как правило, в результате у вас остается меньше акций, чем было в самом начале. Но время от времени на короткий промежуток времени открывается возмож- ность увеличить количество акций. Цикл, операции по которому приводят к увеличению количества исходных акций, будем называть благоприятным циклом. Такая возможность открывается в точности тогда, когда произведение всех дробей в цикле превышает 1. Фирма анализирует состояние рынка и хочет знать, существуют ли на нем благоприятные циклы.

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

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

В сети, изменяющейся со временем, естественно возникает задача поиска эф- фективных способов поддержания путей между заданными узлами. При под- держании такого пути приходится учитывать два противоположных фактора: пути должны быть короткими, но при этом путь не должен часто изменяться при изменении структуры сети. (Другими словами, нам хотелось бы, чтобы один путь продолжал работать даже при добавлении и исчезновении ребер, если это возможно.) Ниже описан возможный способ моделирования этой задачи. Предположим, имеется множество мобильных узлов V, в какой-то момент вре- мени существует множество E0 ребер между этими узлами. При перемещении узлов множество ребер преобразуется из E0 в E1, затем в E2, затем в E3 и т. д., вплоть до множества ребер Eъ. Для i = 0, 1, 2, ..., b граф (V, E) обозначается G.. Итак, если рассматривать структуру сети на базе узлов V «по кадрам», она будет представлять собой последовательность графов G0, G1, G2, ..., Gb1, Gb. Предпо- лагается, что все эти графы G являются связными.

Теперь рассмотрим два конкретных узла s, t V. Для пути s-t P в одном из графов

G. длина P определяется как количество ребер в P; обозначим ее i(P). Наша цель — построить такую последовательность путей P0, P1, ..., Pъ, чтобы для каждого i существовал путь s-tP. в G.. Пути должны быть относительно короткими. Кроме того, нежелательно слишком большое количество изменений — точек, в которых изменяется структура пути. Формально определим changes(P0, P1, ..., Pb) как ко- личество индексов i (0 < i < b - 1), для которых P. ф P.+1.

Возьмем фиксированную константу K > 0. Стоимость последовательности путей P0, P1, ..., Pb определяется по формуле

cost(P0, P1, ..., Pь) = X] t (Р,) - К - сhшщеs (⅞,/>.............. Pь )

i-⅛

(a) Предположим, можно выбрать один путь P, который является путем s-t в каждом из графов G0, G1, ..., Gb. Предложите алгоритм с полиномиальным временем для нахождения кратчайшего из таких путей.

(b) Предложите алгоритм с полиномиальным временем для нахождения последовательности путей P0, P1, ..., Pъ с минимальной стоимостью, где P. является путем s-t в G. для i = 0, 1, ..., Ъ.

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

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

• Небесный свод размечен в одномерной координатной системе (в градусах от некоторой центральной базовой линии); событие j происходит в точке с координатой d. для некоторого целого d. В минуту 0 телескоп направлен в координату 0.

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

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

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

Пример. Одномерные координаты событий приведены в следующей таблице. События 1 23456789

Координаты 1 -4 -1 4 5 -4 6 7 -2

В этом случае в оптимальном решении наблюдаются события 1, 3, 6 и 9. Обра- тите внимание: у телескопа хватает времени на перемещение от одного события к другому, хотя он и поворачивается всего на один градус в минуту.

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

Пометить все события j with |dn - dj\ > n - j как недопустимые (так как их наблюдение не позволит наблюдать событие n)

Пометить все остальные события как допустимые

Инициализировать текущую позицию координатой 0 для минуты 0 Пока не будет достигнут конец последовательности

Найти самое раннее допустимое событие j, которое может быть достигнуто без превышения максимальной скорости поворота телескопа Добавить j в множество S

Обновить текущую позицию координатой dj в минуту j Конец Пока Вывести множество S

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

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

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

У каждого работника фирмы, кроме директора, есть начальник. Таким образом, иерархия может быть описана деревом T, корнем которого является директор, а у любого другого узла v имеется родительский узел u, представляющий его начальника. Соответственно, мы будем называть v прямым подчиненным по от- ношению к u. На рис. 6.30 узел A обозначает директора, узлы B и D — прямых подчиненных A, а узел C — прямого подчиненного B.

Чтобы оповестить всех об отмене пикника, директор сначала поочередно звонит каждому из своих прямых подчиненных. Сразу же после звонка подчиненный должен оповестить каждого из своих прямых подчиненных (тоже поочередно). Процесс продолжается до тех пор, пока не будут оповещены все сотрудники. Обратите внимание: каждый участник процесса звонит только своим прямым подчиненным: например, на рис. 6.30 директор A не будет звонить C.


Рис. 6.30. Иерархия с четырьмя участниками. В самой быстрой схеме оповещения A звонит B в первом раунде. Во втором раундеA звонит D, а B звонит C.

Если бы A начал со звонка D, то C не узнал бы о новостях до третьего шага

Можно рассматривать процесс распространения информации как разделенный на раунды. В одном раунде каждый работник, уже знающий об отмене, звонит одному из своих прямых подчиненных по телефону. Количество раундов, не- обходимое для оповещения всех участников, зависит от последовательности, в которой каждый участник звонит своим прямым подчиненным. Например, на рис. 6.30 оповещение будет состоять из двух раундов, если A сначала позвонит B, но займет целых три раунда, если A начнет со звонка D.

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

17. Ваши друзья занимаются анализом динамики цен на акции технологических фирм. Они определили закономерность, которая была названа возрастающим трендом; формальное описание этой закономерности приводится ниже. Известна последовательность цен на некие акции P[1], P[2], ..., P[n], зафик- сированных на момент закрытия биржи для n последовательных дней. Воз- растающим трендом в этой серии называется такая подпоследовательность P[iJ, P[i2], ..., P[ik] для дней i1 < i2 < ... < ik, у которой:

i1 = 1;

• P[i] < P[/j.+J для всех j = 1, 2, ..., k - 1.

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

Требуется найти самый длинный возрастающий тренд для заданной последо- вательности цен.

Пример. Допустим, n = 7, а последовательность цен выглядит так:

10, 1, 2, 11, 3, 4, 12.

В этом случае самый длинный возрастающий тренд образуется в дни 1, 4 и 7. Обратите внимание: дни 2, 3, 5 и 6 тоже образуют серию возрастающих цен, но так как эта подпоследовательность не начинается с дня 1, она не соответствует определению возрастающего тренда.

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

Определить i = 1 L = 1

For j = 2 to n

Если If P[j] > P[i]

Присвоить i = j.

Увеличить L на 1.

Конец Если Конец For

В своем примере приведите длину самого длинного возрастающего тренда и укажите, какой результат находит приведенный алгоритм.

(b) Предложите эффективный алгоритм, который получает последователь- ность цен P[1], P[2], ..., P[n] и возвращает длину самого длинного возраста- ющего тренда.

18. Рассмотрим задачу выравнивания последовательностей для алфавита из четы- рех букв {z1, z2, z3, z4} с заданными стоимостями разрыва и несовпадения. Пред- положим, каждый из этих параметров является положительным целым числом. Имеются две строки A = a1a2... am и B = bib2...bn с предложенным выравниванием между ними. Предложите алгоритм θ(mn), который решит, является ли вы- равнивание уникальным выравниванием минимальной стоимости между A и B.

19. Вы консультируете группу специалистов (лучше обойтись без подробностей), занимающихся отслеживанием и анализом электронных сигналов от кораблей в прибрежных водах Атлантики. Они хотят получить быстрый алгоритм для базовой операции, который встречается достаточно часто: «распутывание» суперпозиции двух известных сигналов. А именно, ваши работодатели пред- ставляют ситуацию, в которой два корабля снова и снова передают короткую последовательность из 0 и 1; нужно убедиться в том, что полученный сигнал представляет собой результат простого чередования этих двух передач и в него не добавлено ничего лишнего.

Немного уточним формулировку задачи. Для заданной строки х, состоящей из 0 и 1, xk обозначает результат конкатенации к копий строки х. Мы будем называть строку х' повторением х, если она является префиксом xk для некоторого числа к. Таким образом, х' = 10110110110 является повторением х = 101.

Строка 5 называется чередованием х и у, если ее символы можно разбить на две (необязательно смежные) последовательности s' и s”, так что s' является повто- рением х, а s” является повторением у. (При этом каждый символ s принадлежит либо s', либо s''). Например, если х = 101 и у = 00, строка s = 100010101 является чередованием х и у, поскольку символы 1, 2, 5, 7, 8, 9 образуют серию 101101 (по- вторение х), а оставшиеся символы 3, 4 и 6 образуют серию 000 — повторение у. В контексте нашего приложения х и у являются повторяющимися последова- тельностями, полученными от двух кораблей, а s — прослушиваемый сигнал: нужно убедиться в том, что s «разворачивается» в простые повторения х и у. Предложите эффективный алгоритм, который получает строки s, х и у и решает, является ли s чередованием х и у.

20. Семестр близится к завершению, и вам предстоит выполнить курсовые проек- ты по n учебным курсам. За каждый проект будет выставлена оценка — целое число в диапазоне от 1 до g > 1; более высокие числа означают лучшие оценки. Разумеется, вы стремитесь к максимизации средней оценки по n проектам.

Вы располагаете временем H > n часов для работы над проектами (с перерыва- ми); нужно решить, как распределить это время. Для простоты будем считать, что H — положительное целое число и на каждый проект расходуется целое количество часов. Чтобы определить, как лучше распределить время, вы опре- деляете множество функций {f: i = 1, 2, ..., n} (конечно, оценки весьма приблизи- тельные) для каждого из n проектов: потратив h < H часов на проект по курсу i, вы получите оценкуfi(h). (Функции f не убывают: если h < h', тоfi(h) 40 000. Предположим, вы начинаете с x = 100 000 ак- ций. При продаже всех акций в день 1 цена составит 70 за акцию, а общий до- ход — 7 000 000. Если же продать 40 000 акций в день 1 по цене 89 за акцию, а затем продать остальные 60 000 акций в день 2 по цене 59 за акцию, общий доход составит 7 100 000.

26. Вы руководите компанией, которая продает некий крупный товар (допустим, грузовики). Аналитики предоставляют вам прогнозы с предполагаемым объ- емом продаж за следующие n месяцев. Обозначим d. предполагаемый объем продаж в месяце i. Будем считать, что все продажи происходят в начале месяца, а непроданные грузовики хранятся на складе до начала следующего месяца. На складе помещается максимум S грузовиков, а затраты на хранение одно- го грузовика в течение месяца равны C. Чтобы получить партию грузовиков с завода, вы размещаете заказ. За каждое размещение заказа (независимо от количества заказанных грузовиков) взимается фиксированная плата K. Изна- чально на складах нет ни одного грузовика. Требуется разработать алгоритм, который решает, как разместить заказы для выполнения всех требований {di} с минимальными издержками. Вкратце:

• расходы складываются из двух составляющих: 1) хранение — за каждый грузовик на складе, который не продан в этом месяце, приходится платить C; 2) размещение заказа — за каждый заказ приходится платить K;

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

Предложите алгоритм, решающий эту задачу за время, полиномиальное по n и S.

27. Владелец бензоколонки столкнулся со следующей проблемой: имеется большой подземный бак, в котором хранится бензин; емкость бака составляет L галлонов. Заказы обходятся дорого, поэтому они оформляются относительно редко. Для каждого заказа владелец должен заплатить фиксированную цену P (кроме сто- имости заказанного бензина). Однако хранение галлона в течение дня требует затрат с, поэтому слишком большие запасы увеличивают расходы на хранение. Владелец бензоколонки собирается закрыть ее на неделю зимой. К моменту за- крытия бак должен быть пустым. К счастью, на основании многолетнего опыта он может точно предсказать, сколько бензина будет расходоваться ежедневно до заданного момента. Допустим, что до закрытия осталось n дней и в день i (i = 1, ..., n) будет расходоваться g галлонов. Предполагается, что в конце дня 0 бак пуст. Предложите алгоритм, который решает, в какие дни следует разме- щать заказы и сколько бензина нужно заказывать для минимизации общих затрат.

28. Вспомните задачу планирования из раздела 4.2, в которой мы стремились к минимизации максимальной задержки. Существуют n заданий, каждое зада- ние имеет предельное время d. и необходимое время обработки t; все задания доступны для планирования, начиная с времени 5. Чтобы задание i было вы- полнено, ему необходимо выделить период времени от s. > s до f = s. + t, причем разным заданиям должны назначаться неперекрывающиеся интервалы. Такое распределение времени называется расписанием.

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

• (a) Докажите, что существует оптимальное решение J (то есть планируемое множество максимального размера), в котором задания J планируются по возрастанию предельного времени.

• (b) Предположим, все значения предельного времени d и необходимого времени t. являются целыми числами. Предложите алгоритм для поиска оптимального решения. Алгоритм должен выполняться за время, полино- миальное по количеству заданий n и максимальному предельному времени D = max d..

I l

29. Граф G = (V, E) состоит из n узлов, каждая пара узлов соединена ребром. Каж- дому ребру (i, j) присвоен положительный вес w ф предполагается, что веса удовлетворяют неравенству треугольника wk < Wj+w^. Для подмножества V Έ V запись G[V'] обозначает подграф (с весами ребер), построенный для узлов из V'. Дано множество X !Ξ V из к терминальных узлов, которые должны быть со- единены ребрами. Деревом Штейнера для X называется такое множество Z, что X !Ξ Z !Ξ V в сочетании с остовным поддеревом T подграфа G[Z]. Весом дерева Штейнера называется вес дерева T.

Покажите, что существует f ( ) и полиномиальная функция p(), для которых задача нахождения дерева Штейнера с минимальным весом для X может быть решена за время O(f (k)p(n)).

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

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

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