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

Вы управляете строительством рекламных щитов на дороге с интенсивным дви- жением, идущей с запада на восток на протяжении М миль. Возможные точки для установки рекламных щитов определяются числами x1, x2, ..., х , каждое из которых принадлежит интервалу [0, М] (эти числа определяют позицию в милях от западно- го конца дороги).
Разместив рекламный щит в точке х, вы получите прибыль r. > 0.

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

Пример. Предположим, M = 20, n = 4, {xp x2, x3, x4} = {6, 7, 12, 14}, и {r1, r2, r3, r4} = = {5, 6, 5, 1}. В оптимальном решении рекламные щиты размещаются в точках x1 и x3, с суммарной прибылью 10.

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

Решение

Следующие рассуждения позволяют естественным образом применить к этой задаче принцип динамического программирования. Рассмотрим оптимальное решение для заданного входного экземпляра задачи; в этом решении рекламный щит либо размещается в точке xn, либо не размещается. Если щит не размещается, то оптимальное решение для точек x1, ..., xn совпадает с оптимальным решением для точек x1, ..., xn1; если же щит размещается, следует исключить xn и все остальные точки на расстоянии до 5 миль включительно и найти оптимальное решение для полученного множества. Аналогичные рассуждения применимы при рассмотрении задачи, определяемой только первыми j сайтами x1, ..., x:. точка x либо включается в оптимальное решение, либо не включается с теми же последствиями.

Определим вспомогательные обозначения, которые помогут выразить эту идею. Для точки x. величина e( j) обозначает крайнюю точку на восточном направ- лении, которая удалена от x. не более чем на 5 миль. Так как точки нумеруются с запада на восток, это означает, что допустимыми вариантами после решения о размещении рекламного щита в точке x. остаются точки x1, x2, ..., x., но не точки x ,л.., ..., x. ..

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

Итак, мы собрали основные ингредиенты, необходимых для работы алгоритма динамического программирования.

Во-первых, это множество из n подзадач, со- стоящее из первых j точек для j = 0, 1, 2, ..., n. Во-вторых, имеется рекуррентное от- ношение OPT( j) = max(r. + OPT(e(j)), OPT( j - 1)), которое позволяет строить решения подзадач.

Чтобы преобразовать все это в алгоритм, достаточно определить массив M, в ко- тором будут храниться значения OPT, и сформировать на основе рекуррентного отношения цикл, который строит значения M[ j] в порядке возрастания j.

Инициализировать M[0] = 0 и M[1] = r1 For j = 2,3.............. n:

Вычислить M[j] с использованием рекуррентного отношения End For Вернуть M[n]

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

При заданных значениях e(j) для всех j время выполнения алгоритма состав- ляет O(n), потому что каждая итерация цикла выполняется за постоянное время. Мы также можем вычислить все значения e(j) за время O(n): для каждой точки x определяется х'. = x - 5. Затем отсортированный список x1, ..., xn объединяется с от- сортированным списком x'1, ..., x'n за линейное время, как было показано в главе 2. Теперь мы перебираем элементы объединенного списка; добравшись до элемента xj, мы знаем, что все последующие элементы до x. не могут быть выбраны вместе с x. (потому что находятся на расстоянии менее 5 миль), поэтому мы просто определя- ем e( j) как наибольшее значение ., для которого мы обнаружили x. при переборе.

И последнее замечание по поводу этой задачи. Очевидно, решение очень по- хоже на решение задачи взвешенного интервального планирования, и для этого существует веская причина. Дело в том, что задача размещения рекламных щитов может быть напрямую сформулирована как экземпляр задачи взвешенного интер- вального планирования. Предположим, для каждой точки x. определяется интервал с конечными точками [x - 5, x ] и вес r. Затем для любого неперекрывающегося множества интервалов соответствующее множество точек обладает тем свойством, что никакие две точки не могут находиться на расстоянии менее 5 миль. Соот- ветственно, для любого такого множества точек (никакие две на расстоянии ме- нее 5 миль) интервалы, связанные с ними, не будут перекрываться. Следовательно, группы неперекрывающихся интервалов точно соответствуют множеству действи- тельных размещений рекламных щитов, а подстановка только что определенного нами множества интервалов (с их весами) в алгоритм взвешенного интервального планирования даст желаемое решение.

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

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

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