Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Динамическое программирование




Вывод

Ввод

Пример

Обозначим через F(N) количество сообщений, которые можно сформировать из первых N цифр. Попытаемся выразить F(N+ 1 ) через значения этой функции на предыдущих шагах. Рассмотрим два случая:

· цифры на местах N и N +1 образуют двухзначное число, большее 33;

· цифры на местах N и N +1 образуют двухзначное число, не превышающее 33.

В первом случае любое сообщение, зашифрованное первыми N цифрами, может быть дополнено буквой, код которой содержится в позиции N +1. В то же время последние две цифры не могут кодировать какую-либо букву. Значит, в этом случае F(N+ 1 )=F(N).

Во втором случае помимо этого любое сообщение, представленное первыми N -1 цифрами, может быть дополнено буквой, код которой содержится в позициях N и N +1. В этом случае F(N+ 1 )= F(N)+ F(N- 1 ).

Очевидно, F( 1 ) =1. Правильно считать, что F( 0 ) =1 – пустое сообщение, которое может дополняться. Далее проблем не видно. Снова потребуется использование длинной арифметики.

 

Динамическое программирование – это особый способ оптимизации, специально приспособленный к так называемым “многошаговым” операциям, в частности к задачам перебора вариантов. Предположим, что эффективность операции определяется функцией стоимости, которая складывается из стоимостей на отдельных шагах, то есть

F (a1, a2, …, am) = С(a1) + С(a2) +…+ С(am),

где С(ai) – функция, определенная для всех ai. Показатели такого вида называют аддитивными. Требуется найти такой набор (a1, a2, …, am), чтобы стоимость была минимальной (максимальной).

Рассмотрим примеры многошаговых операций.

1. Руководитель предприятия намерен эксплуатировать некоторый аппарат в течение m лет. В начале каждого года он может принять одно из трех решений:

1) продать аппарат и заменить его новым;

2) провести капитальный ремонт и продолжить эксплуатацию;

3) продолжить эксплуатацию без капитального ремонта.

Требуется спланировать управление на все m лет, чтобы суммарные расходы на эксплуатацию, ремонт и приобретение новых аппаратов были минимальными. Управление состоит в выборе одного из трех решений в начале каждого года. Обозначим их цифрами 1, 2 и 3.

Стоимость складывается из годовых затрат. Решение представляет из себя комбинацию чисел 1, 2 и 3. Например, (3, 3, 2, 2, 2, 1, 3, …) означает: первые 2 года эксплуатировать аппарат без ремонта, последующие 3 года производить ремонт, в начале шестого года продать, купив новый, затем снова эксплуатировать без ремонта и т. д.

2. Планируется деятельность промышленных предприятий B1, B2, …, Bk на m лет. В начале периода на развитие всей группы предприятий выделены средства в размере S единиц. В процессе работы предпрятия вложенные в него средства частично расходуются, а частично сохраняются и снова могут быть перераспределены. Каждое предприятие за год приносит доход, зависящий от того, сколько средств в него вложено. В начале каждого года имеющиеся в наличии средства перераспределяются между предприятиями. Ставится вопрос: какое количество средств нужно выделять каждому предприятию, чтобы суммарный доход за m лет был максимальным?

Суммарный доход представляет собой сумму доходов на отдельных шагах (годах). На каждом i-ом шаге предприятиям выделяются некоторые средства ai1, ai2, …, aik (первый индекс – номер шага, второй – номер предприятия), то есть ai = (a i1, a i2, …, a ik). Таким образом, элементы ai представлят собой вектора.

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

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

Планируя последний шаг, нужно рассмотреть все возможности того, чем кончился предпоследний (m-1)-й шаг, и для каждой такой возможности найти наилучший вариант последнего шага. В динамическом программировании это называют условным оптимальным управлением, так как оно выбирается из условия, что предпоследний шаг закончился определенным образом. Затем находят условное оптимальное управление на (m-2)-м шаге и т. д., пока не доходят до первого шага, на котором находится уже истинное оптимальное управление, минимизирующее функцию стоимости. Сейчас двигаясь от начала к концу, на каждом i-ом шаге находят наилучшие значения ai.

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

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

Пусть, например, прямоугольник (квадрат) заполнен следующим образом:

 

  A B C D E
           
          -11
           
  -15       -1
      -10    

 

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

Начнем с конечной клетки E 5. В нее можно попасть за один ход из клеток D 5 и E 4. В обеих клетках возможен единственный ход. В клетке D 5 проставляется стоимость 14+9=23, а в E 4 – (-1)+9=8. Далее проставим минимальную стоимость во все клетки последней строки, двигаясь влево от клетки D 5. Для каждой такой клетки также имеется единственный ход, и стоимость формируется путем сложения стоимости текущей клетки с минимальной стоимостью клетки справа, рассмотренной на предыдущем шаге. Аналогично снизу вверх находятся минимальные стоимости для всех клеток последней вертикали E.

  A B C D E
  43 ► 35 ► ▼ 28 ►
  33 ► 29 ►
  38 ►
  20 ► 35 ► 20 ►
  59 ► 34 ► 13 ► 23 ►  

 

Далее также в порядке снизу вверх рассмотрим клетки предпоследнего столбца D. В клетке D 4 нужно, очевидно, двигаться направо, поскольку стоимость кратчайшего пути от клетки E 4 меньше, чем от D 5. Запомним направление движения из клетки D 4 и минимальную стоимость 12+8 = 20. В клетке D 3 лучший ход вниз обеспечивает стоимость 8+12=20. Затем можем перейти к третьему столбцу С и т. д. Отметим, что в клетке B 1 оба хода приводят к одинаковой стоимости 35.

Начальная клетка A 1 будет рассмотрена последней. В итоге получаем, что минимальная стоимость пути из A 1 в E 5 составляет 43 единицы. Сам путь восстанавливается по тем лучшим ходам, которые были сохранены. В этом примере есть два пути минимальной стоимости: A 1, B 1, B 2, C 2, C 3, C 4, C 5, D 5, E 5 и A 1, B 1, C 1, C 2, C 3, C 4, C 5, D 5, E 5.

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

Отметим в заключение некоторые дополнительные аспекты применения методов динамического программирования.

1. Число шагов процесса может быть переменным. Например, это произойдет в рассмотренной задаче, если разрешить ход в соседнюю клетку по диагонали сверху вниз.

2. Функция стоимости может выражаться не суммой, а произведением стоимостей на отдельных шагах.

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

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

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

Рассмотрим еще одну задачу, связанную с подходами динамического программирования.

Возрастающая подпоследовательность. Даны N целых чисел X 1, X 2,..., XN. Требуется вычеркнуть из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.

Ввод из файла INPUT.TXT. В первой строке находится число N. В следующей строке - N чисел через пробел.

Вывод в файл OUTPUT.TXT. В первой строке выводится количество невычеркнутых чисел, во второй - сами невычеркнутые числа через пробел в исходном порядке. Если вариантов несколько, вывести любой.

Ограничения: 1 ≤ N ≤ 5000, 1 ≤ Xi ≤ 60 000, время 2 с.




Поделиться с друзьями:


Дата добавления: 2014-01-11; Просмотров: 1010; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.021 сек.