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

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

Типичная ситуация выглядит так.

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

Предположим, n = 3, p(1) = 9, p(2) = 1, p(3) = 5. Алгоритм должен вернуть «По- купать в день 2, продавать в день 3» (в этом случае прибыль составит $4 на акцию — максимально возможная прибыль за этот период).

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

Покажите, как найти правильные числа i и j за время O(n log n).

Решение

В этой главе уже были рассмотрены примеры, в которых перебор пар элементов методом «грубой силы» сокращается до O(n log n) методом «разделяй и властвуй». Здесь мы сталкиваемся с аналогичной проблемой — нельзя ли и в этом случае при- менить стратегию «разделяй и властвуй»?

Было бы естественно рассмотреть первые и последние n/2 дней по отдельности, рекурсивно решить проблему для каждого из этих двух множеств, а затем сфор- мировать из полученных результатов общее решение за время O(n). Тогда можно будет прийти к обычному рекуррентному отношению Г (и) < 2Т |— + O(n), а зна- чит, и ко времени O(n log n) согласно (5.1).

Кроме того, для упрощения задачи мы сделаем обычное предположение, что n является степенью 2. Такое предположение не ведет к потере общности: если n' — следующая степень 2 больше n, можно назначитьp(i) = p(n) для всех i между n и n'. Ответ при этом не изменится, а размер входных данных в худшем случае увеличится вдвое (что не повлияет на обозначение O()).

Пусть S — множество дней 1, ..., n/2, а S' — множество дней n/2 + 1, ..., n. Наш алгоритм «разделяй и властвуй» базируется на следующем наблюдении: либо су- ществует оптимальное решение, при котором инвесторы удерживают купленные ранее акции в конце дня n/2, либо его не существует. Если решения не существует, то оптимальное решение является лучшим из оптимальных решений множеств S и S'. Если существует оптимальное решение, при котором акции удерживаются в конце дня n/2, то значение этого решения равно p( j) - p(i), где i S и j S'. Но

это значение максимизируется простым выбором i S, при котором минимизиру- ется p(i), и выбором j S', при котором максимизируется p( j).

Следовательно, наш алгоритм должен взять лучшее из трех возможных реше- ний:

♦ Оптимальное решение для S.

♦ Оптимальное решение для S'.

♦ Максимум p( j) - p(i) для i S и j S'.

Первые две альтернативы вычисляются за время T(n/2) (каждая посредством рекурсии), а третья альтернатива вычисляется нахождением минимума в S и макси- мума в S', что выполняется за время O(n). Следовательно, общее время выполнения

T(n) удовлетворяет условию Г(tt) а..

Также напомним, что задача подсчета инверсий была представлена как способ оценки различий между вариантами упорядочения. Однако кому-то эта метри- ка может показаться излишне чувствительной. Назовем пару значимой инверси- ей, если i < j, а а. > 2а. Приведите алгоритм O(n log n) для подсчета количества значимых инверсий между двумя ранжировками.

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

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

Вопрос заключается в следующем: можно ли найти в множестве из n карт подмножество с размером более n/2, эквивалентных друг другу? Считается, что единственной возможной операцией с картами является проверка их на эквивалентность.

Покажите, как найти ответ на вопрос так, чтобы количество проверок эквивалентности не превышало O(n log n).

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

ваться последовательностью точек {1, 2, 3, ..., n) на прямой; в каждой из точек j находится частица с зарядом q.. (Каждый заряд может быть как положитель- ным, так и отрицательным.)

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


Конец Если Конец For Вывести F.

Конец For

Нетрудно проанализировать время выполнения этой программы: каждое вы- полнение внутреннего цикла по i занимает время O(n); этот внутренний цикл вызывается O(n) раз, так что общее время выполнения составляет O(n2).

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

Помогите им и разработайте алгоритм, который вычисляет все силы F. за вре- мя O(n log n).

5. Удаление скрытых поверхностей — задача из области компьютерной графики, которая вряд ли нуждается в долгих объяснениях: если Вуди стоит перед Баз- зом, то вы видите Вуди, а не Базза; если Базз стоит перед Вуди... ну, в общем, вы поняли.

Особенность удаления скрытых поверхностей заключается в том, что часто вычисления производятся намного чаще, чем подсказывает интуиция. Про- стой геометрический пример демонстрирует суть ускорения. Имеются n не- вертикальных линий на плоскости L1, ..., L , i-я линия определяется уравнением у = ах + bПредполагается, что никакие три линии не пересекаются в одной точке. Линия L. будет называться верхней в заданной координате x0, если ко- ордината у для точки x0 больше координат у всех остальных линий в точке x0: ax0 + b. > ax0 + b. для всех j = i. Линия L. называется видимой, если существует координата х, в которой она является верхней (то есть какая-то часть линии видна, если смотреть на нее «сверху вниз» из у = ∞).

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

Рис. 5.10. Пример удаления скрытых поверхностей с пятью линиями (помеченными 1-5).

Все линии, кроме 2, являются видимыми


6. Рассмотрим полное бинарное дерево T из n узлов, где n = 2d - 1 для некоторого d. Каждый узел v дерева T помечен вещественным числом х Считайте, что все вещественные числа различны. Узел v дерева Tявляется локальным минимумом, если метка xv меньше метки xw для всех узлов w, соединенных с v ребром.

Вы получаете полное бинарное дерево T, но метки заданы косвенно: для каж- дого узла v значение xv определяется проверкой узла v. Покажите, как найти локальный минимум T с использованием только O(log n) проверок узлов T.

7. Предположим, имеется решетчатый граф n χ n G. (Решетчатый граф n χ n представляет собой граф смежности шахматной доски n χ n. Или для полной точности — граф, множество узлов которого является множеством всех упоря- доченных пар натуральных чисел (i, j), где 1 < i < n и 1 < j < n; узлы (i, j) и (k, i) соединены ребром в том и только в том случае, если |i - k| + j - i\ = 1.) Воспользуемся терминологией из предыдущего вопроса. Снова каждый узел v помечается вещественным числом xv; считается, что все метки различны.

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

Покажите, как найти локальный минимум G с использованием только O(n) проверок узлов G. (Обратите внимание: G состоит из n2 узлов.)

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

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

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